Stack Code Challenge Breakdown
Holy HackerRank, Batman! I recently completed a HackerRank code challenge called Min Max Riddle. It requires the use of a data type/structure called a stack, and the riddle doesn’t end there. I had to refer to many resources before writing a working solution, and I decided to write an article about this challenge because I wanted to thoroughly understand it and offer a JavaScript algorithm resource to the world wide web.
Before we tackle the code challenge, let’s review what a stack is. In computer science, a stack is an abstract data type that serves as a collection of elements from which additions and subtractions can only be performed on the back end of the collection, or—speaking vertically—from the top of the stack. Although some programming languages provide more, when working with a stack, there are two principal operations:
- Push: add an element to the top of the stack
- Pop: remove an element from the top of the stack
Because of how elements are added or removed only from the end of the collection — or top of the stack, another terminology to represent the stack data structure is LIFO (last in, first out). Here’s a visual representation of pushing on to and popping off of a stack:
A stack is commonly represented by an Array, which has a .push() and .pop() method in JavaScript and many other programming languages. An example of using an Array as a stack in JavaScript could look like this:
const stack = [1, 2, 3]stack.push(4)
// [1, 2, 3, 4]stack.push(5)
// [1, 2, 3, 4, 5]stack.pop()
// [1, 2, 3, 4]stack.pop()
// [1, 2, 3]
Min Max Riddle:
Problem Statement:
Given an Array of positive integers, use a series of sliding windows to collect the minimum value of each window, then record the maximum value of the collected minima for that window size. The window size varies from 1 to n wherein n is equal to the size, i.e. length, of the input Array. For example:
const arr = [3, 5, 4, 7, 6, 2] // consider window sizes 1 to n = arr.length = 6
// wSize1 => [3] [5] [4] [7] [6] [2]
// wSize2 => [3, 5] [5, 4] [4, 7] [7, 6] [6, 2]
// ...
// wSize6 => [3, 5, 4, 7, 6, 2]____________________________________________________________________
| window | * collected minima * | window | * |
| size | w1 | w2 | w3 | w4 | w5 | w6 | maximum | * |
|––––––––––|–––––––––––––––––––––––––––––––––––––––––|–––––––––|–––|
| 1 | 3 | 5 | 4 | 7 | 6 | 2 | 7 | c |
|––––––––––|––––––|––––––|––––––|––––––|––––––|––––––|–––––––––| o |
| 2 | 3 | 4 | 4 | 6 | 2 | | 6 | l |
|––––––––––|––––––|––––––|––––––|––––––|––––––|––––––|–––––––––| l |
| 3 | 3 | 4 | 4 | 2 | | | 4 | . |
|––––––––––|––––––|––––––|––––––|––––––|––––––|––––––|–––––––––| m |
| 4 | 3 | 4 | 2 | | | | 4 | a |
|––––––––––|––––––|––––––|––––––|––––––|––––––|––––––|–––––––––| x |
| 5 | 3 | 2 | | | | | 3 | i |
|––––––––––|––––––|––––––|––––––|––––––|––––––|––––––|–––––––––| m |
| 6 | 2 | | | | | | 2 | a |
––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––// maxima of minima = [7, 6, 4, 4, 3, 2]
Function Description:
The riddle() function must return an Array of integers representing the maximum minimum value for each window of size 1 to n.
Input parameter:
arr: anArrayof integers
Solution:
The algorithm to solve this challenge has a lot going on, but don’t worry, I’m just as confused as you might be. The gist is this:
- Use a
for loop,while loop, and stackArrayto build a hashmap of window maxima. - Use a
for loopto build a hashmap of inverted window maxima. - Use a
for loop,if elsestatement, and inverted window maxima hashmap to collect window maxima in anArray. - Return a reversed copy of the maxima
Array.
Step 0: Outline Function
function riddle(arr) {
const wMaxes = {}
const wInver = {}
const stack = []
const maxima = []
const result return result
}
We start by outlining the function riddle() with its included parameter arr. We know from the outline that we’ll need two Object to use as hashmaps: wMaxes for the first hashmap of window maxima, and wInver for the second hashmap of inverted window maxima. We know we need two Array: stack to use as a stack, and maxima to contain values from the inverted window maxima hashmap. We know we need to create a reversed copy of the maxima Array values, so we’ll declare the reserved variable result, ultimately using it as the return value.
Step 1: Build Window Maxima Hashmap
function riddle(arr) {
const wMaxes = {}
const wInver = {}
const stack = []
const maxima = [] arr.push(0) for (let i = 0; i < arr.length; i++) {
let idx = i while (stack.length && stack[stack.length - 1][0] >= arr[i]) {
let [val, prevIdx] = stack.pop() wMaxes[arr[i]] = Math.max(
wMaxes[arr[i]] || 0, i - prevIdx + 1
)
wMaxes[val] = Math.max(wMaxes[val] || 0, i - prevIdx)
idx = prevIdx
}
stack.push([arr[i], idx])
} delete wMaxes['0'] const result return result
}
The first thing to notice is the first line of active code: arr.push(0). By adding a 0 to the end of the input array we can efficiently create an extra iteration of the for loop and force the while loop to evaluate any remaining content of the stack. We’ll come back to this.
The for loop evaluates each element of arr. The variable idx is assigned the index of the current element. If stack is empty, as it will be on the first iteration, or the value on the top of stack is less than the current element, the while loop is skipped and a sub-Array containing the current element and its index is pushed on to stack. Note that idx is mutable.
If stack is not empty and the value on the top of stack is greater than or equal to the current element, the while loop is triggered, and this is where wMaxes is built.
stack.pop() removes the sub-Array from the top of stack. Destructuring assignment is used to assign the element to the variable val and the index to the variable prevIdx.
Next, two bracket notation operations are performed to add entries to wMaxes. In the first, an entry is made with a key equal to the current element (wMaxes[arr[i]]) and a value equal to the greater of: the current value of wMaxes[arr[i]], if it exists, or the value of the current index minus the previous index plus one (i — prevIdx + 1). In the second, an entry is made with a key equal to the last element on top of stack, or previous qualifying element (wMaxes[val]), and a value equal to the greater of: the current value of wMaxes[val], if it exists, or the value of the current index minus the previous index (i — prevIdx).
Note that the Logical OR operator (||) within each Math.Max() function sets the first argument to 0 if an entry with the specified key does not yet exist in wMaxes. This is a shorthand way to create a default entry with the second argument, the calculated index, as the value if the key does not yet exist in wMaxes.
The last operation within the while loop is to set the variable idx, in the for loop scope, to the index from the previous element popped off the top of stack. Note that the calculation for wMaxes[arr[i]] considers i — prevIdx + 1 to accommodate the difference of iteration beginning at 0 and window size beginning at 1.
So, what on earth is going on here? In short, we’re creating a hashmap—wMaxes—which stores key value pairs as ‘arr element': ‘window size' wherein ‘arr element’ is an element from the arr which represents the maximum value of the collected minima of ‘window size’. Consider this example:
const arr = [3, 5, 4, 7, 6, 2]wMaxes => {'0': 7, '2': 6, '3': 5, '4': 4, '5': 1, '6': 2, '7': 1}____________________________________________________________________
| window | * collected minima * | window | * |
| size | w1 | w2 | w3 | w4 | w5 | w6 | maximum | * |
|––––––––––|–––––––––––––––––––––––––––––––––––––––––|–––––––––|–––|
| 2 | 3 | 4 | 4 | 6 | 2 | | 6 | m |
|––––––––––|––––––|––––––|––––––|––––––|––––––|––––––|–––––––––| a |
| 5 | 3 | 2 | | | | | 3 | x |
––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
How the stack data structure plays a key role here is that it stores, in linear order, data that has come previous to the currently evaluated data. The end of this article will include a nifty process log to demonstrate how the data is being manipulated throughout the function, but consider this process log from the third iteration of the for loop, evaluating arr[2] // 4:
const arr = [3, 5, 4, 7, 6, 2]loop #3
current element: 4
stack: [[3, 0], [5, 1]]
while loop
element on top of stack(5) is >= current element(4)
stack.pop(): [5, 1]
load window maxes map
build or update key:value with curEl(4) as key
set value to max of existing key(set to 0)
or index - last index + 1: 2
wMaxes: {'4': 2} build or update key:value with lastEl(5) as key
set value to max of existing key(set to 0)
or index - last index: 1
wMaxes: {'4': 2, '5': 1} change curIdx from 2 to 1 push [4, 1] (curEl, curIdx) on top of stack
stack: [[ 3, 0 ], [ 4, 1 ]]
This shows us that, if each element in arr is greater than the last, it is added to the stack for future calculations, and once we reach an element in arr that is less than the last, we can start evaluating some results with the data we have so far; expanding the window, so to speak, back to the previous element. The act of expanding the window back is also controlled by setting idx to the prevIdx from the last sub-Array at the top of stack, assigning that index to the next sub-Array to be pushed on to stack, preparing the next iteration of the for loop.
In the process log of loop #3, we can evaluate the current element: 4, and add it to wMaxes with window size 2 since, so far:
minimum of [3, 5] = 3
minimum of [5, 4] = 4
maximum of 3, 4 = 4
wMaxes['4'] = 2 // {'4': 2}Then, we can peek back at the previous element: 5, via stack, and add it to wMaxes with window size 1 since, so far:
minimum of [3] = 3
minimum of [5] = 5
minimum of [4] = 4
maximum of 3, 5, 4 = 5
wMaxes['5'] = 1 // {'5': 1}The 0 that was added to arr at the top of the riddle() function will force the while loop to process any remaining sub-Array in stack upon the last iteration of the for loop, and appropriately adjust the maximum window sizes recorded in the wMaxes hashmap.
The last process for this step is optional, but I’ve included it to remove extraneous code. After wMaxes is built, it will include a key of ‘0’ due to the final iteration of the for loop. If left, this key will just be ignored in next steps, but we can clean up the code by deleting the key value pair from wMaxes with delete wMaxes[‘0’].
Step 2: Build Inverted Window Maxima Hashmap
function riddle(arr) {
const wMaxes = {}
const wInver = {}
const stack = []
const maxima = [] arr.push(0) for (let i = 0; i < arr.length; i++) {
let idx = i while (stack.length && stack[stack.length - 1][0] >= arr[i]) {
let [val, prevIdx] = stack.pop() wMaxes[arr[i]] = Math.max(
wMaxes[arr[i]] || 0, i - prevIdx + 1
)
wMaxes[val] = Math.max(wMaxes[val] || 0, i - prevIdx)
idx = prevIdx
}
stack.push([arr[i], idx])
} delete wMaxes['0'] for (let k in wMaxes) {
wInver[wMaxes[k]] = Math.max(wInver[wMaxes[k]] || 0, k)
} const result return result
}
To more easily build our forthcoming maxima Array, we can invert the key value pairs of wMaxes and assign them to the wInver hashmap. This step will also handle needed amendments to the window size maxima. Consider this:
const arr = [3, 5, 4, 7, 6, 2]wMaxes = {'2': 6, '3': 5, '4': 4, '5': 1, '6': 2, '7': 1}
Because of the order of operations conducted in building wMaxes, multiple values can be assigned to the same window size. Illustrated above: ‘5’ and ‘7’ are both assigned as maximums of window size 1. There can be only one maximum, so we favor the greater of the two values: ‘7’.
Quite simply, the for loop iterates through the keys (k) of wMaxes and uses bracket notation to add entries to wInver with a key equal to the value of wMaxes[k], and a value equal to the greater of: the current value of wInver[wMaxes[k]], if it exists, or the value of the current key: k. Our example will provide this transformation:
const arr = [3, 5, 4, 7, 6, 2]wMaxes = {'2': 6, '3': 5, '4': 4, '5': 1, '6': 2, '7': 1}wInver = {'1': 7, '2': 6, '4': 4, '5': 3, '6': 2}
Step 3: Build Maxima Array
function riddle(arr) {
const wMaxes = {}
const wInver = {}
const stack = []
const maxima = [] arr.push(0) for (let i = 0; i < arr.length; i++) {
let idx = i while (stack.length && stack[stack.length - 1][0] >= arr[i]) {
let [val, prevIdx] = stack.pop() wMaxes[arr[i]] = Math.max(
wMaxes[arr[i]] || 0, i - prevIdx + 1
)
wMaxes[val] = Math.max(wMaxes[val] || 0, i - prevIdx)
idx = prevIdx
}
stack.push([arr[i], idx])
} delete wMaxes['0'] for (let k in wMaxes) {
wInver[wMaxes[k]] = Math.max(wInver[wMaxes[k]] || 0, k)
} maxima.push(wInver[arr.length - 1]) for (let i = arr.length - 2; i > 0; i--) {
if (!wInver[i] || wInver[i] < maxima[maxima.length - 1]) {
maxima.push(maxima[maxima.length - 1])
} else {
maxima.push(wInver[i])
}
}
const result return result
}
This step begins by pushing a value into the maxima Array: the window maxima which correlates to the largest window size, or n: the size/length of arr. Bracket notation is used to access the window maximum value from wInver with a key of arr.length — 1, which considers the extra element—0—which was previously added to arr.
Next, the for loop traverses arr in reverse, using a decrementing index based on arr.length, which evaluates the maximum for window sizes n to 1 by referencing the wInver hashmap. Since we preload the maxima Array with wInver[arr.length — 1], the for loop begins with a counter set to arr.length — 2.
Within the for loop, an if else statement evaluates each value of wInver accessed by the key of the current index (i). If wInver does not include the key, or the accessed value is less than the last element of maxima, the last element of maxima is added to maxima—repeated. Otherwise (but, principally, if the accessed value is greater than the last element of maxima), the accessed value is added, or *pushed on, to maxima. Note that maxima is being used as a stack, only referencing the end, or top, of the stack, and only pushing elements on top of the stack.
This step seems a bit mysterious, but its purpose and benefit is that it can properly use the values we collected in wInver, properly sequence the window maxima to correlate with window size, and easily produce correct values when repeated window minima are encountered. The minutia can be explored in the process log, but consider this transformation and recall the chart from the problem statement:
const arr = [3, 5, 4, 7, 6, 2]wMaxes = {'2': 6, '3': 5, '4': 4, '5': 1, '6': 2, '7': 1}wInver = {'1': 7, '2': 6, '4': 4, '5': 3, '6': 2}maxima = [2, 3, 4, 4, 6, 7]
Step 4: Reverse Maxima Array and Return
// complete solutionfunction riddle(arr) {
const wMaxes = {}
const wInver = {}
const stack = []
const maxima = [] arr.push(0) for (let i = 0; i < arr.length; i++) {
let idx = i while (stack.length && stack[stack.length - 1][0] >= arr[i]) {
let [val, prevIdx] = stack.pop() wMaxes[arr[i]] = Math.max(
wMaxes[arr[i]] || 0, i - prevIdx + 1
)
wMaxes[val] = Math.max(wMaxes[val] || 0, i - prevIdx)
idx = prevIdx
}
stack.push([arr[i], idx])
} delete wMaxes['0'] for (let k in wMaxes) {
wInver[wMaxes[k]] = Math.max(wInver[wMaxes[k]] || 0, k)
} maxima.push(wInver[arr.length - 1]) for (let i = arr.length - 2; i > 0; i--) {
if (!wInver[i] || wInver[i] < maxima[maxima.length - 1]) {
maxima.push(maxima[maxima.length - 1])
} else {
maxima.push(wInver[i])
}
}
const result = maxima.reverse() return result
}
The one last thing to address is the order of the maxima Array. While all of our work so far required a certain order, the resulting maxima Array is in reverse order from what the function description dictates. Recall that while building the maxima Array, arr was traversed from the end (largest window size) to beginning (smallest window size). However, the function description explains that the riddle() function must return an Array of integers representing the maximum minimum value for each window of size 1 to n, or beginning to end.
This operation is easily achievable by many means, e.g. a for loop or a convenient built-in like .reverse(), which the test cases on HackerRank did not mind the use of. To properly compile our result, we assign maxima.reverse() to a reserved variable, in our case result, and then return it.
const arr = [3, 5, 4, 7, 6, 2]riddle(arr)// [7, 6, 4, 4, 3, 2]
I’m not the most experienced coder or mathematician, but I feel even Batman would be hard pressed to out-do the Riddler with a puzzle like Min Max Riddle! As noted previously, I’ve included a nifty process log of the riddle() function for you to more deeply analyze the code mechanics. There may be a better solution to this challenge, but, now, there’s a decent, correct, thoroughly analyzed, JavaScript solution for others to reference. Nanana 🦇!
github.com/dangrammer
linked.com/in/danieljromans
danromans.com
Process Log:
const arr = [3, 5, 4, 7, 6, 2]riddle(arr)// LOG /////////////////////////////////////////////////////////////arr input
[ 3, 5, 4, 7, 6, 2 ]add 0 to end of arr
[ 3, 5, 4, 7, 6, 2, 0 ]
______________________________________________________________
first for loop: build window maxes map loop #1
current element, index: 3, 0
stack: []
stack empty
push [3, 0] on top of stack
stack: [ [ 3, 0 ] ] loop #2
current element, index: 5, 1
stack: [ [ 3, 0 ] ]
element on top of stack(3) is < current element(5)
push [5, 1] on top of stack
stack: [ [ 3, 0 ], [ 5, 1 ] ] loop #3
current element, index: 4, 2
stack: [ [ 3, 0 ], [ 5, 1 ] ] while loop
element on top of stack (5) is >= current element: 4
stack.pop(): [ 5, 1 ]
load window maxes map
build or update key:value with curEl(4) as key
set value to max of [no key](0)
or [index - last index + 1](2)
wMaxes: { '4': 2 }
build or update key:value with prevEl(5) as key
set value to max of [no key](0)
or [index - last index](1)
wMaxes: { '4': 2, '5': 1 }
change curIdx from 2 to 1 push [4, 1] on top of stack
stack: [ [ 3, 0 ], [ 4, 1 ] ] loop #4
current element, index: 7, 3
stack: [ [ 3, 0 ], [ 4, 1 ] ]
element on top of stack(4) is < current element(7)
push [7, 3] on top of stack
stack: [ [ 3, 0 ], [ 4, 1 ], [ 7, 3 ] ] loop #5
current element, index: 6, 4
stack: [ [ 3, 0 ], [ 4, 1 ], [ 7, 3 ] ] while loop
element on top of stack (7) is >= current element: 6
stack.pop(): [ 7, 3 ]
load window maxes map
build or update key:value with curEl(6) as key
set value to max of [no key](0)
or [index - last index + 1](2)
wMaxes: { '4': 2, '5': 1, '6': 2 }
build or update key:value with prevEl(7) as key
set value to max of [no key](0)
or [index - last index](1)
wMaxes: { '4': 2, '5': 1, '6': 2, '7': 1 }
change curIdx from 4 to 3 push [6, 3] on top of stack
stack: [ [ 3, 0 ], [ 4, 1 ], [ 6, 3 ] ] loop #6
current element, index: 2, 5
stack: [ [ 3, 0 ], [ 4, 1 ], [ 6, 3 ] ] while loop
element on top of stack (6) is >= current element: 2
stack.pop(): [ 6, 3 ]
load window maxes map
build or update key:value with curEl(2) as key
set value to max of [no key](0)
or [index - last index + 1](3)
wMaxes: { '2': 3, '4': 2, '5': 1, '6': 2, '7': 1 }
build or update key:value with prevEl(6) as key
set value to max of existing key(2)
or [index - last index](2)
wMaxes: { '2': 3, '4': 2, '5': 1, '6': 2, '7': 1 }
change curIdx from 5 to 3 while loop
element on top of stack (4) is >= current element: 2
stack.pop(): [ 4, 1 ]
load window maxes map
build or update key:value with curEl(2) as key
set value to max of existing key(3)
or [index - last index + 1](5)
wMaxes: { '2': 5, '4': 2, '5': 1, '6': 2, '7': 1 }
build or update key:value with prevEl(4) as key
set value to max of existing key(2)
or [index - last index](4)
wMaxes: { '2': 5, '4': 4, '5': 1, '6': 2, '7': 1 }
change curIdx from 3 to 1 while loop
element on top of stack (3) is >= current element: 2
stack.pop(): [ 3, 0 ]
load window maxes map
build or update key:value with curEl(2) as key
set value to max of existing key(5)
or [index - last index + 1](6)
wMaxes: { '2': 6, '4': 4, '5': 1, '6': 2, '7': 1 }
build or update key:value with prevEl(3) as key
set value to max of [no key](0)
or [index - last index](5)
wMaxes: { '2': 6, '3': 5, '4': 4, '5': 1, '6': 2, '7': 1 }
change curIdx from 1 to 0 push [2, 0] on top of stack
stack: [ [ 2, 0 ] ] loop #7
current element, index: 0, 6
stack: [ [ 2, 0 ] ] while loop
element on top of stack (2) is >= current element: 0
stack.pop(): [ 2, 0 ]
load window maxes map
build or update key:value with curEl(0) as key
set value to max of [no key](0)
or [index - last index + 1](7)
wMaxes: { '0': 7, '2': 6, '3': 5, '4': 4, '5': 1, '6': 2, '7': 1 }
build or update key:value with prevEl(2) as key
set value to max of existing key(6)
or [index - last index](6)
wMaxes: { '0': 7, '2': 6, '3': 5, '4': 4, '5': 1, '6': 2, '7': 1 }
change curIdx from 6 to 0 push [0, 0] on top of stack
stack: [ [ 0, 0 ] ]______________________________________________________________
window maxes map (wMaxes)
{ '0': 7, '2': 6, '3': 5, '4': 4, '5': 1, '6': 2, '7': 1 }remove 0 key from wMaxes
{ '2': 6, '3': 5, '4': 4, '5': 1, '6': 2, '7': 1 }______________________________________________________________
second for loop: create inverted window maxes map loop #1
current key: 2
add key(wMaxes[2]) to wInver: 6
set value for wInver key(6) to the greater of:
[wInver[wMaxes[2]] || 0](0) & current key(2)
{ '6': 2 } loop #2
current key: 3
add key(wMaxes[3]) to wInver: 5
set value for wInver key(5) to the greater of:
[wInver[wMaxes[3]] || 0](0) & current key(3)
{ '5': 3, '6': 2 } loop #3
current key: 4
add key(wMaxes[4]) to wInver: 4
set value for wInver key(4) to the greater of:
[wInver[wMaxes[4]] || 0](0) & current key(4)
{ '4': 4, '5': 3, '6': 2 } loop #4
current key: 5
add key(wMaxes[5]) to wInver: 1
set value for wInver key(1) to the greater of:
[wInver[wMaxes[5]] || 0](0) & current key(5)
{ '1': 5, '4': 4, '5': 3, '6': 2 } loop #5
current key: 6
add key(wMaxes[6]) to wInver: 2
set value for wInver key(2) to the greater of:
[wInver[wMaxes[6]] || 0](0) & current key(6)
{ '1': 5, '2': 6, '4': 4, '5': 3, '6': 2 } loop #6
current key: 7
add key(wMaxes[7]) to wInver: 1
set value for wInver key(1) to the greater of:
[wInver[wMaxes[7]] || 0](5) & current key(7)
{ '1': 7, '2': 6, '4': 4, '5': 3, '6': 2 }______________________________________________________________
inverted window maxes map (wInver)
{ '1': 7, '2': 6, '4': 4, '5': 3, '6': 2 }load maxima arr with value from wInver[6(last index of input arr)]
[ 2 ]______________________________________________________________
third for loop: create maxima arr loop #1
the value of wInver[5](3) is >= the last element of maxima(2)
so add new value
[ 2, 3 ] loop #2
the value of wInver[4](4) is >= the last element of maxima(3)
so add new value
[ 2, 3, 4 ] loop #3
wInver has no key of 3 so repeat last element
[ 2, 3, 4, 4 ] loop #4
the value of wInver[2](6) is >= the last element of maxima(4)
so add new value
[ 2, 3, 4, 4, 6 ] loop #5
the value of wInver[1](7) is >= the last element of maxima(6)
so add new value
[ 2, 3, 4, 4, 6, 7 ]______________________________________________________________
reverse the maxima arr and assign it to result arr
print result arr
[ 7, 6, 4, 4, 3, 2 ]
