Find the Next Greater Element - Codes with Visualization
Sasank is a Technical Content Writer with a strong background in competitive programming. He has solved nearly 1500 problems on LeetCode and achieved top rankings in LeetCode Weekly Contests, including global ranks of 171, 196, 206, 308, 352, and more. His expertise in algorithms and problem-solving is also reflected in his active participation on platforms like Codeforces. Sasank enjoys sharing his technical knowledge and helping others learn by creating clear and accessible content.
Problem Statement
Given an array, find the next greater element for each element in the array. The next greater element is the first element to the right that is larger than the current element. If no such element exists, consider it as -1.
For example, if the input array is [4, 5, 2, 10, 8], the output should be:
For 4, the next greater element is 5
For 5, the next greater element is 10
For 2, the next greater element is 10
For 10, there is no greater element, so -1
For 8, there is no greater element, so -1
Therefore, the output array would be [5, 10, 10, -1, -1].
Brute Force Approach
Explanation
The brute force approach is straightforward. For each element in the array, we scan through all the elements to its right until we find the first element that is greater than the current element.
The steps are:
- Initialize a result array of the same size as the input array
- For each element in the input array:
- Look at all elements to its right
- Find the first element that is greater than the current element
- If such an element exists, add it to the result array; otherwise, add -1
The time complexity of this approach is O(n²) where n is the size of the array, because for each element, we might need to scan through the rest of the array in the worst case. The space complexity is O(n) for storing the result array.
Python Code
def next_greater_element_brute(arr):
n = len(arr)
result = [-1] * n # Initialize result array with -1
for i in range(n):
# For each element, look at all elements to its right
for j in range(i + 1, n):
if arr[j] > arr[i]:
# Found the next greater element
result[i] = arr[j]
break
return result
C++ Code
#include <iostream>
#include <vector>
std::vector<int> nextGreaterElementBrute(std::vector<int>& arr) {
int n = arr.size();
std::vector<int> result(n, -1); // Initialize result array with -1
for (int i = 0; i < n; i++) {
// For each element, look at all elements to its right
for (int j = i + 1; j < n; j++) {
if (arr[j] > arr[i]) {
// Found the next greater element
result[i] = arr[j];
break;
}
}
}
return result;
}
Java Code
import java.util.Arrays;
public class NextGreaterElement {
public static int[] nextGreaterElementBrute(int[] arr) {
int n = arr.length;
int[] result = new int[n];
Arrays.fill(result, -1); // Initialize result array with -1
for (int i = 0; i < n; i++) {
// For each element, look at all elements to its right
for (int j = i + 1; j < n; j++) {
if (arr[j] > arr[i]) {
// Found the next greater element
result[i] = arr[j];
break;
}
}
}
return result;
}
}
Optimized Approach
Explanation
We can solve this problem more efficiently using a stack. This method allows us to process elements in a single pass through the array.
The key insight: elements that haven't yet found their next greater element need to be kept track of, and we can use a stack for this.
The steps are:
- Initialize a result array with -1's
- Initialize an empty stack
- Iterate through the array from right to left:
- While the stack is not empty and the current element is greater than or equal to the element at the top of the stack, pop elements from the stack
- If the stack is not empty after the while loop, the element at the top of the stack is the next greater element
- Push the current element onto the stack
This approach has a time complexity of O(n) since each element is pushed and popped at most once. The space complexity is O(n) for the stack and the result array.
Let's Consider array = [4,5,2,10,8].
Initial State:
- result = [-1, -1, -1, -1, -1]
- stack = []
i = 4 → arr[4] = 8
- Stack is empty ⇒ no greater element
- Push 8
result = [-1, -1, -1, -1, -1], stack = [8]
i = 3 → arr[3] = 10
- Pop 8 (since 8 <= 10)
- Stack is now empty ⇒ no greater element
- Push 10
result = [-1, -1, -1, -1, -1], stack = [10]
i = 2 → arr[2] = 2
- Stack top 10 > 2 ⇒ next greater is 10
- Set result[2] = 10
- Push 2
result = [-1, -1, 10, -1, -1], stack = [10, 2]
i = 1 → arr[1] = 5
- Pop 2 (since 2 <= 5)
- Stack top 10 > 5 ⇒ next greater is 10
- Set result[1] = 10
- Push 5
result = [-1, 10, 10, -1, -1], stack = [10, 5]
i = 0 → arr[0] = 4
- Stack top 5 > 4 ⇒ next greater is 5
- Set result[0] = 5
- Push 4
result = [5, 10, 10, -1, -1], stack = [10, 5, 4]
<visualization-box>
Python Code
def next_greater_element(arr):
n = len(arr)
result = [-1] * n # Initialize result array with -1
stack = [] # Stack to keep track of elements
# Process all elements from right to left
for i in range(n-1, -1, -1):
# Remove elements from stack that are smaller than or equal to current
while stack and stack[-1] <= arr[i]:
stack.pop()
# If stack is not empty, top element is the next greater element
if stack:
result[i] = stack[-1]
# Push current element to stack
stack.append(arr[i])
return result
C++ Code
#include <vector>
#include <stack>
std::vector<int> nextGreaterElement(std::vector<int>& arr) {
int n = arr.size();
std::vector<int> result(n, -1); // Initialize result array with -1
std::stack<int> stack; // Stack to keep track of elements
// Process all elements from right to left
for (int i = n - 1; i >= 0; i--) {
// Remove elements from stack that are smaller than or equal to current
while (!stack.empty() && stack.top() <= arr[i]) {
stack.pop();
}
// If stack is not empty, top element is the next greater element
if (!stack.empty()) {
result[i] = stack.top();
}
// Push current element to stack
stack.push(arr[i]);
}
return result;
}
Java Code
import java.util.Arrays;
import java.util.Stack;
public static int[] nextGreaterElement(int[] arr) {
int n = arr.length;
int[] result = new int[n];
Arrays.fill(result, -1); // Initialize result array with -1
Stack<Integer> stack = new Stack<>(); // Stack to keep track of elements
// Process all elements from right to left
for (int i = n - 1; i >= 0; i--) {
// Remove elements from stack that are smaller than or equal to current
while (!stack.isEmpty() && stack.peek() <= arr[i]) {
stack.pop();
}
// If stack is not empty, top element is the next greater element
if (!stack.isEmpty()) {
result[i] = stack.peek();
}
// Push current element to stack
stack.push(arr[i]);
}
return result;
}
Conclusion
We've explored two methods to solve the "Next Greater Element" problem:
1. The brute force approach with O(n²) time complexity, which is simple but inefficient for large inputs.
2. The optimized stack-based approach with O(n) time complexity, which efficiently handles large inputs.
The stack-based solution shows how using the right data structure can transform an inefficient algorithm into an efficient one. This optimization pattern is common in array and sequence problems, where information about previous elements needs to be tracked.
