Next Greater Element I

Problem

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.

Follow up: Could you find an O(nums1.length + nums2.length) solution?

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.

Solution

The problem Next Greater Element I can be solved using a hash map of next greater elements for all elements in nums2. In order to improve the performance, a stack can be used to create a hash map in O(nums2.length) time complexity. Let nums2[i] and nums2[j] be the elements for which their next greater elements are yet found. Then nums2[i] > nums2[j] holds true for i < j as nums2[i] would have a next greater element of nums2[j] if nums2[i] < nums2[j]. In other words, if elements which has yet found their next greater elements are pushed to stack in order, it is guaranteed that the top of the stack always contains the smallest element among them. Therefore, at iteration k, by comparing elements from the top of the stack with nums2[k] and popping the stack until the element at the top of the stack is larger than nums2[k], it is possible to create a hash map of all next greater elements in O(nums2.length) complexity.

Implementation

class Solution
{
  public:
    vector<int> nextGreaterElement(vector<int> &nums1, vector<int> &nums2)
    {
        unordered_map<int, int> nge;

        stack<int> nums;
        for (int num : nums2)
        {
            while (!nums.empty() && nums.top() < num)
            {
                nge[nums.top()] = num;
                nums.pop();
            }
            nums.push(num);
        }
        while (!nums.empty())
        {
            nge[nums.top()] = -1;
            nums.pop();
        }

        vector<int> ret;
        ret.reserve(nums1.size());
        for (int num : nums1)
            ret.push_back(nge[num]);

        return ret;
    }
};