Next Greater Element Using Stack in DSA Java - Execution Trace

Concept Flow - Next Greater Element Using Stack

Start with empty stack

↓

Iterate over array from right to left

↓

While stack not empty and top <= current element

↓

Pop stack top

↓

If stack empty -> No greater element, assign -1

↓

Else -> Top of stack is next greater element

↓

Push current element onto stack

↓

Move to next element left

↓

Repeat until all elements processed

↓

Return result array

We scan the array from right to left, using a stack to keep track of candidates for the next greater element. For each element, we pop smaller or equal elements from the stack until we find a greater one or the stack is empty.

Execution Sample

DSA Java

int[] arr = {4, 5, 2, 25};
int[] result = new int[arr.length];
Stack<Integer> stack = new Stack<>();
for (int i = arr.length - 1; i >= 0; i--) {
  while (!stack.isEmpty() && stack.peek() <= arr[i]) stack.pop();
  result[i] = stack.isEmpty() ? -1 : stack.peek();
  stack.push(arr[i]);
}

This code finds the next greater element for each item in the array using a stack scanning from right to left.

Execution Table

Step	Operation	Current Element	Stack Before	Stack After	Result Array State	Visual State
1	Start	-	[]	[]	[-, -, -, -]	Stack: [] Result: [-, -, -, -]
2	Process element at index 3	25	[]	[25]	[-, -, -, -1]	Stack: [25] Result: [-, -, -, -1]
3	Process element at index 2	2	[25]	[25, 2]	[-, -, 25, -1]	Stack: [25, 2] Result: [-, -, 25, -1]
4	Process element at index 1	5	[25, 2]	[25, 5]	[-, 25, 25, -1]	Stack: [25, 5] Result: [-, 25, 25, -1]
5	Process element at index 0	4	[25, 5]	[25, 5, 4]	[5, 25, 25, -1]	Stack: [25, 5, 4] Result: [5, 25, 25, -1]
6	End	-	[25, 5, 4]	[25, 5, 4]	[5, 25, 25, -1]	Final Stack: [25, 5, 4] Final Result: [5, 25, 25, -1]

💡 All elements processed from right to left; stack contains elements for reference; result array filled with next greater elements or -1 if none.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
i	3 (start)	3	2	1	0	-1 (end)
stack	[]	[25]	[25, 2]	[25, 5]	[25, 5, 4]	[25, 5, 4]
result	[-, -, -, -]	[-, -, -, -1]	[-, -, 25, -1]	[-, 25, 25, -1]	[5, 25, 25, -1]	[5, 25, 25, -1]

Key Moments - 3 Insights

Why do we pop elements from the stack while they are less than or equal to the current element?

Because those elements cannot be the next greater element for the current or any earlier elements. This is shown in step 4 where 2 is popped before pushing 5.

Why do we assign -1 when the stack is empty?

An empty stack means no greater element exists to the right. In step 2, for element 25, stack is empty so result is -1.

Why do we process the array from right to left?

Processing from right to left ensures we have seen all elements to the right of the current element in the stack, allowing us to find the next greater element efficiently.

Visual Quiz - 3 Questions

Look at the execution table at step 4. What is the stack after processing element 5?

A [5]

B [25, 5]

C [25, 2, 5]

D [25]

💡 Hint

Check the 'Stack After' column for step 4 in the execution table.

At which step does the result array get its first non -1 value?

A Step 3

B Step 2

C Step 4

D Step 5

💡 Hint

Look at the 'Result Array State' column and find when the first value other than -1 appears.

If the input array was strictly decreasing, what would the result array contain?

A Next greater elements to the right

B Same as input array

C All elements replaced by -1

D All zeros

💡 Hint

Think about the stack being empty after popping all smaller elements, as shown in the exit note.

Concept Snapshot

Next Greater Element Using Stack:
- Traverse array from right to left
- Use stack to track next greater candidates
- Pop smaller or equal elements from stack
- If stack empty, assign -1
- Else assign stack top as next greater
- Push current element onto stack
- Result array stores next greater elements or -1

Full Transcript

The Next Greater Element problem finds for each element in an array the next element to the right that is greater. We solve this by scanning the array from right to left, using a stack to keep track of elements that could be the next greater element. For each element, we pop from the stack all elements smaller or equal to it, because they cannot be the next greater element. If the stack is empty after popping, it means no greater element exists to the right, so we assign -1. Otherwise, the top of the stack is the next greater element. We then push the current element onto the stack and move left. This process continues until all elements are processed. The execution table shows each step with the stack state and the result array being built. Key moments clarify why we pop elements, why we assign -1, and why we process from right to left. The visual quiz tests understanding of stack states and result array updates. This method efficiently finds next greater elements in O(n) time.

Practice

1. What does the Next Greater Element problem using a stack find for each element in an array?

easy

A. The sum of all elements greater than the current element

B. The first smaller element to the left of each element

C. The first greater element to the right of each element

D. The index of the maximum element in the array

Solution

1. Step 1: Understand the problem definition

   The Next Greater Element problem asks to find, for each element, the first element to its right that is greater than it.

2. Step 2: Identify the role of the stack

   The stack helps keep track of elements for which we haven't found a greater element yet, allowing efficient lookup.

3. Final Answer:

   The first greater element to the right of each element -> Option C

4. Quick Check:

   Next Greater Element = first greater right element [OK]

Hint: Look right for first bigger number using stack [OK]

Common Mistakes:

• Confusing next greater with next smaller element
• Searching to the left instead of right
• Thinking it finds max element overall

2. Which of the following Java code snippets correctly initializes a stack to solve Next Greater Element?

easy

A. Stack stack = new Stack<int>();

B. Stack<Integer> stack = new Stack<>();

C. Stack<int> stack = new Stack<>();

D. Stack<> stack = new Stack<Integer>();

Solution

1. Step 1: Check Java generic syntax for Stack

   Java uses generics with angle brackets and wrapper classes, so Stack<Integer> stack = new Stack<>(); is correct.

2. Step 2: Identify errors in other options

   Stack stack = new Stack<int>(); misses generic type parameter syntax; Stack<int> stack = new Stack<>(); uses primitive int which is invalid; Stack<> stack = new Stack<Integer>(); has incorrect generic syntax.

3. Final Answer:

   Stack<Integer> stack = new Stack<>(); -> Option B

4. Quick Check:

   Use wrapper class Integer with generics [OK]

Hint: Use Stack<Integer> stack = new Stack<>(); for integers [OK]

Common Mistakes:

• Using primitive int instead of Integer in generics
• Missing generic type parameter <>
• Incorrect generic syntax placement

3. What is the output of the following Java code for Next Greater Element?

int[] arr = {4, 5, 2, 25};
int[] nge = nextGreaterElement(arr);
System.out.println(Arrays.toString(nge));

public static int[] nextGreaterElement(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    Stack<Integer> stack = new Stack<>();
    for (int i = n - 1; i >= 0; i--) {
        while (!stack.isEmpty() && stack.peek() <= nums[i]) {
            stack.pop();
        }
        result[i] = stack.isEmpty() ? -1 : stack.peek();
        stack.push(nums[i]);
    }
    return result;
}

medium

A. [5, 25, 25, -1]

B. [25, -1, 5, -1]

C. [5, 25, -1, -1]

D. [-1, 25, 25, -1]

Solution

1. Step 1: Trace from right to left

   Start with i=3 (25): stack empty, result[3] = -1, push 25.
   i=2 (2): stack top=25 > 2, result[2]=25, push 2.
   i=1 (5): pop 2 (<=5), stack top=25 > 5, result[1]=25, push 5.
   i=0 (4): stack top=5 > 4, result[0]=5, push 4.

2. Step 2: Collect results

   Result array is [5, 25, 25, -1].

3. Final Answer:

   [5, 25, 25, -1] -> Option A

4. Quick Check:

   Right side bigger elements found correctly [OK]

Hint: Traverse array backward, use stack to track next greater [OK]

Common Mistakes:

• Traversing left to right instead of right to left
• Not popping smaller or equal elements from stack
• Assigning wrong default -1 positions

4. Identify the bug in this Next Greater Element code snippet:

public static int[] nextGreaterElement(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && stack.peek() <= nums[i]) {
            stack.pop();
        }
        result[i] = stack.isEmpty() ? -1 : stack.peek();
        stack.push(nums[i]);
    }
    return result;
}

medium

A. Loop should run from right to left (i = n-1 to 0)

B. Stack should store indices, not values

C. Result array size is incorrect

D. Missing initialization of stack

Solution

1. Step 1: Analyze loop direction

   The code loops from left to right, but Next Greater Element using stack requires right to left traversal to find next greater on the right.

2. Step 2: Understand impact of loop direction

   Looping left to right causes incorrect results because stack does not have future elements yet.

3. Final Answer:

   Loop should run from right to left (i = n-1 to 0) -> Option A

4. Quick Check:

   Traverse backward for correct next greater [OK]

Hint: Traverse array backward to find next greater correctly [OK]

Common Mistakes:

• Looping forward instead of backward
• Using stack for values instead of indices (not always wrong but different approach)
• Not popping smaller or equal elements

5. Given the array {13, 7, 6, 12}, what is the Next Greater Element array using a stack? Also, explain why the last element's next greater element is -1.

hard

A. [ 7, 12, 13, -1 ]

B. [ -1, 13, 12, -1 ]

C. [ -1, 12, -1, -1 ]

D. [ -1, 12, 12, -1 ]

Solution

1. Step 1: Find next greater elements from right to left

   Start with 12 (last element): no elements to right, so result is -1.
   Next 6: next greater is 12.
   Next 7: next greater is 12.
   Next 13: no greater element to right, so -1.

2. Step 2: Explain last element's result

   The last element has no elements to its right, so no next greater element exists, hence -1.

3. Final Answer:

   [ -1, 12, 12, -1 ] -> Option D

4. Quick Check:

   Last element no right neighbor = -1 [OK]

Hint: Last element always -1, no elements to right [OK]

Common Mistakes:

• Assigning next greater for last element incorrectly
• Mixing up indices and values
• Not traversing array backward