leetcode-textbook

0057 - Insert Interval

Difficulty: Medium Pattern: Intervals LeetCode: https://leetcode.com/problems/insert-interval/

Problem

You are given an array of non-overlapping intervals sorted by their start time, intervals[i] = [start_i, end_i], and a new interval newInterval = [start, end]. Insert newInterval into intervals so that the list stays sorted, non-overlapping, and merged as needed. Return the resulting list.

Signature:

int[][] insert(int[][] intervals, int[] newInterval)

Examples (verbatim from LeetCode):

Input:  intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Input:  intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: the new interval [4,8] overlaps [3,5],[6,7],[8,10].

Intuition

The trigger signals are the same as Merge Intervals, plus the key gift: the input is already sorted and non-overlapping. That constraint turns the problem from “merge everything” into “place one new interval and merge only what it touches”. No full sort is needed — a single left-to-right walk does everything.

Walk the list and classify each existing interval by where it stands relative to newInterval. There are exactly three phases, and they always appear in this order:

  1. Before. Intervals whose end < newInterval.start. They sit entirely to the left of the new interval — copy them straight through.
  2. Overlap. Intervals that touch or intersect newInterval. Because the list is sorted, these form one contiguous block. Absorb each into newInterval by taking min of the starts and max of the ends. This grows newInterval to its final merged shape; touching intervals are absorbed too (<= in disguise).
  3. After. Intervals whose start > newInterval.end. They sit entirely to the right — push the (now-final) newInterval once, then copy the rest straight through.

The trick is to defer inserting newInterval until the first “after” interval appears (or until the loop ends). That way the merged range is emitted exactly once, in the correct position.

Checkpoint A – Three phases

Pause and answer before expanding. A wrong first guess teaches more than a fast right one.

Q1 (recall). The problem guarantees the input list is already:

Show answer **(b)** -- that gift is what lets the solution be one O(n) walk with no sort, classifying each existing interval into before / overlap / after.

Q2 (comprehend). In the three-phase walk, an existing interval is absorbed into newInterval (the overlap branch) when:

Show answer **(c)** -- the "before" and "after" branches peel off the disjoint cases, so whatever falls through to the `else` is exactly an overlap (including touching). No extra overlap test is needed.

Pseudocode

function insert(intervals, newInterval):
    result = empty list
    placed = false                  # has newInterval been emitted yet?

    for each interval cur in intervals:
        if cur.end < newInterval.start:
            # phase 1: entirely before
            append cur to result
        else if cur.start > newInterval.end:
            # phase 3: entirely after -> newInterval goes first (once)
            if not placed:
                append newInterval to result
                placed = true
            append cur to result
        else:
            # phase 2: overlap -> absorb cur into newInterval
            newInterval.start = min(newInterval.start, cur.start)
            newInterval.end   = max(newInterval.end,   cur.end)

    # newInterval never overlapped a later interval -> emit it at the tail
    if not placed:
        append newInterval to result

    return result

Java Solution

import java.util.*;

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> result = new ArrayList<>();
        int start = newInterval[0];
        int end = newInterval[1];
        boolean placed = false;

        for (int[] cur : intervals) {
            if (cur[1] < start) {
                // Entirely before the new interval.
                result.add(cur);
            } else if (cur[0] > end) {
                // Entirely after the new interval: emit it once, then this one.
                if (!placed) {
                    result.add(new int[]{start, end});
                    placed = true;
                }
                result.add(cur);
            } else {
                // Overlap (incl. touching): absorb cur into the running range.
                start = Math.min(start, cur[0]);
                end = Math.max(end, cur[1]);
            }
        }

        // newInterval belongs at the tail (no later interval triggered phase 3).
        if (!placed) {
            result.add(new int[]{start, end});
        }
        return result.toArray(new int[0][]);
    }
}

We copy newInterval’s endpoints into local start/end so the merge mutates only those locals, never the caller’s array. The placed flag guarantees the merged range is emitted exactly once: it fires either at the first “after” interval (correct sorted position) or after the loop (if the new interval ends up last). The three branches are mutually exclusive because “before” and “after” already peeled off the disjoint cases, so the else is precisely the overlap block — no extra overlap test needed. result.toArray(new int[0][]) converts back to the int[][] LeetCode wants.

Complexity

Time:  O(n)   -- the input is already sorted, so one pass with no sort.
Space: O(n)   -- the output list holds up to n + 1 intervals.

Dry-Run

Step-by-step on intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] (so start = 4, end = 8):

Step cur branch (start=4, end=8) start/end after result after placed
1 [1,2] 2 < 4 -> before 4 / 8 [[1,2]] false
2 [3,5] 3<=4<=5<=8 -> overlap min(4,3)=4 / max(8,5)=8 [[1,2]] false
3 [6,7] 6<=8, 6>=4 -> overlap 4 / max(8,7)=8 [[1,2]] false
4 [8,10] 8<=8 (touching) -> overlap 4 / max(8,10)=10 [[1,2]] false
5 [12,16] 12 > 10 -> after; emit [4,10], then cur 4 / 10 [[1,2],[4,10],[12,16]] true

Loop ends with placed = true, so the trailing emit is skipped. Final result: [[1,2],[4,10],[12,16]] — matches the expected output.

For contrast, a no-overlap case intervals = [[5,6]], newInterval = [1,2] (start=1, end=2):

Step cur branch result after placed
1 [5,6] 5 > 2 -> after [[1,2],[5,6]] true

Result [[1,2],[5,6]] — the new interval is emitted before any existing one because every existing interval is in the “after” phase.

Checkpoint B – Trace and stress it

Q1 (apply). Trace intervals = [[1,5]], newInterval = [6,8] (so start = 6, end = 8). What is returned?

Show answer **(b)** -- `[1,5]` has `end 5 < start 6`, so it is in the "before" branch and is appended. The loop then ends with `placed = false`, so the trailing `if (!placed)` emits `[6,8]` at the tail, giving `[[1,5],[6,8]]`.

Q2 (analyze). Consider intervals = [[1,2],[3,4]], newInterval = [1,4], which overlaps every existing interval. What is the job of the placed flag plus the post-loop emit here?

Show answer **(a)** -- every existing interval falls in the overlap branch, so the "after" branch never fires and `placed` stays false. The trailing `if (!placed)` is the only thing that emits the final merged range. Together the flag and the trailing emit guarantee exactly-once emission.

Q3 (transfer). Suppose the input list were NOT guaranteed non-overlapping – it might already contain overlaps among its own intervals. How would you change the approach?

Show answer Drop the three-phase walk (it relies on the non-overlapping guarantee). Instead, append `newInterval` to the list and run the full Merge Intervals algorithm: sort everything by start, then do the one-pass merge with `max` on the end. O(n log n) instead of O(n).

Common mistakes