- Min Max Riddle
- Discussions

# Min Max Riddle

# Min Max Riddle

+ 24 comments A few hints for people who are banging their heads on the wall trying to pass all test cases:

1) O(N) solution is possible using stacks; avoid DP for this problem

2) Think about how to identify the largest window a number is the minimum for (e.g. for the sequence

`11 2 3 14 5 2 11 12`

we would make a map of number -> window_size as`max_window = {11: 2, 2: 8, 3: 3, 14: 1, 5: 2, 12: 1}`

) - this can be done using stacks in O(n)3) Invert the max_window hashmap breaking ties by taking the maximum value to store a mapping of windowsize -> maximum_value (continuing with example above

`inverted_windows = {1: 14, 8:2, 3:3, 2:11}`

4) starting from w=len(arr) iterate down to a window size of 1, looking up the corresponding values in

`inverted_windows`

and fill missing values with the previous largest window value (continuing with the example result = [2, 2, 2, 2, 2, 3, 11, 14] )5) Return the result in reverse order (return [14, 11, 3, 2, 2, 2, 2, 2])

+ 1 comment We will be using the term “MaxMin” to denote “maximum minimum”.

1.

Let's have a look at the brute force solution.

Let's say : arr = [ 1, 4, 6, 5, 3, 4, 5 ]

Brute force gives us O(N^2) time complexity and the array used for the solution gives O(N) space complexity.

You can find several solutions in the comments to optimise the time complexity.

What follows is an explanation for the shortest solution I found in the comments. I had to spend quite some time analysing the code before I understood what was going on. Hat tip to Liu Yu-Chi (@louisfghbvc) from Taiwan for the code.

C++ with O(N) :

vector<long> riddle(vector<long> arr) { arr.push_back(-1); int n = arr.size(), i = 0; vector<long> res(n-1); stack<long> st; while(i < n){ if(st.empty() || arr[i] > arr[st.top()]) st.push(i++); else{ long val = arr[st.top()]; st.pop(); int len = st.empty() ? i : i-st.top()-1; res[len-1] = max(val, res[len-1]); } } for(int i = n-3; i >= 0; --i) res[i] = max(res[i], res[i+1]); return res; }

2.

Find an ideal situation that makes the solution easier. Let's pretend the array will be an ordered ascending array.

Let’s say : arr = [ 1 , 2 , 3 , 4 , 5 , 6 ].

An input with ascending order would permit us to find the MaxMin much more easily starting from the back like this :

3.

Let’s take a look at what happens when the value descends at some point. This creates a “bump” in the sequence.

Let’s consider the array [ 1 , 5 , 6 , 4 , 5 , 6 ] :

In this case the logic from ascending arrays doesn’t work anymore. We get the first wrong result with window size = 4 which gives 6 as a result where it should be 3.

MaxMin(1) = 5

MaxMin(2) = 4

MaxMin(3) = 3

MaxMin(4) = ??? logic breaks, should’ve been 3

So here’s where the STACK comes in. Instead of running through the array backwards, we will start from the beginning. As we travel through the array, we store the indexes in a stack. When we encounter a descent, we will evaluate the “bump” or ascent that precedes it.

We want to take advantage of the simplified logic from ascending arrays. In order to do so we will eliminate the bump by popping the stack when we evaluate that bump.

In order to trigger the evaluation of the final ascending slope we will add an element with value [-1] to the original array : [ 1 , 5 , 6 , 3 , 4 , 5 , -1 ]

We’re going to create some temporary solutions by applying the previous logic on a local scale -- or think of it as local ascending stretches. In the next figure, we see such a stretch between index 0 and index 2 where the value ascends from 1 over 5 to 6.

Notice how the stack get’s represented on the horizontal axis.

MaxMin(1) = 6 MaxMin(1) = 5 : second result for MaxWin(1)

MaxMin(2) = 5 MaxMin(2) = 4 : second result for MaxWin(2)

MaxMin(5) = 3

MaxMin(6) = 1

As you can see, instead of running through the array backwards, we are now beginning from the start. As we travel through the array, we store the indexes in a STACK. Each time we encounter a “dive” or a “drop”, we pop the STACK until we end up with an ascending array. At the same time we store the temporary results for the indexes that get popped off.

Pay attention to how the window size for a solution is determined by the current index and the index at the top of the stack. So for instance when the current index is [6] (with value [-1]) and we evaluate index [3], the index at the top of the stack is [0]. Therefore value [3] at index [3] will be a solution for a window size that fits between indexes [0] and [6] = size[5]

Notice how in the above figure, we find 2 temporary results:

For size [1] we find value [6].

For size [2] we find value [5].

Then at the end we find 2 more results for the same sizes:

For size [1] we find value [5].

For size [2] we find value [4].

So we’ll have to compare these results and only keep the maximum value of the 2:

Size [1] → value [6]. Size [2] → value [5].

Then at last we find 2 more results:

For size [5] we find value [3].

For size [6] we find value [1].

So we get the partial solution : [ 6 , 5 , ?? , ?? , 3 , 1 ]

We didn’t collect any results for sizes [3] and [4]. Looking at the chart you can easily tell that both should have a value of [3]. As a generalisation you could say that the results that were left blank, should get the value of the next solved bigger window size.

But how can we tell that we have to fill the blanks with the value of the bigger window size? Why not the smaller window size?

Well : the smaller window size would be impossible. Look at the graph above and notice that we lose the results for size[4] and size [5] when we evaluate index 3. This index is located in a valley which means that solutions for small window sizes will occur both left and right from this index. Therefore this index might only be possibly involved as a solution to larger window sizes.

To get the final result we run through the partial solution array starting from the back. Each blank get’s replaced by the previous larger window size, which gives us :

Solution : [ 6 , 5 , 3 , 3 , 3 , 1 ]

Let’s finish where we started and have a look how this all works on our original array.

arr = [ 1, 4, 6, 5, 3, 4, 5 ]

Solution : [ 6 , 5 , 4 , 3 , 3 , 3 , 1 ]

I hope this was helpful to decipher the O(N) code.

Of course chances are I only confused you more :D

Cheers.

+ 2 comments Javascript solution

As several people mentioned already, this is based on the least price stock problem (but this is two way)

If you are struggling (like I was), read this first: https://practice.geeksforgeeks.org/problems/stock-span-problem/0

and then: https://www.geeksforgeeks.org/find-the-maximum-of-minimums-for-every-window-size-in-a-given-array/

function riddle(arr, n) { const s = [] // Used to find previous and next smaller // Arrays to store previous and next smaller const left = [] const right = [] // Initialize elements of left[] and right[] for (let i = 0; i < n; i++) { left[i] = -1; right[i] = n; } // Fill elements of left[] (closer lower value on the left of i) for (let i = 0; i < n; i++) { while (s.length && arr[s[s.length - 1]] >= arr[i]) { s.pop() } if (s.length) { left[i] = s[s.length - 1] } s.push(i) } // Empty the stack as stack is going to be used for right[] while (s.length) { s.pop() } // Fill elements of right[] (closer lower value on the right of i) for (let i = n - 1; i >= 0; i--) { while (s.length && arr[s[s.length - 1]] >= arr[i]) { s.pop() } if (s.length) { right[i] = s[s.length - 1] } s.push(i) } // Create and initialize answer array const ans = [] for (let i = 0; i <= n; i++) { ans[i] = 0 } // Fill answer array by comparing minimums of all // lengths computed using left[] and right[] for (let i = 0; i < n; i++) { // length of the interval const len = right[i] - left[i] - 1; // arr[i] is a possible answer for this length // 'len' interval, check if arr[i] is more than // max for 'len' ans[len] = Math.max(ans[len], arr[i]); } // Some entries in ans[] may not be filled yet. Fill // them by taking values from right side of ans[] for (let i = n - 1; i >= 1; i--) { ans[i] = Math.max(ans[i], ans[i + 1]) } ans.shift() // The first 0 is useless return ans }

+ 3 comments This problem is a two-way, least price stock problem.

The canonical stock span problem can be formulated as:

Consider a stock price sampled on the kth day, denoted price[k], What is the largest i, where i < k, such that for all i <= j < k, price[j] <= price[k]? In other words, given a kth day stock price price[k],

**for how many consecutive previous days has price[k] reigned as the greatest**?For this problem, we need to solve

**two**instances of the stock span problem,**one going back in time and one going "forward" in time;**furthermore,**rather than**considering how long price[k] has been the**greatest**for, we need to consider how long price[k] has been the**smallest**for. I shall denote them problem 1 and problem 2:**Problem 1.**Consider a stock price sampled on the kth day, denoted price[k]. What is the largest i, where i < k, such that for all i <= j < k, price[j] >= price[k]? In other words, given a kth day stock price price[k],**for how many previous consecutive days has price[k] been the lowest**?**Problem 2.**Consider a stock price sampled on the kth day, denoted price[k], What is the largest m, where k < m, such that for all k <= l < m, price[k] <= price[m]? In other words, given a kth day stock price price[k],**for how many next consecutive days will price[k] have been the lowest**?Combine the results from problem 1 and 2 to determine the largest window that a given number is a minimum for. Be careful with counting when you combine the results.

+ 2 comments Here is my code in java...Passed all the test cases.....

static long[] riddle(long[] arr) { // complete the function int n=arr.length; Stack<Integer> st=new Stack<>(); int[] left=new int[n+1]; int[] right=new int[n+1]; for(int i=0;i<n;i++){ left[i]=-1; right[i]=n; } for(int i=0;i<n;i++){ while(!st.isEmpty() && arr[st.peek()]>=arr[i]) st.pop(); if(!st.isEmpty()) left[i]=st.peek(); st.push(i); } while(!st.isEmpty()){ st.pop(); } for(int i=n-1;i>=0;i--){ while(!st.isEmpty() && arr[st.peek()]>=arr[i]) st.pop(); if(!st.isEmpty()) right[i]=st.peek(); st.push(i); } long ans[] = new long[n+1]; for (int i=0; i<=n; i++) { ans[i] = 0; } for (int i=0; i<n; i++) { int len = right[i] - left[i] - 1; ans[len] = Math.max(ans[len], arr[i]); } for (int i=n-1; i>=1; i--) { ans[i] = Math.max(ans[i], ans[i+1]); } long[] res=new long[n]; for (int i=1; i<=n; i++) { res[i-1]=ans[i]; } return res; }

Sort 103 Discussions, By:

Please Login in order to post a comment