LeetCode · #57

Insert Interval Solution

Insert a new interval into a sorted, non-overlapping list and merge if necessary.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #57

🏗️

Pattern

Intervals — insert + merge

Given a sorted, non-overlapping array of intervals and a new interval, insert the new interval and merge all overlapping intervals. Return the result sorted and non-overlapping.

Example

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

Constraints

• 0 ≤ intervals.length ≤ 10⁴ • intervals is sorted by startᵢ, non-overlapping

Section Two · Approach 1

Add + Re-merge — O(n log n)

Add the new interval to the list, re-sort, and apply LC 56 merge. Simple but doesn't exploit the pre-sorted property.

Problem: Sorting is O(n log n) when the list is already sorted. We can do O(n) by scanning in three phases: before, overlapping, after.

Java — Add + re-sort + merge

 import java.util.*;
class Solution {
public int[][] insert(int[][] intervals, int[] ni) {
int[][] all = new int[intervals.length + 1][];
        System.arraycopy(intervals, 0, all, 0, intervals.length);
        all[intervals.length] = ni;
        Arrays.sort(all, (a,b) -> a[0] - b[0]);
List<int[]> res = new ArrayList<>();
for (int[] iv : all) {
if (res.isEmpty() || res.get(res.size()-1)[1] < iv[0]) res.add(iv);
else res.get(res.size()-1)[1] = Math.max(res.get(res.size()-1)[1], iv[1]);
        }
return res.toArray(new int[res.size()][]);
    }
}

Python — Add + re-sort + merge

 class Solution:
def insert(self, intervals: list[list[int]], ni: list[int]) -> list[list[int]]:
        intervals.append(ni)
        intervals.sort()
        res = [intervals[0]]
for s, e in intervals[1:]:
if s <= res[-1][1]: res[-1][1] = max(res[-1][1], e)
else: res.append([s, e])
return res

Section Three · Approach 2

Three-Phase Scan — O(n)

Scan in three phases: (1) Add all intervals that end before the new one starts. (2) Merge all overlapping intervals with the new one. (3) Add remaining intervals.

💡 Mental model: Imagine sliding a new appointment into a calendar. First, keep all meetings that finish before the new one starts (no conflict). Then, absorb any meetings that overlap with the new one — stretch the new meeting to cover them all. Finally, keep everything after. Three sweeps, one pass.

Algorithm

Phase 1: While intervals[i].end < newInterval.start: add to result. (Before new interval.)
Phase 2: While intervals[i].start ≤ newInterval.end: merge (expand new interval). Add merged interval.
Phase 3: Add remaining intervals.

🎯 When to recognize this pattern: "Insert into sorted intervals and re-merge." The input is already sorted — exploit that for O(n). The three-phase pattern: before-overlap, merge-overlap, after-overlap. Also applies to calendar/booking problems.

Section Four · Trace

Visual Walkthrough

Trace for intervals=[[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval=[4,8].

Insert Interval — Three Phases

Section Five · Implementation

Code — Java & Python

Java — Three-phase O(n)

 import java.util.*;
class Solution {
public int[][] insert(int[][] intervals, int[] ni) {
List<int[]> res = new ArrayList<>();
int i = 0, n = intervals.length;
// Phase 1: before while (i < n && intervals[i][1] < ni[0])
            res.add(intervals[i++]);
// Phase 2: merge overlap while (i < n && intervals[i][0] <= ni[1]) {
            ni[0] = Math.min(ni[0], intervals[i][0]);
            ni[1] = Math.max(ni[1], intervals[i][1]);
            i++;
        }
        res.add(ni);
// Phase 3: after while (i < n) res.add(intervals[i++]);
return res.toArray(new int[res.size()][]);
    }
}

Python — Three-phase O(n)

 class Solution:
def insert(self, intervals: list[list[int]], ni: list[int]) -> list[list[int]]:
        res, i, n = [], 0, len(intervals)
while i < n and intervals[i][1] < ni[0]:
            res.append(intervals[i]); i += 1 while i < n and intervals[i][0] <= ni[1]:
            ni = [min(ni[0], intervals[i][0]), max(ni[1], intervals[i][1])]
            i += 1
res.append(ni)
while i < n:
            res.append(intervals[i]); i += 1 return res

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Add + re-sort + merge	O(n log n)	O(n)	Doesn't exploit sorted input
Three-phase scan ← optimal	O(n)	O(n)	Single pass; exploits sorted input

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Empty list	`[], [2,5]`	Only the new interval. Return [[2,5]].
Insert at start	`[[3,5]], [1,2]`	Phase 1 empty, Phase 2 no overlap. [1,2] added, then [3,5].
Insert at end	`[[1,2]], [3,5]`	Phase 1 takes [1,2]. Phase 2 no overlap. [3,5] added.
Total overlap	`[[1,10]], [3,5]`	New interval inside existing. Merge: [1,10] unchanged.
Merge all	`[[1,2],[3,4]], [2,3]`	[2,3] overlaps both. Result: [1,4].

⚠ Common Mistake: Using intervals[i].end < ni.start for Phase 1 but intervals[i].start < ni.end for Phase 2. The Phase 2 condition must be intervals[i].start ≤ ni.end (less-than-or-equal) to catch touching intervals. Asymmetric comparison between phases is the #1 bug source.

← Back to Interval problems

LearningTree

LC 57 · Insert Interval — Solution & Explanation | DSA Guide