Monotonic Stack

A monotonic stack is a concept of maintaining either increasing or decreasing elements in the stack to solve many problems. In general, the following is an approach to filling the stack.

1. Initialize stack = []
2. If empty then simply push a new element
3. Otherwise, compare the top element with the incoming item and make sure that order is maintained. If violation then remove the top element. Keep performing this check until the new item is safe to add.

Monotonic stacks are used to calculate the previous smaller element and the next smaller element in linear time complexity.

496. Next Greater Element I

https://leetcode.com/problems/next-greater-element-i/description/

Problem

You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2.

For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1.

Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.

Example

Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
- 4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
- 1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3.
- 2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.

Bruteforce approach

The brute force approach would be the first iterate i then for each i run another loop j=i+1,....n-1 to find out the next greater element for i . This would be O(n*n) .

Using monotonic stack

Intuitively, we can observe that if numbers are in decreasing order then none of the elem will have the next greater elem.

nums = [15,10,8,6,4] 
ans = [-1,-1,-1,-1]

The first number which breaks the decreasing order becomes the answer for the last number.

nums = [15,10,8,6,4,5] 
ans = [-1,-1,-1,5,-1]

But the first number can also be large enough to become the next greater element for many numbers.

nums = [15,10,8,6,4,11] 
ans = [-1,11,11,11,-1]

It means we can maintain the monotonic decreasing stack. If a new number doesn’t break the order then add it. Otherwise new number can be used as answer for all elements lesser than the new number.

Based on this logic, we can write the following code to solve this problem.

var nextGreaterElement = function (nums1, nums2) {
    const m = nums1.length;
    const n = nums2.length;
    const map = new Map();
    // Maintain decreasing stack
    const stack = [];
    for (let i = 0; i < n; i++) {
        const num = nums2[i];
        // Check for violation
        while (stack.length > 0 && stack[stack.length - 1] < num) {
            // At this time num will be the next greater elem fo top
            map.set(stack.pop(), num);
        }
        stack.push(num);
    }
    // Now build the final answer
    return nums1.map(x => map.has(x) ? map.get(x) : -1);
};

503. Next Greater Element II

https://leetcode.com/problems/next-greater-element-ii/description/

Problem

For a given circular array, we need to find out the next greater element. Following is one example.

nums = [1, 2, 1]
ans =  [2, -1, 2]

Approach

Based on the previous problem, we can now try to apply the monotonic stack to solve this problem as well. But this problem has two unique properties.

1. The value of the array can be duplicated. To handle this, instead of storing value in the stack, we can store the index of the element.
2. The circular nature of the array. To handle this, we can simply run the algorithm twice.

Following is code to solve this problem using a decreasing monotonic stack.

var nextGreaterElements = function (nums) {
    // Use monotonic decreasing stack, since nums can have duplicate values therefore will store index.
    const stack = [];
    const n = nums.length;
    const ans = new Array(n).fill(-1);
    // Run two pass to handle the circular nature
    for (let pass = 0; pass < 2; pass++) {
        for (let i = 0; i < n; i++) {
            // handle violation for monotonic decreasing stack
            while (stack.length > 0 && nums[stack[stack.length - 1]] < nums[i]) {
                ans[stack.pop()] = nums[i]
            }
            stack.push(i);
        }
    }
    return ans;
};

739. Daily Temperatures

https://leetcode.com/problems/daily-temperatures/description/

Problem

How many days need to wait to get the warmer temperature?

For example temperature=[73,74,75,71,69,72,76,73] , 73 needs to wait for 1 day to get the next higher temperature 74 . Similarly, 74 needs to wait for 1 day to get the next higher temperature 75 . But 75 will have to wait for 4 days to get the next highest temperature 76 . So the answer would be [1,1,4,2,1,1,0,0]

Approach# Using monotonic stack

Based on the previously solved problem, we can see that here as well need to find out the next higher number. I.e. we can use the monotonic decreasing stack to find out the next higher temperature and find the distance. Since temperature can be duplicates therefore we will be storing an index that can also be used to calculate the distance. Following would be the code.

var dailyTemperatures = function(T) {
    const n = T.length;
    // Monotonic decreasing stack
    const stack = [];
    const ans = new Array(n).fill(0);
    for (let i=0; i < n; i++) {
        // On violation, pop the element and also calulcate the answer
        while(stack.length > 0 && T[stack[stack.length-1]] < T[i]) {
            const index = stack.pop();
            ans[stack.pop()] = i - index;
        }
        stack.push(i);
    }
    return ans;
};

1762. Buildings With an Ocean View

https://leetcode.com/problems/buildings-with-an-ocean-view/description/

There are n buildings in a line. You are given an integer array heights of size n that represents the heights of the buildings in the line.

The ocean is to the right of the buildings. A building has an ocean view if the building can see the ocean without obstructions. Formally, a building has an ocean view if all the buildings to its right have a smaller height.

Return a list of indices (0-indexed) of buildings that have an ocean view, sorted in increasing order.

Example 1:

Input: heights = [4,2,3,1]
Output: [0,2,3]
Explanation: Building 1 (0-indexed) does not have an ocean view because building 2 is taller.

Approach

1. We can use monotonic increasing stack to keep track of buildings not having ocean view.
2. Add a new building if it’s height is greater than the top stack’s height.
3. Otherwise don’t add.
4. At the end, stack will have answer in reverse order.

Following is code for reference.

/**
 * @param {number[]} heights
 * @return {number[]}
 */
var findBuildings = function (heights) {
    const n = heights.length;
    const stack = [];
    for (let i = n - 1; i >= 0; i--) {
        const height = heights[i];
        if (stack.length === 0 || height > heights[stack[stack.length - 1]]) {
            stack.push(i);
        }
    }
    return stack.reverse();
};

84. Largest Rectangle in Histogram

https://leetcode.com/problems/largest-rectangle-in-histogram/description/

Problem

Return the area of the largest rectangle in the histogram.

For the above example, 5*2=10 is the largest rectangle.

Approach# 1: Using brute force

We can apply two loops, first to track the left-most rectangle and then second to track all possible rightmost rectangles and calculate the area.

var largestRectangleArea = function(heights) {
    const n = heights.length;
    let ans = 0;
    for (let i=0; i < n; i++) {
        let height = heights[i]; // Track the min height
        for (let j=i; j < n; j++) {
            const width = j - i + 1;
            height = Math.min(height, heights[j]);
            ans = Math.max(ans, width * height); // Update global ans
        }
    }
    return ans;
};

Approach#2: Using a monotonic stack

Following are a few observations that give an intuition to use a monotonic increasing stack to track the height.

1. If we know that all rectangles are in increasing order then only the width of the lower height bar will be increased to cover the overlapped area with the higher bar.
2. If the height is in increasing order then we can start calculating areas from right to left for each bar and overlap with larger bar.
3. This gives an idea to use the monotonic increasing stack.
4. Also, we can add bar with 0 height in the beginning and at the end to keep the logic simple.

TLDR; Goal is to maintain the monotonic increasing stack and on violation, perform the calculation to find the local answer.

Following is code to implement this logic.

var largestRectangleArea = function(heights) {
    
    // Increasing monotonic stack
    const stack = [];
    // Add 0 at the beginning and end to simplify the calculation
    heights.unshift(0);
    heights.push(0);
    const n = heights.length;
    let ans = 0;
    for (let i=0; i < n; i++) {
        // Increasing monotonic stack violation check
        while(stack.length > 0 && heights[i] < heights[stack[stack.length -1]]) {
            // Local ans calculation
            const height = heights[stack.pop()];
            const width = i - stack[stack.length-1] - 1;
            ans = Math.max(ans, height * width); // Update global ans
        }
        stack.push(i);
    }
    return ans;
};

581. Shortest Unsorted Continuous Subarray

https://leetcode.com/problems/shortest-unsorted-continuous-subarray/description/

Given an integer array nums, you need to find one continuous subarray such that if you only sort this subarray in non-decreasing order, then the whole array will be sorted in non-decreasing order.

Return the shortest such subarray and output its length.

Example 1:

Input: nums = [2,6,4,8,10,9,15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.

Approach

Using Selection sort

The following would be the approach to apply the selection sort approach to solve this problem.

1. Iterate each nums[i] of the array and try to determine it’s correct position in the sorted array.
2. Compare nums[i] with every nums[j] , here i<j<n
3. If nums[j] < nums[i] it means both are not in their correct position.
4. Instead of swapping (as per selection sort), we will track the value of i and j as a possible boundary of the unsorted subarray (i,j) which needs to be sorted.
5. Out of all possible chosen nums[i] , the lowest index l will the lower boundary of the subarray, similarly out of all possible chosen nums[j] , the highest index r will be the highest boundary of the subarray which needs sorting.

Following is the code to implement this logic.

const usingSelectionSort = nums =>{
    const n = nums.length;
    let l = n, r=0;
    for (let i=0; i < n; i++) {
        for (let j=i+1; j < n; j++) {
            if(nums[j] < nums[i]) {
                l = Math.min(l, i);
                r = Math.max(r, j);
            }
        }
    }
    return r - l < 0 ? 0 : r - l + 1;
}

The time complexity of this code is O(n*n).

Observations

1. l once set first doesn’t get updated again. This is because we are traversing from left to right and first, nums[j]<nums[i] will set the value of i will stay as the minimum value for l .
2. Only the value of r will be keep updating every time we see nums[j]<nums[i] .

Improve Selection sort using a monotonic stack

1. The selection sort approach tries to find out the lowest value of l which would be the position to insert the next upset smallest number.
2. It means we can use a monotonic increasing stack and keep track of the lowest l if the new number is upsetting the order.
3. Similarly, we can run the second pass from right to left using a monotonic decreasing stack and keep track of the maximum r if the new number is upsetting the order.

Following is code to improve the selection sort logic using two-pass monotonic stacks.

const usingMonotonicStack = nums => {
    const n = nums.length;
    // Pass1 to use monotonic increasing stack to track the minimum left index needs sorting
    let left = n;
    const stack = [];
    for (let i = 0; i < n; i++) { // left to right
        while (stack.length > 0 && nums[i] < nums[stack[stack.length - 1]]) {
            left = Math.min(left, stack.pop())
        }
        stack.push(i);
    }
    // Pass 2 to use monotonic decreasing stack to track the max right index needs sorting
    let right = 0;
    stack.length = 0; // reset stack
    for (let i = n - 1; i >= 0; i--) { // right to left
        while (stack.length > 0 && nums[i] > nums[stack[stack.length - 1]]) {
            right = Math.max(right, stack.pop());
        }
        stack.push(i);
    }
    return right - left > 0 ? right - left + 1 : 0;
}

901. Online Stock Span

https://leetcode.com/problems/online-stock-span/description/

Problem

Design an algorithm that collects daily price quotes for some stock and returns the span of that stock’s price for the current day.

The span of the stock’s price in one day is the maximum number of consecutive days (starting from that day and going backward) for which the stock price was less than or equal to the price of that day.

• For example, if the prices of the stock in the last four days is [7,2,1,2] and the price of the stock today is 2, then the span of today is 4 because starting from today, the price of the stock was less than or equal 2 for 4 consecutive days.
• Also, if the prices of the stock in the last four days is [7,34,1,2] and the price of the stock today is 8, then the span of today is 3 because starting from today, the price of the stock was less than or equal 8 for 3 consecutive days.

Implement the StockSpanner class:

• StockSpanner() Initializes the object of the class.
• int next(int price) Returns the span of the stock's price given that today's price is price.

Example 1:

Input
["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
[[], [100], [80], [60], [70], [60], [75], [85]]
Output
[null, 1, 1, 1, 2, 1, 4, 6]

Explanation
StockSpanner stockSpanner = new StockSpanner();
stockSpanner.next(100); // return 1
stockSpanner.next(80);  // return 1
stockSpanner.next(60);  // return 1
stockSpanner.next(70);  // return 2
stockSpanner.next(60);  // return 1
stockSpanner.next(75);  // return 4, because the last 4 prices (including today's price of 75) were less than or equal to today's price.
stockSpanner.next(85);  // return 6

Approach# Using Monotonic stack

Generally, during violation of monotonic, we calculate the answer. In this problem, we want to know how many previous stock prices were less than or equal to the current price. It means we should use a monotonic decreasing stack so that all the increasing patterns will be popped if a bigger number comes.

How to calculate the answer?

On violation of decreasing stack, we can sum the span for each popped-out stock price. It means along with stock price we will also have to store the span answer.

Following is code to implement this logic.

var StockSpanner = function() {
    // Monotonic decreasing stack
    this.stack = [];
};

StockSpanner.prototype.next = function(price) {
    let ans = 1;
    // On violation
    while(this.stack.length > 0 && this.stack[this.stack.length-1][0] <= price) {
        const [x,y] = this.stack.pop();
        ans +=y;
    }
    this.stack.push([price, ans]);
    return ans;
};

132 Pattern

https://leetcode.com/problems/132-pattern/description/

Problem

Given an array of n integers nums, a 132 pattern is a subsequence of three integers nums[i], nums[j] and nums[k] such that i < j < k and nums[i] < nums[k] < nums[j].

Return true if there is a 132 pattern in nums, otherwise, return false.

Example 1:

Input: nums = [1,2,3,4]
Output: false
Explanation: There is no 132 pattern in the sequence.

Approach# 1: Using brute force

We can apply three for loop each for i , j and k and if the condition satisfies then return true. Following is brute force code.

const usingBruteforce = nums => {
    // This with O(n^3) throws TLE
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            for (let k = j + 1; k < n; k++) {
                const a = nums[i];
                const b = nums[j];
                const c = nums[k];
                if (a < c && c < b) {
                    return true;
                }
            }
        }
    }
    return false;
}

Approach #2: Using min finding

Thinking a little bit, we can notice that if we just have to solve nums[i] < nums[j] then we don’t need two loops. We can find it using a single loop by keeping track of the last minimum value as below.

    const n = nums.length;
    let min = nums[0];
    for (let j = 1; j < n; j++) {
        min = Math.min(min, nums[j]);
        if (min === nums[j]) {
            continue;
        }
    }

Since we could find ith and jth in a single loop, so now we can apply a second loop to iterate k to find out the triplet answer as below.

const usingMinFinding = nums => {
    // This with O(n^2) also throws TLE
    const n = nums.length;
    let min = nums[0];
    for (let j = 1; j < n; j++) {
        min = Math.min(min, nums[j]);
        if (min === nums[j]) {
            continue;
        }
        // We found ith and jth sunch that nums[i] (min) < nums[j], now search for kth
        for (let k = j + 1; k < n; k++) {
            if (min < nums[k] && nums[k] < nums[j]) {
                return true;
            }
        }
    }
    return false;
}

Approach #3: Optimize using a Monotonic stack

We found out ith and jth in O(n) which satisfy nums[i]<nums[j]. We can store this result in a separate array for each j . We can then use a monotonic decreasing stack to hold the values for kth . If nums[i] < nums[k] doesn’t hold then keep popping out from the stack.

Following is code using a monotonic stack.

const usingMonotonicStack = nums => {
    const n = nums.length;
    if( n < 3) {
        return false;
    }
    // min holds values for ith
    const min = new Array(n).fill(0);
    min[0] = nums[0];
    for (let i=1; i < n; i++) {
        min[i] = Math.min(min[i-1], nums[i]);
    }
    // stack holds values for kth in decreasing order to maintain nums[i] < nums[k] relationship
    const stack = [];
    for (let j=n-1; j >=0; j--) {
        // make sure nums[i] < nums[j]
        if( min[j] < nums[j]) {
            while(stack.length > 0 && stack[stack.length-1] <= min[j]) {
                stack.pop();
            }
            // Now need to verify nums[k] < nums[j]
            if(stack.length > 0 && stack[stack.length-1] < nums[j]) {
                return true;
            }
            stack.push(nums[j]);
        }
    }
    return false;
}

907. Sum of Subarray Minimums

https://leetcode.com/problems/sum-of-subarray-minimums/description/

Problem

For every possible sub array of given array, find the sum of minimum value of each sub array. For array [3, 1, 2 , 4] following are possible sub arrays.

sub arrays = [3],[1],[2],[4],[3,1],[1,2],[2,4],[3,1,2],[1,2,4],[3,1,2,4]
min(sub)   =  3   1   2   4    1     1     2     1       1       1
sum = 17

Approach#1: Bruteforce approach

We can use two nested loop to generate all possible sub arrays and then find the minimum value in each sub array to sum up the total answer as below.

var sumSubarrayMins = function(arr) {
    const n = arr.length;
    let ans = 0;
    const PRIME = Math.pow(10, 9) + 7;
    for (let i=0; i < n; i++) {
        for (let j=i; j < n; j++) {
            ans = (ans + Math.min(...arr.slice(i, j + 1))) % PRIME;
        }
    }
    return ans;
};

Time complexity of this approach is O(n*n*n) which cause TLE. So we need to optimize it.

Approach#2: Better bruteforce

Instead taking slice followed by finding the min, we can calculate the running min. Following is modified code.

/**
 * @param {number[]} arr
 * @return {number}
 */
var sumSubarrayMins = function(arr) {
    const n = arr.length;
    let ans = 0;
    const PRIME = Math.pow(10, 9) + 7;
    for (let i=0; i < n; i++) {
        let min = arr[i];
        for (let j=i; j < n; j++) {
            // Each cycle represent sub array of window <i,j>
            min = Math.min(min, arr[j]); 
            ans = (ans + min) % PRIME;
        }
    }
    return ans;
};

This brings time complexity down to O(n*n) but it still throw TLE error.

Observations on this approach.

• Most of the time O(n*n) spent to find out the range of the sub array.

Can we flip it? I.e. what if we can find out in which range the given number is minimum? If we can then we can count haw many ranges the given number is minimum to calculate the ans.

Approach#3: Using a monotonic stack

Let’s say for array [0,3,4,5,2,3,4,1,4] we need to find out number of subarrays where 2 is minimum?

1. We can see that 2 is minimum in [3,4,5,2,3,4]
2. It means in all the subarray of this contains 2, 2 will still be minimum.

Q. In the given range, find the count of subarrays which contain 2?

1. This can be answer by multiplying the count of elements before (and including) 2 and the count of elements after (and including) 2.
2. There are 4 elements before (and including) 2 — [3,4,5,2]
3. There are 3 elements are after (and including) 2 — [2,3,4].
4. So the total is 3∗4=12.

Q. How to get the range in which each element is the smallest?

1. we find the nearest element on the left, which is less than itself.
2. Then, find the closest element on the right, which is less than itself.
3. If i and j are the indices of these elements on the left and right, then [i+1,j−1] indices create our range.
4. We can use a monotonic increasing stack to determine the value of i and j.
5. It means we can use monotonic increasing stack to answer this question

Edge Case — Duplicate Elements

Following is code for reference.

class Solution {
public:
    int sumSubarrayMins(vector<int>& arr) {
        /**
        - sum of min(b) where b ranges over every contiguous subarray of arr
        - Example # 1
            - arr = [3,1,2,4]
            - for num=1
            - left[1] = 2 i.e. distance of element smaller than 1
            - right[1] = 3 i.e. distance of element smaller than 1
            - Total number of subarray with num=1 as minimum = 2*3 = 6
            - {3,1}{1}{1,2}{1,2,4}{3,1,2} {3,1,2,4}
        */
        int PRIME = pow(10,9)+7;
        int n = arr.size();
        vector<int> left(n);
        vector<int> right(n);
        int ans = 0;
        stack<int> st;
        // pass#1: build left using monotonic increasing stack
        for (int i = 0; i < n; i++) {
            int num = arr[i];
            while (!st.empty() && num < arr[st.top()]) {
                st.pop();
            }
            left[i] = st.empty() ? i + 1 : i - st.top();
            st.push(i);
        }
        // pass#2: build right using monotonic increasing stack
        stack<int>().swap(st);
        for (int i = n - 1; i >= 0; i--) {
            int num = arr[i];
            while (!st.empty() && num <= arr[st.top()]) {
                st.pop();
            }
            right[i] = st.empty() ? n - i : st.top() - i;
            st.push(i);
        }
        // Calculate ans
        for(int i=0; i <n; i++) {
            long size = (left[i]*right[i])%PRIME;
            long sum = (arr[i]*size)%PRIME;
            ans =  (ans + sum)%PRIME;
        }
        return ans;
    }
};

2104. Sum of Subarray Ranges

https://leetcode.com/problems/sum-of-subarray-ranges/description/

You are given an integer array nums. The range of a subarray of nums is the difference between the largest and smallest element in the subarray.

Return the sum of all subarray ranges of nums.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [1,2,3]
Output: 4
Explanation: The 6 subarrays of nums are the following:
[1], range = largest - smallest = 1 - 1 = 0 
[2], range = 2 - 2 = 0
[3], range = 3 - 3 = 0
[1,2], range = 2 - 1 = 1
[2,3], range = 3 - 2 = 1
[1,2,3], range = 3 - 1 = 2
So the sum of all ranges is 0 + 0 + 0 + 1 + 1 + 2 = 4.

Approach#1: Use monotonic stack to get sum of all min followed by max and then diff it

We can simply run the monotonic stack based algorithm based on previous problem as below.

1. Get sum of subarray minimums
2. Get sum of subarray maximum
3. Subtract max sum with min sum

Following is code for reference.

class Solution {
private:
    bool op(int a, int b, bool isMin, bool isTrue) {
        if (isMin) {
            return isTrue? a <= b : a <b;
        }
        return isTrue? a >=b : a > b;
    }
    long long subarraySum(vector<int>& nums, bool isMin) {
        int n = nums.size();
        long long ans = 0;
        vector<int> left(n);
        vector<int> right(n);
        stack<int> st;
        // Pass1: for left
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            while (!st.empty() && op(num, nums[st.top()], isMin, false)) {
                st.pop();
            }
            left[i] = st.empty() ? i + 1 : i - st.top();
            st.push(i);
        }
        // Pass2: for right
        stack<int>().swap(st);
        for (int i = n - 1; i >= 0; i--) {
            int num = nums[i];
            while (!st.empty() && op(num, nums[st.top()], isMin, true)) {
                st.pop();
            }
            right[i] = st.empty() ? n - i : st.top() - i;
            st.push(i);
        }
        // Calculate answer
        for (int i = 0; i < n; i++) {
            long long size = left[i] * right[i];
            ans += (nums[i] * size);
        }
        return ans;
    }

public:
    long long subArrayRanges(vector<int>& nums) {
        long long minSum = subarraySum(nums, true);
        long long maxSum = subarraySum(nums, false);
        return maxSum - minSum;
    }
};

975. Odd Even Jump

https://leetcode.com/problems/odd-even-jump/description/

You are given an integer array arr. From some starting index, you can make a series of jumps. The (1st, 3rd, 5th, ...) jumps in the series are called odd-numbered jumps, and the (2nd, 4th, 6th, ...) jumps in the series are called even-numbered jumps. Note that the jumps are numbered, not the indices.

You may jump forward from index i to index j (with i < j) in the following way:

• During odd-numbered jumps (i.e., jumps 1, 3, 5, …), you jump to the index j such that arr[i] <= arr[j] and arr[j] is the smallest possible value. If there are multiple such indices j, you can only jump to the smallest such index j.
• During even-numbered jumps (i.e., jumps 2, 4, 6, …), you jump to the index j such that arr[i] >= arr[j] and arr[j] is the largest possible value. If there are multiple such indices j, you can only jump to the smallest such index j.
• It may be the case that for some index i, there are no legal jumps.

A starting index is good if, starting from that index, you can reach the end of the array (index arr.length - 1) by jumping some number of times (possibly 0 or more than once).

Return the number of good starting indices.

Example 1:

Input: arr = [10,13,12,14,15]
Output: 2
Explanation: 
From starting index i = 0, we can make our 1st jump to i = 2 (since arr[2] is the smallest among arr[1], arr[2], arr[3], arr[4] that is greater or equal to arr[0]), then we cannot jump any more.
From starting index i = 1 and i = 2, we can make our 1st jump to i = 3, then we cannot jump any more.
From starting index i = 3, we can make our 1st jump to i = 4, so we have reached the end.
From starting index i = 4, we have reached the end already.
In total, there are 2 different starting indices i = 3 and i = 4, where we can reach the end with some number of
jumps.

Approach# Using monotonic stack

TBD