Next Greater Element Using Stack in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Next Greater Element for a given array

What is the output of the following Java code that finds the next greater element for each element in the array using a stack?

DSA Java

import java.util.*;
public class Main {
    public static void main(String[] args) {
        int[] arr = {4, 5, 2, 25};
        int[] result = nextGreaterElement(arr);
        System.out.println(Arrays.toString(result));
    }
    public static int[] nextGreaterElement(int[] nums) {
        int n = nums.length;
        int[] res = 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();
            }
            res[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(nums[i]);
        }
        return res;
    }
}

A [5, 25, 25, -1]

B [-1, 25, 25, -1]

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

D [-1, -1, -1, -1]

💡 Hint

Think about how the stack helps find the next greater element by storing candidates from right to left.

The code iterates from right to left, using a stack to keep track of elements that could be the next greater element. For each element, it pops smaller or equal elements from the stack until it finds a greater one or the stack is empty. The result array stores the next greater element or -1 if none exists.

🧠 Conceptual

intermediate

Understanding the role of stack in Next Greater Element

Why do we use a stack when solving the Next Greater Element problem?

A To store the final results of next greater elements

B To sort the array elements in ascending order

C To reverse the array before processing

D To keep track of elements for which we haven't found the next greater element yet

💡 Hint

Think about how the stack helps remember elements while scanning the array.

The stack stores elements for which the next greater element is not yet found. As we scan from right to left, we pop smaller elements and find the next greater element for the current element.

🔧 Debug

advanced

Identify the error in Next Greater Element implementation

What error will the following code produce when executed?

DSA Java

import java.util.*;
public class Main {
    public static void main(String[] args) {
        int[] arr = {2, 7, 3, 5};
        int[] result = nextGreaterElement(arr);
        System.out.println(Arrays.toString(result));
    }
    public static int[] nextGreaterElement(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && stack.peek() <= nums[i]) {
                stack.pop();
            }
            res[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(nums[i]);
        }
        return res;
    }
}

A The output will be [ -1, -1, -1, -1 ] but logic is incorrect for next greater element

B The output will be [7, -1, 5, -1]

C The output will be [-1, -1, -1, -1]

D The output will be [-1, 3, 5, -1]

💡 Hint

Check the direction of iteration and how the stack is used.

The code iterates from left to right, which causes the stack to only contain elements smaller or equal to the current element, resulting in no next greater element found for any element, so all results are -1.

🚀 Application

advanced

Next Greater Element for Circular Array

Given a circular array where the next greater element for the last element may be at the start, what is the output of the code below?

DSA Java

import java.util.*;
public class Main {
    public static void main(String[] args) {
        int[] nums = {1, 2, 1};
        int[] res = nextGreaterElements(nums);
        System.out.println(Arrays.toString(res));
    }
    public static int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        Arrays.fill(res, -1);
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < 2 * n; i++) {
            int num = nums[i % n];
            while (!stack.isEmpty() && nums[stack.peek()] < num) {
                res[stack.pop()] = num;
            }
            if (i < n) stack.push(i);
        }
        return res;
    }
}

A [2, -1, 2]

B [2, 1, -1]

C [-1, -1, -1]

D [1, 2, 1]

💡 Hint

Remember the array is circular, so elements at the start can be next greater for elements at the end.

The code simulates a circular array by iterating twice the length. For each element, it finds the next greater element considering wrap-around. For input [1,2,1], the next greater elements are [2, -1, 2].

❓ Predict Output

expert

Next Greater Element with duplicates and negative numbers

What is the output of the following code that finds the next greater element for each element in the array containing duplicates and negative numbers?

DSA Java

import java.util.*;
public class Main {
    public static void main(String[] args) {
        int[] arr = {2, -1, 2, 3, 2};
        int[] result = nextGreaterElement(arr);
        System.out.println(Arrays.toString(result));
    }
    public static int[] nextGreaterElement(int[] nums) {
        int n = nums.length;
        int[] res = 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();
            }
            res[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(nums[i]);
        }
        return res;
    }
}

A [3, 2, -1, -1, -1]

B [3, 2, 3, -1, -1]

C [3, 2, 3, 2, -1]

D [3, -1, 3, -1, -1]

💡 Hint

Duplicates and negative numbers do not affect the stack logic; focus on the next greater element for each position.

The code correctly finds the next greater element for each element, even with duplicates and negatives. For example, for the first 2, the next greater is 3; for -1, next greater is 2; for the second 2, next greater is 3; for 3, no greater element; for last 2, no greater element.

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