LearnFrenzy
Sign in Take a free test

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

A min-stack that stores the running minimum Answer, explanation & discussion

  • Output
  • Medium
  • 0 comments
  • Answer explained
  • Moderated community
Question 18 Back to Exercise

What is the output of the following Java program?

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

public class Main {
    public static void main(String[] args) {
        Deque<int[]> st = new ArrayDeque<>();          // each entry: {value, minimum so far}
        for (int x : new int[]{5, 3, 7, 2, 8})
            st.push(new int[]{x, st.isEmpty() ? x : Math.min(x, st.peek()[1])});

        StringBuilder sb = new StringBuilder();
        sb.append(st.peek()[1]);
        st.pop();
        st.pop();
        sb.append(' ').append(st.peek()[1]).append(' ').append(st.peek()[0]);
        st.pop();
        sb.append(' ').append(st.peek()[1]);
        System.out.println(sb);
    }
}
  • A 2 3 7 3 Correct
  • B 2 2 7 3
  • C 2 3 3 5
  • D 8 3 7 3
Correct Answer: Option A

Popping 8 and 2 leaves 7 on top, whose stored minimum is 3; popping 7 leaves 3 (minimum 3). getMin is O(1) at every moment.

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