Next Greater Element I
Problem Description
We are given two arrays: nums1 (smaller) and nums2 (larger). For each element in nums1, find where it appears in nums2. Once you find it in nums2, look to the right of its position to find the next element that is larger. If no such element exists, return -1 for that element. Collect these results in an array and return it.
Examples
Input: nums1 = [4, 1, 2] and nums2 = [1, 3, 4, 2]
Output: [-1, 3, -1]
Explanation:
For nums1[0] = 4, no greater element to the right in nums2 -> -1.
For nums1[1] = 1, the next greater element to the right is 3 in nums2 -> 3.
For nums1[2] = 2, no greater element to the right in nums2-> -1.
So, the output is [-1, 3, -1]
Input: nums1 = [2, 4] and nums2 = [1, 2, 3, 4]
Output: [3, -1]
Explanation:
For nums1[0] = 2, the next greater element to the right is 3 in nums2 -> 3.
For nums1[1] = 4, no greater element to the right in nums2 -> -1.
So, the output is [3, -1].
Constraints:
- 1 <= nums1.length <= nums2.length <= 1000
- 0 <= nums1[i], nums2[i] <= 10^4
- All integers in nums1 and nums2 are unique.
- All the integers of nums1 also appear in nums2.
Brute Force Approach
Intuition
The first thought that comes to mind is the simple simulation of the whole procedure for finding the next greater element. This method is straightforward.
The problem requires finding the next greater element for each element in nums1 from the array nums2. The "next greater element" for an element x in nums2 is the first element that is greater than x and appears to the right of x in nums2. If no such element exists, the answer for that element should be -1.
Approach:
- Initialization:
- Create an empty vector ans to store the result.
2. Nested Loops:
- Outer Loop: Iterate over each element in nums1. Let’s call the current element nums1[i].
- First Inner Loop: For each nums1[i], iterate through nums2 to find the first occurrence of nums1[i]. Let’s call the index of this occurrence j.
- Second Inner Loop: Once nums1[i] is found in nums2 at index j, start another loop from j + 1 to the end of nums2 to find the next greater element. If an element greater than nums1[i] is found, store it in a temporary variable val and break the loop. If no such element is found, val remains -1.
- Append val to the ans vector.
3. Return the Result:
- After processing all elements in nums1, return the ans vector which contains the next greater elements or -1 if no such element exists.
Dry Run
Let’s perform a dry run of the provided code using the following example:
- nums1 = [2, 4, 3]
- nums2 = [1, 2, 3, 4, 5]
nums1 = [2, 4, 3]
nums2 = [1, 2, 3, 4, 5]
Step 1: Find Next Greater Element for nums1[0] = 2
Search for 2 in nums2 (Traversing in nums2) : 1 -> 2 (Found)
Next elements to the right of 2 in nums2: [3, 4, 5]
The next greater element after 2 is 3
Result: [3]
Step 2: Find Next Greater Element for nums1[1] = 4
Search for 4 in nums2 (Traversing in nums2) : 1 -> 2 -> 3 -> 4 (Found)
Next elements to the right of 4 in nums2: [5]
The next greater element after 4 is 5
Result: [3, 5]
Step 3: Find Next Greater Element for nums1[2] = 3
Search for 3 in nums2 (Traversing in nums2) : 1 -> 2 -> 3 (Found)
Next elements to the right of 3 in nums2: [4, 5]
The next greater element after 3 is 4
Result: [3, 5, 4]
Final Result : The final result array ans for nums1 = [2, 4, 3] is [3, 5, 4].
Brute Force Code for All Languages
C++
class Solution {
public:
// Function to find the next greater element for each element in nums1 from nums2
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
// Result vector to store the next greater elements
vector<int> ans;
// Iterate over each element in nums1
for (int i = 0; i < nums1.size(); i++) {
// Iterate over nums2 to find the first occurrence of nums1[i]
for (int j = 0; j < nums2.size(); j++) {
// Initialize val to -1 (default if no greater element is found)
int val = -1;
// When nums1[i] is found in nums2
if (nums1[i] == nums2[j]) {
// Search for the next greater element in nums2 from index j + 1
for (int k = j + 1; k < nums2.size(); k++) {
// Next greater element found
if (nums2[k] > nums1[i]) {
// Update val
val = nums2[k];
// Exit the inner loop once the next greater element is found
break;
}
}
// Add the next greater element or -1 to the result
ans.push_back(val);
}
}
}
// Return the result vector
return ans;
}
};
Java
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
// Result array to store the next greater elements
int[] ans = new int[nums1.length];
// Iterate over each element in nums1
for (int i = 0; i < nums1.length; i++) {
// Initialize the next greater element as -1 by default
int val = -1;
// Find the first occurrence of nums1[i] in nums2
for (int j = 0; j < nums2.length; j++) {
if (nums1[i] == nums2[j]) {
// Search for the next greater element in nums2 from index j + 1
for (int k = j + 1; k < nums2.length; k++) {
// If a next greater element is found
if (nums2[k] > nums1[i]) {
val = nums2[k];
break;
}
}
// Store the result for the current element in nums1
ans[i] = val;
break;
}
}
}
// Return the result array
return ans;
}
}
Python
from typing import List
class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
# Result list to store the next greater elements
ans = []
# Iterate over each element in nums1
for num in nums1:
# Initialize val to -1 (default if no greater element is found)
val = -1
# Find the index of num in nums2
found = False
for j in range(len(nums2)):
if nums2[j] == num:
# Search for the next greater element in nums2 from index j + 1
for k in range(j + 1, len(nums2)):
# Next greater element found
if nums2[k] > num:
val = nums2[k]
break
found = True
break
# Add the next greater element or -1 to the result
ans.append(val)
# Return the result list
return ans
Javascript
var nextGreaterElement = function(nums1, nums2) {
// Result array to store the next greater elements
let ans = [];
// Iterate over each element in nums1
for (let i = 0; i < nums1.length; i++) {
// Initialize the next greater element as -1 by default
let val = -1;
// Find the first occurrence of nums1[i] in nums2
for (let j = 0; j < nums2.length; j++) {
if (nums1[i] === nums2[j]) {
// Search for the next greater element in nums2 from index j + 1
for (let k = j + 1; k < nums2.length; k++) {
// If a next greater element is found
if (nums2[k] > nums1[i]) {
val = nums2[k];
break;
}
}
// Store the result for the current element in nums1
ans.push(val);
break;
}
}
}
// Return the result array
return ans;
};
Time Complexity - O(n^3)
The approach utilizes three nested loops, leading to a time complexity of O(n1×n2×n2), where n1 is the length of nums1 and n2 is the length of nums2. Here’s a detailed breakdown:
- The outermost loop iterates over each element in nums1, which contributes O(n1).
- For each element in nums1, we need to find its position in nums2, leading to an O(n2) operation.
- Once the position is found, we then iterate through the remaining elements in nums2 to find the next greater element, which in the worst case takes O(n2).
Thus, the total time complexity becomes O(n1×n2×n2). This can be inefficient for large inputs, as the time taken grows quickly with the size of the input arrays.
Space Complexity : O(n)
The space complexity is O(n1) for storing the result vector ans, where n1 is the length of nums1. This is because we need to store one result for each element in nums1, and no additional space is used that scales with the size of nums2.
When to use this Approach?
Use this approach when the input constraint's given to you is of the order 10³, and when you are discussing the very first approach in an interview. Obviously the interviewer wont be happy with this O(n1*n2*n2) approach he will definitely ask you to optimize it.
As we saw the time complexity of the brute force approach is O(n³) which is insufficient for large inputs, so lets move towards building a more optimized approach.
Optimal Approach
Intuition
To improve the time complexity of finding the next greater element, we need to identify patterns in the problem that can guide us towards a more efficient solution. Let’s analyze the input array from left to right and consider the following observations:
Important Observations
When traversing the input array, we can encounter two main cases:
- Decreasing Order Sequence:
- In a sequence where elements are in decreasing order, the first next greater value will be the next greater element for all the values in the sequence.
- For example, in the sequence [6, 4, 3], the next greater element for 6, 4, and 3 is 8, the first value greater than all of them. Similarly, in the sequences [8, 7] and [2, 1], their next greater elements would be 12 and 5 respectively.
2. Increasing Order Sequence:
- In a sequence where elements are in increasing order, each element’s adjacent element is the next greater element.
- For example, in the sequence [12, 15, 16], the next greater element for 12 is 15, and for 15, it is 16. Similarly, in the sequence [5, 11, 13], the next greater element for 5 is 11, and for 11, it is 13.
To identify the next greater elements efficiently, we can traverse the array from left to right. When we find the first element that is greater than the previous elements, we can stop and save it as the next greater element for those elements. This greater element can also serve as the next greater element for some preceding elements.
To better understand this procedure, we can say that elements need to wait until their next greater element arrives. As we observed, there can be two types of sequences: either an increasing order sequence or a decreasing order sequence. In an increasing order sequence, only one element is waiting each time, and the current element becomes the next greater element for that single waiting element. On the other hand, in a decreasing order sequence, there can be many previous elements waiting for their next greater element. In this case, if the current element breaks the decreasing order of the sequence, it becomes the next greater element for all the waiting elements that are lesser than its value.
Where to store Previous Elements?
So the question arises: as we are traversing the array and elements are waiting for their next greater element, how do we store them to identify the waiting elements? Let’s take an array for this purpose and simulate this procedure.
Initial Setup arr[] = [4, 5, 2, 25, 7, 8, 6, 3, 12]
Stored Elements: []
Results: []
Step 1: Current Element: arr[0] = 4
Action: Store 4
Stored Elements: [4]
Results: []
Step 2: Current Element: arr[1] = 5
Action: Compare 5 with 4 (5 > 4), so 5 is the next greater element for 4.
Remove 4 and store 5
Stored Elements: [5]
Results: [(4, 5)]
Step 3: Current Element: arr[2] = 2
Action: 5 > 2, so just store 2
Stored Elements: [5, 2]
Results: [(4, 5)]
Step 4: Current Element: arr[3] = 25
Action: Compare (25 > 2), so 25 is the next greater element for 2. Remove 2.
Compare (25 > 5), so 25 is the next greater element for 5. Remove 5.
Store 25
Stored Elements: [25]
Results: [(4, 5), (2, 25), (5, 25)]
Step 5: Current Element: arr[4] = 7
Action: 25 > 7, so just store 7
Stored Elements: [25, 7]
Results: [(4, 5), (2, 25), (5, 25)]
Step 6: Current Element: arr[5] = 8
Action: Compare (8 > 7), so 8 is the next greater element for 7. Remove 7.
Store 8
Stored Elements: [25, 8]
Results: [(4, 5), (2, 25), (5, 25), (7, 8)]
Step 7: Current Element: arr[6] = 6
Action: 8 > 6, so just store 6
Stored Elements: [25, 8, 6]
Results: [(4, 5), (2, 25), (5, 25), (7, 8)]
Step 8: Current Element: arr[7] = 3
Action: 6 > 3, so just store 3
Stored Elements: [25, 8, 6, 3]
Results: [(4, 5), (2, 25), (5, 25), (7, 8)]
Step 9: Current Element: arr[8] = 12
Action: Compare (12 > 3), so 12 is the next greater element for 3. Remove 3.
Compare (12 > 6), so 12 is the next greater element for 6. Remove 6.
Compare (12 > 8), so 12 is the next greater element for 8. Remove 8.
Store 12
Stored Elements: [25, 12]
Results: [(4, 5), (2, 25), (5, 25), (7, 8), (3, 12), (6, 12), (8, 12)]
Remaining elements: 25, 12 (no next greater elements)
Final Stored Elements: [25, 12]
Final Results: [(4, 5), (2, 25), (5, 25), (7, 8), (3, 12), (6, 12), (8, 12), (25, None), (12, None)]
As the elements which we are storing are coming out in the LIFO fashion (Last in First Out), the most used data structure which is used for such situations is nothing but a Stack.
Approach
- Process the Second Array to Find Next Greater Elements:
- We utilize a stack to identify the next greater elements for each element in the second array.
- As we iterate through the second array, we maintain elements in the stack in a way that the top of the stack always holds the index of the current highest element for which we are yet to find a next greater element.
- For each element, we pop elements from the stack until we find a greater element or the stack becomes empty. The popped elements have found their next greater element.
- We store these results in a hash map where the key is the element and the value is its next greater element.
2. Process the First Array to Retrieve Results Efficiently:
- For each element in the first array, we directly fetch the next greater element from the hash map.
What is a Hash Map?
Hash maps are a powerful data structure that store key-value pairs, allowing for fast access to values using their keys. They are used to determine where to store each pair, enabling average-case time complexities of O(1) for insertion, search, and deletion.
Why Use a Hash Map?
A hash map is used because it provides average O(1) time complexity for both insertions and lookups. By storing the next greater elements of the second array in a hash map, we can efficiently retrieve these results while processing the first array. This approach ensures that we maintain an overall O(n) time complexity for the entire operation.
Dry Run
let’s perform a dry run of the monotonic stack approach using the following example:
- nums1 = [4, 1, 2]
- nums2 = [1, 3, 4, 2]
Initialize:
Stack: []
NextGreaterMap: {}
Traverse nums2 from right to left:
Step 1:
Current Element: nums2[4] = 5
Stack: []
Since the stack is empty, there is no next greater element for 5.
NextGreaterMap: {5: -1}
Stack after pushing 5: [5]
Step 2:
Current Element: nums2[3] = 4
Stack: [5]
The top element of the stack (5) is greater than 4.
NextGreaterMap: {5: -1, 4: 5}
Stack after pushing 4: [5, 4]
Step 3:
Current Element: nums2[2] = 3
Stack: [5, 4]
The top element of the stack (4) is greater than 3.
NextGreaterMap: {5: -1, 4: 5, 3: 4}
Stack after pushing 3: [5, 4, 3]
Step 4:
Current Element: nums2[1] = 2
Stack: [5, 4, 3]
The top element of the stack (3) is greater than 2.
NextGreaterMap: {5: -1, 4: 5, 3: 4, 2: 3}
Stack after pushing 2: [5, 4, 3, 2]
Step 5:
Current Element: nums2[0] = 1
Stack: [5, 4, 3, 2]
The top element of the stack (2) is greater than 1.
NextGreaterMap: {5: -1, 4: 5, 3: 4, 2: 3, 1: 2}
Stack after pushing 1: [5, 4, 3, 2, 1]
Final NextGreaterMap: {1: 2, 2: 3, 3: 4, 4: 5, 5: -1}
To find the result for nums1 = [2, 4, 3], we use the NextGreaterMap:
For 2: NextGreaterMap[2] is 3
For 4: NextGreaterMap[4] is 5
For 3: NextGreaterMap[3] is 4
Result: [3, 5, 4]
Optimal Code for All Languages
C++
class Solution {
public:
// Function to find the next greater element for each element in nums1 from nums2
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
// Stack to keep track of next greater elements
stack<int> stack;
// Initialize with -1 as a sentinel value
stack.push(-1);
// Hash map to store the next greater element for each number in nums2
unordered_map<int, int> nextGreaterMap;
// Iterate over nums2 from right to left
for (int i = nums2.size() - 1; i >= 0; i--) {
// Maintain the decreasing order in the stack
while (stack.top() != -1 && stack.top() <= nums2[i]) {
stack.pop();
}
// Map the current element to the next greater element
nextGreaterMap[nums2[i]] = stack.top();
// Push the current element to the stack
stack.push(nums2[i]);
}
// Prepare the result for nums1 based on the nextGreaterMap
vector<int> result;
for (int num : nums1) {
result.push_back(nextGreaterMap[num]);
}
// Return the result vector
return result;
}
};
Java
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
// Stack to keep track of next greater elements
Stack<Integer> stack = new Stack<>();
// Initialize with -1 as a sentinel value
stack.push(-1);
// Hash map to store the next greater element for each number in nums2
Map<Integer, Integer> nextGreaterMap = new HashMap<>();
// Iterate over nums2 from right to left
for (int i = nums2.length - 1; i >= 0; i--) {
// Maintain the decreasing order in the stack
while (stack.peek() != -1 && stack.peek() <= nums2[i]) {
stack.pop();
}
// Map the current element to the next greater element
nextGreaterMap.put(nums2[i], stack.peek());
// Push the current element to the stack
stack.push(nums2[i]);
}
// Prepare the result for nums1 based on the nextGreaterMap
int[] result = new int[nums1.length];
for (int i = 0; i < nums1.length; i++) {
result[i] = nextGreaterMap.get(nums1[i]);
}
// Return the result array
return result;
}
}
Python
class Solution:
def nextGreaterElement(self, nums1, nums2):
# Stack to keep track of next greater elements
stack = [-1] # Initialize with -1 as a sentinel value
# Dictionary to store the next greater element for each number in nums2
next_greater_map = {}
# Iterate over nums2 from right to left
for num in reversed(nums2):
# Maintain the decreasing order in the stack
while stack[-1] != -1 and stack[-1] <= num:
stack.pop()
# Map the current element to the next greater element
next_greater_map[num] = stack[-1]
# Push the current element to the stack
stack.append(num)
# Prepare the result for nums1 based on the next_greater_map
return [next_greater_map[num] for num in nums1]
Javascript
var nextGreaterElement = function(nums1, nums2) {
// Stack to keep track of next greater elements
let stack = [ - 1];
// Map to store the next greater element for each number in nums2
let nextGreaterMap = new Map();
// Iterate over nums2 from right to left
for (let i = nums2.length - 1; i >= 0; i -- ) {
// Maintain the decreasing order in the stack
while (stack[stack.length - 1] !== -1 && stack[stack.length - 1] <= nums2[i]) {
stack.pop();
}
// Map the current element to the next greater element
nextGreaterMap.set(nums2[i], stack[stack.length - 1]);
// Push the current element to the stack
stack.push(nums2[i]);
}
// Prepare the result for nums1 based on the nextGreaterMap
return nums1.map(num =>nextGreaterMap.get(num));
};
Time Complexity : O(n+m)
The time complexity of this approach is O(n + m), broken down as follows:
- Building the nextGreaterMap: O(n)
- We iterate through nums2 once to build nextGreaterMap.
- Using a stack, each element in nums2 is pushed and popped at most once, which means all stack operations take O(n) time where n is the length of nums2.
- Constructing the Result Array: O(m)
- For each element in nums1, we use nextGreaterMap to find the next greater element in constant time.
- This lookup operation takes O(m) time in total, where m is the length of nums1.
Overall Time Complexity
- Combining both steps, the total time complexity is O(n + m).
- Here, n is the length of nums2 for building the map, and m is the length of nums1 for constructing the result array.
Space Complexity : O(n+m)
- Stack for Storing Elements of nums2: O(n)
- We use a stack to help efficiently find the next greater element for each element in nums2.
- In the worst case, every element of nums2 could be pushed onto the stack (for example, if nums2 is strictly decreasing).
- So, the space needed for the stack can be up to O(n), where n is the length of nums2.
- Hash Map for Mapping Elements of nums2: O(n)
- After determining the next greater element for each element in nums2, we store these mappings in a hash map.
- This hash map allows us to look up the next greater element for any element in nums1 in constant time.
- Since there are n elements in nums2, we need O(n) space for this hash map.
- Result Array for nums1: O(m)
- We create a result array to store the next greater element for each element in nums1.
- The size of this array is m, where m is the length of nums1.
- This space is necessary to store the final output, so it requires O(m) space.
Combining the Components
- The total space complexity is the sum of the individual space requirements: O(n) (stack) + O(n) (hash map) + O(m) (result array) = O(n + m)
- Here, n represents the number of elements in nums2, and m represents the number of elements in nums1.
So, the overall space complexity is O(n + m), where we need space proportional to the lengths of both nums2 and nums1.
This particular approach is suitable for large input size of order of 10⁵
Key Takeaways
The technique of using a stack with a monotonic property (either increasing or decreasing) is often referred to as a Monotonic stack. Many problems can be efficiently solved using this approach, so it is important to become familiar with it.
What is a Monotonic Stack?
The monotonic stack approach revolves around utilizing a stack data structure to solve specific types of problems efficiently.
It is based on the idea of maintaining a monotonic property, either increasing or decreasing, while processing the elements of an array or sequence.
Monotonic Increasing Stack
- The elements in the stack are maintained in increasing order.
- When processing a new element, you pop elements from the stack until you find an element smaller than the current element.
Monotonic Decreasing Stack:
- The elements in the stack are maintained in decreasing order.
- When processing a new element, you pop elements from the stack until you find an element larger than the current element.
Why Use a Monotonic Stack?
The monotonic stack is a powerful use stack, particularly for problems involving comparisons or ranges within a sequence. Here are some key reasons to use it:
- The monotonic stack allows certain types of problems to be solved in linear time, O(n). This is because each element is pushed and popped from the stack at most once.
- It simplifies the logic for problems involving finding the next/previous greater/smaller elements. Instead of using nested loops which can be complex and inefficient, a single pass with a stack suffices.
- It can be applied to a variety of problems in different domains, such as arrays, histograms, and even strings.
Learning Tip
Since we have solved the Next Greater Element problem, let’s now tackle the following related problems:
Previous Greater Element
For each element in the array, find the first greater element to its left. If no such element exists, return -1.
Next Smaller Element
For each element in the array, find the first smaller element to its right. If no such element exists, return -1.
Previous Smaller Element
For each element in the array, find the first smaller element to its left. If no such element exists, return -1.