Original problem · C++ solution
Copy each original value in order and emit X immediately after the K-th value.
Copy each original value in order and emit X immediately after the K-th value. This inserts one new element without changing any existing order.
- Time: O(n).
- Extra space: O(1).
Parenthesize conditional expressions sent to an output stream so the stream insertion operator does not change their grouping. Use separate variables for quantities with different roles.
Check whether the condition is strict or inclusive, particularly at the smallest and largest permitted values.
State the invariant without looking at the code. Give one input that breaks the most tempting incorrect approach, then add it to the tests.