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

  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

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

Stock price processing problem

Question You are given a stream of records about a particular stock. Each record contains a timestamp and  the corresponding price of the stock at that timestamp. Unfortunately due to the volatile nature of the stock market, the records do not come in order. Even worse, some records may be incorrect.  Another record with the same timestamp may appear later in the stream   correcting the price of the previous wrong record. Design an algorithm that: Updates the price of the stock at a particular timestamp, correcting the price from any previous records at the timestamp. Finds the latest price of the stock based on the current records. The latest price is the price at the latest timestamp recorded. Finds the maximum price the stock has been based on the current records. Finds the minimum price the stock has been based on the current records. Implement the StockPrice class: StockPrice() Initializes the object with no price records. void update(int timestamp, int price) Updates the price of
Read more