Local MinMax problem [reviewed]

Problem

Given the list of numbers, find the local min or local max

Local max or min is the number that exists between the first and last number.

For example,


1,2,3,4,3,2 => local max exists, which is 4

1,2,3,4,5,6,7 => No local max or local min exists

 5,4,3,2,1 => No local max or local min exists

 9,8,7,6,5,6,7,8,9 => local min exists, which is 5.

 Challenging part is that your problem should run faster than O(N).



hint: all the numbers are increasing by 1 or decreasing by 1. There is no gap.

Here is the algorithm. There can be two cases that we need to consider.

1) Ascending numbers

No local min or max: The last number, A[N-1] should be the same as A[0] + N-1, where N is the length of the list.
 
     A[0] + N -1  = A[N-1]

If not, there must be local max.

In that case, the local min can be calculated by the following formula

  Local max = (A[0] + N-1 + A[N-1])/2


Figure 1. Local max

As shown in Figure 1. if the numbers ascends to the end. A[0] + N-1 will be same as A+B.
However, there exists a local max. the last number in the array in A[N-1] is the same as A-B.

Therefore, (A[0] + N-1 + A[N-1])/2 = (A+B + A - B)/2 = 2A/2, thereby getting A.


2) Descending numbers

No local min or max: The last number in the array, A[N-1] should be the same as A[0]-(N-1), where N is the length of the list.

    A[0] - (N-1) = A[N-1]

If not, there must be local min

In that case, the local min can be calculated by the following formula

  Local max = (A[0] + N-1 + A[N-1])/2


Figure 2. Local min
As shown in Figure 1. if the numbers descends to the end. A[0] - (N-1) will be same as -(A-B).
However, there exists a local min. the last number in the array in A[N-1] is the same as -A+B.

Therefore, (A[0] - N-1 + A[N-1])/2 = (-A-B - A + B)/2 = -2A/2, thereby getting -A.

Don't forget the fact that, A[0] > -A in the example.

Based on the algorithm discussed, the following implementation can be written.

If look at the formula carefully, it will result in the max or min number when there is no local min or local max exists.

UPDATE(2019-08-01): solved the problem again using binary search, which is practically faster than $O(N)$. However, if the numbers between 0 and N-1 are either up-down or down-up V shape. The above algorithm will work and will be O(1). Need to look closer.

Here is the solution in python.

Practice statistics

10:00: to find the algorithm using a binary search
11:43: to write up the code and test case (No bug was found !!! yeah ...)
01:10: to write up test cases.

UPDATE(2019-08-01): Here is another solution running in $O(1)$ via simple computation to find the middle value.
This question could be just a brain teaser than algorithm question.


Practice statistics

10:00: to write the code with algorithm
02:00: to fix the logical error returning position instead of value and switching min and max

Comments

Post a Comment

Popular posts from this blog

Planting flowers with no adjacent flower plots

Image
Problem Suppose you have a long flowerbed in which some of the plots are planted and some are not. However, flowers cannot be planted in adjacent plots - they would compete for water and both would die. Given a flowerbed (represented as an array containing booleans), return if a given number of new flowers can be planted in it without violating the no-adjacent-flowers rule  Sample inputs  Input: 1,0,0,0,0,0,1,0,0  3 => true  4 => false  Input: 1,0,0,1,0,0,1,0,0  1 => true  2 => false  input: 0  1 => true  2 => false  public boolean canPlaceFlowers(List flowerbed, int numberToPlace) {  // Implementation here  }
Read more
  Given an array of  intervals  where  intervals[i] = [start i , end i ] , merge all overlapping intervals, and return  an array of the non-overlapping intervals that cover all the intervals in the input . Example 1: Input: intervals = [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6]. Example 2: Input: intervals = [[1,4],[4,5]] Output: [[1,5]] Explanation: Intervals [1,4] and [4,5] are considered overlapping.   Constraints: 1 <= intervals.length <= 10 4 intervals[i].length == 2 0 <= start i <= end i <= 10 4
Read more

Find the maximum number of bomb that can be detonated

  Problem You are given a list of bombs. The range of a bomb is defined as the area where its effect can be felt. This area is in the shape of a circle with the center as the location of the bomb. The bombs are represented by a 0-indexed 2D integer array bombs where bombs[i] = [xi, yi, ri]. xi and yi denote the X-coordinate and Y-coordinate of the location of the ith bomb, whereas ri denotes the radius of its range. You may choose to detonate a single bomb. When a bomb is detonated, it will detonate all bombs that lie in its range.  These bombs will further detonate the bombs that lie in their ranges. Given the list of bombs, return the maximum number of bombs that can be detonated if you are allowed to detonate only one bomb. Input: bombs = [[2,1,3],[6,1,4]] Output: 2 Explanation: The above figure shows the positions and ranges of the 2 bombs. If we detonate the left bomb, the right bomb will not be affected. But if we detonate the right bomb, both bombs will be detonated. So...
Read more