Implementation lab in Arrays and Dynamic Lists

Mission

Insert a value at an index while preserving every other item.

Learning outcome: Implement insertion while preserving order

Correctness contract

Invariant: Elements occupy indexes 0 through size - 1, and size never exceeds capacity.

Required technique: Open the insertion gap by shifting the live suffix from right to left before writing the new value.

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

Input and output

Input: n, then n integers, then an insertion index in [0, n], then the value to insert. 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:

• The insertion index is in the range 0 through n.

Before you code

1. Restate the input and output contract, then predict the visible example without running code.
2. Implement the core state transition: Open the insertion gap by shifting the live suffix from right to left before writing the new value.
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 1 2 4 5 2 3

Sample output

1 2 3 4 5

Why the sample works: Visible walkthrough for the ordinary non-trivial path. The suffix is copied one position right from the end, leaving one safe gap for the inserted value. Input `4 1 2 4 5 2 3` therefore produces `1 2 3 4 5`.

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 first copied value should come from the old last live index; its destination is one position to the right.

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.