Arrays - Next Greater Element

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.

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 highlighted in nums2 = [1, 3, 4, 2]. There is no next greater element, so the answer is -1.
1 is highlighted in nums2 = [1, 3, 4, 2]. The next greater element is 3.
2 is highlighted 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 highlighted in nums2 = [1, 2, 3, 4]. The next greater element is 3.
4 is highlighted in nums2 = [1, 2, 3, 4]. There is no next greater element, so the answer is -1.

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

Solution 1 - scan through nums2 array for every number in nums1
Solution 2 - scan through nums2 and capture next possible greater element for every number (Answer to the follow-up question)

In this approach, we are going to loop through each number in nums1 array and then loop through nums2 array to find where the number is located and get next immediate greater element if exists.

public class NextGreaterElement1 { /* iteration over both arrays and for each number in nums1, find next immediate greater element if exists from nums2 */ static int[] usingIterateOverArrays(int[] nums1, int[] nums2) { for(int i=0;i <nums1.length; i++) { int num = nums1[i]; int nextGreater=0; for(int j=0; j<nums2.length; j++) { if(nums2[j] == num) { nextGreater = -1; } if(nextGreater == -1 && nums2[j] > num) { nextGreater = nums2[j]; break; } } nums1[i] = nextGreater; } return nums1; } }

Complexity Analysis:

Time complexity: Above code runs in O(n * m) time where n is the length of input array nums2 and m is the length of input array nums1. This is because for every number in nums1 we are looping through nums2.
Space complexity: O(m) for the answer array, in the above implementation, we are modifying input array nums1 itself, but you can create a new array for the result.

Main intution of this approach is that, we are going to loop through nums2 elements and for each number, find the next immediate greater element and store this mapping in a HashMap, then it is easy to find greater elements for the numbers in nums1 array.

Implementation details

If we have to capture next greater element for every number in nums2, one possible way is to scan throguh nums2 array again for each number, but this is going to be O(n²) time complexity.

Since we are looking for next immediate greater element, there is a better way to capture that using a Stack.

We will be initializing a Stack, which will be empty in the beginning and a HashMap<Integer, Integer> that we will be using to store the number from array as key and its next immediate greater element as value.
Then, we are going to loop through the numbers in nums2 array, and for each number in nums2 array currentNum check if this number is greater than the number at top of the Stack :
- If it is, then add this to the HashMap we have created, currentNum as key and number from Stack as value.
- If it is not greater than the number from Stack, then add this number to the Stack.
By the end of this loop, HashMap will contain the next greater elements if it finds one, and the Stack may still have some elements, if there is no greater element found.
Then, for any remaining elements in Stack, we simply add them to the HashMap with value as -1 since there is no greater element found.
Finally, we can go through numbers in nums1 array and get the next greater element that we have already computed from HashMap and return the result.

Let's understand with an example, say nums1 = [4, 1, 2] and nums2 = [1, 3, 4, 2].

We will be looping through nums2 and find next greater elements for each number in the array.

In the first step currentNum = 1, since the Stack is empty, we will just add this to the stack.

Stack
elements
1

Map
key	value

Next number is currentNum = 3, now we look at the top element in the Stack which is 1, currentNum is greater than the element coming from stack. So, for element 1 immediate greater element is 3, so add it to the map. At the same time, we remove 1 from stack, since we found answer for it, and add element 3 to the stack.

Stack
elements
3

Map
key	value
1	3

Next number is currentNum = 4, now we look at the top element in the Stack which is 3, currentNum is greater than the element coming from stack. So, for element 3 immediate greater element is 4, so add it to the map. At the same time, we remove 3 from stack, since we found answer for it, and add element 4 to the stack.

Stack
elements
4

Map
key	value
1	3
3	4

Next number is currentNum = 2, now we look at the top element in the Stack which is 4, currentNum is not greater than the element coming from stack. So, we simply add it to the stack.

Stack
elements
2
4

Map
key	value
1	3
3	4

We have now iterated through nums2 aray fully. Now we look at stack and see if it still had any elements left, yes there are two elements left in the stack. So, for these elements we will add -1 to the map, this is because there are no greater elements found for these. Map now looks like this.

Map
key	value
2	-1
4	-1
1	3
3	4

Now, we will go through nums1 array and find the next greater element from the map we have prepared above. So, for nums1 = [4, 1, 2], the result array is going to be result = [-1, 3, -1].

import java.util.HashMap; import java.util.Stack; public class NextGreaterElement1 { /* For every number in nums2, store next greater element possible in a Map, then loop through nums1 and get greater element from already computed Map */ static int[] usingStackAndMap(int[] nums1, int[] nums2) { Stack<Integer> stack = new Stack<>(); HashMap<Integer, Integer> map = new HashMap<>(); for(int i=0; i<nums2.length; i++) { int currentNum = nums2[i]; while(!stack.isEmpty() && currentNum > stack.peek()) { map.put(stack.pop(), currentNum); } stack.push(currentNum); } // If stack still have elements left while(!stack.isEmpty()) { map.put(stack.pop(), -1); } // now, iterate through nums1 array an find the next greatest element from map which we stored above for(int i=0; i<nums1.length; i++) { nums1[i] = map.get(nums1[i]); } return nums1; } }

Complexity Analysis:

Time complexity: Above code runs in O(n + m) time where n is the length of input array nums2 and m is the length of input array nums1. This is because we are looping through nums2 array once and nums1 array once, we can say that the time complexity is O(n) because nums1 array is a subset of nums2, so atmost we will be iterating over O(2n) time, that implies to O(n).
Space complexity: O(n) for the HashMap and Stack that we are using.

Above implementations source code can be found at GitHub link for Java code

Contents

Complexity Analysis:

Implementation details

Complexity Analysis: