Algorithm Pattern – Monotone Stack (LC 496 739 503)

Question

Monotone Stack question usually ask you to find the next greater integer in an array.

Approach

Maintain a monotone stack, which stores index of descending integers, and while you face an element greater than the top of stack, we could assign this element as the next greater integer.

Algorithm Pattern

Deque<Integer> stack = new ArrayDeque<>(); // our monotone stack
int[] res = new int[length]; // the result array

//go over the array
for(int i = 0; i < array.length; i++){
    // if stack is empty(first one) or the current element in smaller than the top element of stack
    If(stack.isEmpty() || nums[i] < nums[stack.peek()]){
        stack.push(i); // insert index rather than the real value
        continue;
    }

    // if not empty and the current element is greater than the top element
    While(nums[i] > nums[stack.peek()]){
        res[stack.peek()] = nums[i];
    }
}
return res;

Example

496. Next Greater Element I

The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.
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 1:
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.
    Example 2:
    Input: nums1 = [2,4], nums2 = [1,2,3,4]
    Output: [3,-1]
    Explanation: The next greater element for each value of nums1 is as follows:
  • 2 is underlined in nums2 = [1,2,3,4]. The next greater element is 3.
  • 4 is underlined in nums2 = [1,2,3,4]. There is no next greater element, so the answer is -1.

My Solution

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Deque<Integer> stack = new ArrayDeque<>();
        Map<Integer, Integer> map = new HashMap<>();

        // go over the nums2 and get the next greater one
        int[] greater = new int[nums2.length];
        for(int i = 0; i < nums2.length; i++){
            map.put(nums2[i], i); // store the pair of integer and index into hashmap

            // only push to stack if in descending order
            if(stack.isEmpty() || nums2[i] < nums2[stack.peek()]){
                stack.push(i);
                continue;
            }
            // if current one is a greater one, we update for all previous values
            while(!stack.isEmpty() && nums2[i] > nums2[stack.peek()]){
                greater[stack.pop()] = nums2[i];
            }
            // push current one into stack
            stack.push(i);
        }

        // set the values for nums1
        int[] ret = new int[nums1.length];
        int index = 0;
        for(int num : nums1){
            int idx = map.get(num);
            ret[index++] = greater[idx] == 0 ? -1 : greater[idx];
        }

        return ret;
    }
}
739. Daily Temperatures

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Example 1:
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]
Example 2:
Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]
Example 3:
Input: temperatures = [30,60,90]
Output: [1,1,0]

My Solution

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        Deque<Integer> stack = new ArrayDeque<>(); // store index
        int[] res = new int[temperatures.length];

        // go over the temperatures and store the index if descending
        for(int i = 0; i < temperatures.length; i++){
            if(stack.isEmpty()){
                stack.push(i);
                continue;
            }

            int cur = temperatures[i];
            if(cur > temperatures[stack.peek()]){
                // assgin the distance to every index with a smaller value
                while(!stack.isEmpty() && cur > temperatures[stack.peek()]){
                    res[stack.peek()] = i - stack.pop();
                }
            }

            stack.push(i);
        }

        return res;
    }
}

What if circular array

A simple way is to re-iterate the array to mimic the circular status.

503. Next Greater Element II

Given a circular integer array nums (i.e., the next element of nums[nums.length – 1] is nums[0]), return the next greater number for every element in nums.
The next greater number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn’t exist, return -1 for this number.

Example 1:
Input: nums = [1,2,1]
Output: [2,-1,2]
Explanation: The first 1’s next greater number is 2;
The number 2 can’t find next greater number.
The second 1’s next greater number needs to search circularly, which is also 2.
Example 2:
Input: nums = [1,2,3,4,3]
Output: [2,3,4,-1,4]

My Solution

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        Deque<Integer> stack = new ArrayDeque<>();
        int[] res = new int[nums.length];
        Arrays.fill(res, -1);

        for(int i = 0; i < nums.length; i++){
            if(stack.isEmpty() || nums[i] < nums[stack.peek()]){
                stack.push(i);
                continue;
            }

            while(!stack.isEmpty() && nums[i] > nums[stack.peek()]){
                res[stack.pop()] = nums[i];
            }
            stack.push(i);
        }

        if(stack.isEmpty()){
            return res;
        }

        for(int i = 0; i < nums.length; i++){
            while(!stack.isEmpty() && nums[i] > nums[stack.peek()]){
                res[stack.pop()] = nums[i];
            }
        }

        return res;
    }
}