The intervals are sorted by start and don't overlap. Insert newInterval, merging any overlaps, and return the result.
Before you code
The list is already sorted, so no sort is needed. Intervals fall into three groups: entirely before the new one, overlapping it, and entirely after.
Hints
- Copy intervals whose end is before the new start.
- Merge every interval that overlaps into the new one: take the minimum start and maximum end.
- Append the merged interval, then the rest.
Production & complexity notes
When solving Insert interval on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Intervals and sweeping to reinforce the underlying pattern.
What it practices
Overlap tests on a sorted list, from Intervals and sweeping.