Next Greater Element Using Stack in DSA Java

Mental Model

We want to find the next bigger number for each number in a list by looking ahead efficiently using a stack.

Analogy: Imagine standing in a line of people with different heights. For each person, you want to find the next taller person standing to their right without checking everyone again and again.

Array: [4] -> [5] -> [2] -> [25] -> null
Stack: empty ↑

Dry Run Walkthrough

Input: array: [4, 5, 2, 25]

Goal: Find the next greater element for each number in the array

Step 1: Push 4 onto stack

Array: 4 -> 5 -> 2 -> 25 -> null
Stack: [4] ↑

Why: Start with first element to compare next elements against

Step 2: 5 is greater than top of stack (4), so pop 4 and set next greater of 4 to 5; push 5

Array: 4 -> 5 -> 2 -> 25 -> null
Stack: [5] ↑

Why: Found next greater for 4, now consider 5 for next elements

Step 3: 2 is not greater than top of stack (5), push 2

Array: 4 -> 5 -> 2 -> 25 -> null
Stack: [5, 2] ↑

Why: 2 might have a next greater later, keep it on stack

Step 4: 25 is greater than top of stack (2), pop 2 and set next greater of 2 to 25

Array: 4 -> 5 -> 2 -> 25 -> null
Stack: [5] ↑

Why: Found next greater for 2, continue checking stack

Step 5: 25 is greater than top of stack (5), pop 5 and set next greater of 5 to 25; push 25

Array: 4 -> 5 -> 2 -> 25 -> null
Stack: [25] ↑

Why: Found next greater for 5, now consider 25

Step 6: No more elements; pop remaining stack elements and set their next greater to -1

Array: 4 -> 5 -> 2 -> 25 -> null
Stack: empty ↑

Why: No next greater element for 25

Result:

Next greater elements: 5 -> 25 -> 25 -> -1

Annotated Code

DSA Java

import java.util.*;

public class NextGreaterElement {
    public static int[] nextGreaterElement(int[] arr) {
        int n = arr.length;
        int[] result = new int[n];
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && arr[i] > arr[stack.peek()]) {
                int index = stack.pop();
                result[index] = arr[i];
            }
            stack.push(i);
        }

        while (!stack.isEmpty()) {
            result[stack.pop()] = -1;
        }

        return result;
    }

    public static void main(String[] args) {
        int[] arr = {4, 5, 2, 25};
        int[] nge = nextGreaterElement(arr);
        for (int val : nge) {
            System.out.print(val + " ");
        }
    }
}

while (!stack.isEmpty() && arr[i] > arr[stack.peek()]) {

Check if current element is greater than element at top index of stack to find next greater

int index = stack.pop();

Pop index from stack to assign its next greater element

result[index] = arr[i];

Set next greater element for popped index

stack.push(i);

Push current index to stack to find its next greater later

while (!stack.isEmpty()) { result[stack.pop()] = -1; }

Assign -1 to elements with no next greater element

Output

5 25 25 -1 

Complexity Analysis

Time: O(n) because each element is pushed and popped at most once from the stack

Space: O(n) for the stack and result array to store next greater elements

vs Alternative: Naive approach is O(n^2) by checking all elements to the right for each element, which is slower

Edge Cases

empty array

returns empty result array without error

DSA Java

int n = arr.length;

all elements in descending order

all elements get -1 as next greater element

DSA Java

while (!stack.isEmpty()) { result[stack.pop()] = -1; }

all elements equal

all elements get -1 as next greater element because no strictly greater element exists

DSA Java

while (!stack.isEmpty()) { result[stack.pop()] = -1; }

When to Use This Pattern

When you need to find the next bigger number for each element in a list efficiently, use the stack pattern to keep track of candidates and find answers in one pass.

Common Mistakes

Mistake: Pushing values instead of indices onto the stack, making it hard to update results correctly
Fix: Push indices to track positions and update the result array properly

Mistake: Not popping all smaller elements from the stack when a bigger element is found
Fix: Use a while loop to pop all smaller elements before pushing the current element

Summary

Finds the next greater element for each item in an array using a stack.

Use when you want to efficiently find the next bigger number to the right for each element.

The key insight is to use a stack to remember elements waiting for their next greater element and update them as soon as a bigger element appears.

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