Question 20
Back to Exercise
What is the output of the following Java program?
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!