FAANG · LeetCode #57

Insert Interval — three-stage drill

1The ProblemMedium

Insert Interval

Insert a new interval into a sorted, non-overlapping list — merge what it touches.

Examples

intervals=[[1,2],[3,5],[6,7],[8,10],[12,16]], new=[4,8]→ [[1,2],[3,10],[12,16]]intervals=[[1,3],[6,9]], new=[2,5]→ [[1,5],[6,9]]

constraintInput list is already sorted by start and has no internal overlaps; merge only happens against the new interval.

2The PatternTIME O(n log n) · SPACE O(n)

Intervals

Given a pile of ranges, sort them by start — now any overlap is a neighbour, so a single left→right pass handles them.

Problems using this pattern

3The SolutionRESULT → [[1,2],[3,10],[12,16]]

Step through it

given: 5 sorted, non-overlapping intervals · insert the orange interval [4, 8]

Step 1 / 8

Python▎before · merge into new · after

1def insert(intervals, new):
2    out = []
3    i, n = 0, len(intervals)
4    # 1. before new
5    while i < n and intervals[i][1] < new[0]:
6        out.append(intervals[i]); i += 1
7    # 2. merge overlapping into new
8    while i < n and intervals[i][0] <= new[1]:
9        new = [min(new[0], intervals[i][0]),
10               max(new[1], intervals[i][1])]
11        i += 1
12    out.append(new)
13    # 3. after new
14    while i < n:
15        out.append(intervals[i]); i += 1
16    return out

why it worksOne left→right pass through the (already sorted) list in three phases. (1) push everything that ends before new starts. (2) merge each interval that overlaps new — new keeps growing: take min(new.s, iv.s) and max(new.e, iv.e). (3) emit the (possibly grown) new, then push the rest. O(n).

Arrow keys to navigate · escape to reset

All problems by pattern

Two Pointers

Sliding Window

Prefix Sum

Monotonic Deque

Shortest Subarray with Sum at Least K

Binary Search

Arrays & Hashing

Monotonic Stack

Intervals

Insert Interval — three-stage drill

Insert Interval

Intervals

Step through it

All problems by pattern

Two Pointers

Sliding Window

Prefix Sum

Monotonic Deque

Binary Search

Arrays & Hashing

Monotonic Stack

Intervals

Heap / Top-K

Backtracking

Recursive Descent