Challenge lab in Stacks and Expression Processing

Mission

Find the next greater value to the right for every item.

Learning outcome: Design a monotonic stack scan

Correctness contract

Invariant: Only the top element is removed, and size equals pushes minus successful pops.

Required technique: Maintain a decreasing stack of unresolved indexes so each index is pushed and popped at most once.

Complexity target: time O(n); space O(n).

Input and output

Input: n followed by exactly n integers. Whitespace may be spaces or line breaks.

Output: Print the requested sequence on one line with single spaces and no trailing space. Return it as a String; Main.java prints it without adding other text.

Assumptions:

• n is positive and is followed by exactly n signed 32-bit integers.

Before you code

1. Restate the input and output contract, then predict the visible example without running code.
2. Implement the core state transition: Maintain a decreasing stack of unresolved indexes so each index is pushed and popped at most once.
3. Trace the smallest boundary case, verify exact formatting, and justify the authored time and auxiliary-space bounds.

Implement Practice.solve(Scanner sc). Keep every provided filename and public class name unchanged.

Sample input

4 2 1 3 0

Sample output

3 3 -1 -1

Why the sample works: Visible walkthrough for the ordinary non-trivial path. An index is resolved when the first strictly greater value to its right pops it from the decreasing stack. Input `4 2 1 3 0` therefore produces `3 3 -1 -1`.

Progressive hints

Try the trace and first milestone before opening a hint. Open them in order.

Hint 1 — Contract: identify what each parsed variable represents and write the invariant beside the loop or recursive method.

Hint 2 — Next step: The stack stores indexes, because both the comparison value and original output position are needed.

Hint 3 — Verification: compare the structure state before and after one operation, then test the smallest valid input and a duplicate or unreachable case when allowed.