LearnFrenzy
Sign in Take a free test

Data Structures in Java · Data Structures in Java Output Questions · Question 20

Next greater element with a monotonic stack Answer, explanation & discussion

  • Output
  • Hard
  • 0 comments
  • Answer explained
  • Moderated community
Question 20 Back to Exercise

What is the output of the following Java program?

Main.java
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class Main {
    public static void main(String[] args) {
        int[] a = {4, 5, 2, 25, 7, 18};
        int[] next = new int[a.length];
        Arrays.fill(next, -1);
        Deque<Integer> st = new ArrayDeque<>();          // indexes still waiting for a greater value
        for (int i = 0; i < a.length; i++) {
            while (!st.isEmpty() && a[st.peek()] < a[i]) next[st.pop()] = a[i];
            st.push(i);
        }
        System.out.println(Arrays.toString(next));
    }
}
  • A [5, 25, 7, 18, 18, -1]
  • B [5, 25, 25, 18, 18, -1]
  • C [-1, 4, 5, 5, 25, 25]
  • D [5, 25, 25, -1, 18, -1] Correct
Correct Answer: Option D

25 resolves both 5 and 2; nothing to the right of 25 is larger, and 18 resolves 7. Each index is pushed and popped once: O(n).

Discussion & Comments 0

Share your method, a shortcut, or ask about a step you didn't follow.

No comments yet. Be the first to share your solution!

Post your comment

Comments appear after a quick review by our team.

Search LearnFrenzy

Esc

Quick links