Next Greater Element I

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:

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:

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.

Given an array, print the Next Greater Element (NGE) for every element. The Next greater Element for an element x is the first greater element on the right side of x in array. Elements for which no greater element exist, consider next greater element as -1.

Examples:
i.   For an array, the rightmost element always has the next greater element as -1.
ii.  For an array that is sorted in decreasing order, all elements have the next greater element as -1.
iii. For the input array {1,4,3,6,7} the next greater elements for each element are as follows.

  Element      NGE    
14
46
36
67
7-1
Next Greater Element in an Array

Algorithm :

  1. Iterate over the array arr[] for i = 0 to (arr.length -1 ).
    1. If the Stack is empty then push the element in the Stack.
    2. Else if the Stack is not empty and Stack top is less than the current element arr[i].
      1. NGE found for the current Stack top. The current element is greater than Stack top.
      2. Print (stack.pop() and arr[i]). Remember stack.pop() will remove the current top.
      3. Repeat 4 and 5 for next Stack Top. All the elements present in the Stack are on the left side of the current element in the input array. And if the current element is greater than stack entries then current element is the NGE.
      4. Push the current element in the Stack.
  2. At these step elements left in the Stack, do not have any NGE.
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        
        Map<Integer, Integer> map = new HashMap<>();
        Stack<Integer> stack = new Stack<>();
        for(int i = nums2.length-1 ; i >= 0 ; i--){
            int num = nums2[i];
            while(!stack.isEmpty() && num > stack.peek()){
                stack.pop();
            }
            int next_greater = stack.isEmpty() ? -1 : stack.peek();
            stack.push(num);
            map.put(num, next_greater);
        }
        int[] result = new int[nums1.length];
        int j = 0;
        for(int num : nums1){
            result[j] = map.get(num);
            j++;
        }
        return result;
    }
}

Complexity Analysis:

  • Time Complexity : O(m+n). The entire nums array(of size n) is scanned only once. The stack’s n elements are popped only once.
  • Space Complexity : O(m+n)stack and map of size n is used. result array of size m is used but output is not considered in complexcity.

Categories: Stack

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s