We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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.
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.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Min Max Riddle
You are viewing a single comment's thread. Return to all comments →
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) :
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.
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.
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:
Then at the end we find 2 more results for the same sizes:
So we’ll have to compare these results and only keep the maximum value of the 2:
Then at last we find 2 more results:
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.
Cheers.