713148. Next Greater Element in Circular Array
Next Greater Element in Circular Array
Slug: next-greater-element
Difficulty: Medium
Id: 713148
Topic Tags: Stack, Data Structures
Company Tags: Flipkart, Amazon, Microsoft
Summary
Given a circular array of integers, find the next greater element for each element. The "next greater" element is defined as the first element in the circular array that is greater than the current element. If no such element exists, return -1.
This problem involves using a stack to keep track of the elements and their indices, which allows us to efficiently find the next greater element for each element in the array.
Detailed Explanation
To solve this problem, we can use a stack-based approach. We iterate through the circular array, pushing elements onto the stack as we go. When we encounter an element that is greater than the top of the stack, we pop elements from the stack until we find the first element that is less than or equal to our current element. This is because all elements in the stack will be smaller than our current element, and any subsequent elements will be larger.
Once we have popped all the elements from the stack that are smaller than our current element, we push our current element onto the stack and mark it as the "next greater" element for the top of the stack. We repeat this process until we have processed the entire circular array.
Here is a step-by-step breakdown of the solution:
- Initialize an empty stack.
- Iterate through the circular array:
- If the current element is greater than the top of the stack, pop elements from the stack until we find the first element that is less than or equal to our current element.
- Push our current element onto the stack and mark it as the "next greater" element for the top of the stack.
- Return the "next greater" element for each element in the circular array.
Time complexity: O(n), where n is the size of the circular array, because we iterate through the array once and pop elements from the stack in constant time.
Space complexity: O(n), because we use a stack to store the elements and their indices.
Optimized Solutions
Java
public int[] nextGreaterElements(int[] nums) {
int n = nums.length;
int[] result = new int[n];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < n * 2; i++) {
while (!stack.isEmpty() && stack.peek() <= nums[i % n]) {
stack.pop();
}
if (!stack.isEmpty()) {
result[i % n] = stack.peek();
} else {
result[i % n] = -1;
}
stack.push(nums[i % n]);
}
return result;
}