[LeetCode] 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.

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.

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.

Approach: The problem is similar to our previous problem Next Greater Element and we are going to use the same approach here too. That means we are going to use Stack to find the next greater element for every element of num2 and store it in a hash map.

Using this hash map, we can the quickly see if the elements in the num1 has any next greater element or not. If yes, we will add that otherwise we will add -1. That's all!

Implementation in C#:

    public int[] NextGreaterElement(int[] nums1, int[] nums2) 

    {

        Stack<int> stack = new Stack<int>();

        Dictionary<int, int> nextGreaterDict = new Dictionary<int, int>();

        foreach (int num in nums2)

        {

            while (stack.Count > 0 && stack.Peek() < num)

            {

                nextGreaterDict.Add(stack.Peek(), num);

                stack.Pop();

            }

            stack.Push(num);

        }

        int[] result = new int[nums1.Length];

        for (int i = 0; i < nums1.Length; ++i)

        {

            result[i] = nextGreaterDict.ContainsKey(nums1[i]) ? nextGreaterDict[nums1[i]] : -1;

        }        

        return result;

    }

Complexity: O(m + n) where m is size of nums1 and n is size of nums2.