Stack : Next Greater Element I

Description

  • You are given two integer arrays nums1 and nums2 both of unique elements, where nums1 is a subset of nums2.

    Find all the next greater numbers for nums1‘s elements in the corresponding places of nums2.

    The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2. If it does not exist, return -1 for this number.

    Example 1:

    1
    2
    3
    4
    5
    6
    Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
    Output: [-1,3,-1]
    Explanation:
    For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1.
    For number 1 in the first array, the next greater number for it in the second array is 3.
    For number 2 in the first array, there is no next greater number for it in the second array, so output -1.

    Example 2:

    1
    2
    3
    4
    5
    Input: nums1 = [2,4], nums2 = [1,2,3,4]
    Output: [3,-1]
    Explanation:
    For number 2 in the first array, the next greater number for it in the second array is 3.
    For number 4 in the first array, there is no next greater number for it in the second array, so output -1.

    Constraints:

    • 1 <= nums1.length <= nums2.length <= 1000
    • 0 <= nums1[i], nums2[i] <= 104
    • All integers in nums1 and nums2 are unique.
    • All the integers of nums1 also appear in nums2.

Thought and Notes

Simply find the pairs in nums2, then travels the nums1.

Solution

Approach 1: Stack

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    public int[] nextGreaterElement(int[] findNums, int[] nums) {
        Stack < Integer > stack = new Stack < > ();
        HashMap < Integer, Integer > map = new HashMap < > ();
        int[] res = new int[findNums.length];
        for (int i = 0; i < nums.length; i++) {
            while (!stack.empty() && nums[i] > stack.peek())
                map.put(stack.pop(), nums[i]);
            stack.push(nums[i]);
        }
        while (!stack.empty())
            map.put(stack.pop(), -1);
        for (int i = 0; i < findNums.length; i++) {
            res[i] = map.get(findNums[i]);
        }
        return res;
    }
}

Complexity Analysis

  • Time complexity : O(m+n)O(m+n). The entire numsnum**s array(of size nn) is scanned only once. The stack’s nn elements are popped only once. The findNumsfindNum**s array is also scanned only once.
  • Space complexity : O(m+n)O(m+n). stackstack and mapmap of size nn is used. resres array of size mm is used, where nn refers to the length of the numsnum**s array and mm refers to the length of the findNumsfindNum**s array.