1. Introduction
This blog post addresses a common problem in array manipulation: finding the Next Greater Element (NGE) for every element in an array. The Next Greater Element for an element x is defined as the first greater element on the right side of x in the array.
Problem
Given an array, print the Next Greater Element (NGE) for every element. For elements that have no greater element on the right, print -1.
2. Solution Steps
1. Use a stack to keep track of the elements whose NGE is not found yet.
2. Iterate through the array, and for each element:
a. Pop elements from the stack if the current element is greater than the stack's top element.
b. The current element is the NGE for all elements that are popped.
c. Push the current element onto the stack.
3. For elements remaining in the stack, their NGE is -1.
4. Return the array of NGEs.
3. Code Program
import java.util.Arrays;
import java.util.Stack;
public class Solution {
// Main method for testing
public static void main(String[] args) {
int[] input1 = {1, 3, 2, 4};
int[] input2 = {6, 4, 12, 5, 2, 10};
System.out.println("Next greater elements: " + Arrays.toString(findNextGreaterElements(input1)));
System.out.println("Next greater elements: " + Arrays.toString(findNextGreaterElements(input2)));
}
// Method to find the next greater element for each element in the array
public static int[] findNextGreaterElements(int[] nums) {
int[] nge = new int[nums.length];
Stack<Integer> stack = new Stack<>();
for (int i = nums.length - 1; i >= 0; i--) {
// Pop elements from the stack until the current element is smaller than the stack's top
while (!stack.isEmpty() && nums[i] >= stack.peek()) {
stack.pop();
}
// The next greater element is the top of the stack, if available
nge[i] = stack.isEmpty() ? -1 : stack.peek();
stack.push(nums[i]);
}
return nge;
}
}
Output:
Next greater elements: [3, 4, 4, -1] Next greater elements: [12, 12, -1, 10, 10, -1]
Explanation:
The findNextGreaterElements method uses a stack to efficiently find the next greater element for each element in the array. The stack stores elements in decreasing order from top to bottom. For each element in the array (traversed from right to left), the method pops elements from the stack until it finds an element greater than the current one. This element is the next greater element for the current array element. If the stack becomes empty, the next greater element is -1. The method correctly identifies the next greater elements for each element in the provided examples.
Comments
Post a Comment
Leave Comment