LeetCode 57: Insert Interval Solution in Python Explained

Problem Statement

LeetCode 57, Insert Interval, is a medium-level problem where you’re given an array of non-overlapping intervals intervals, sorted by start time, and a new interval newInterval to insert. Your task is to merge newInterval into intervals if it overlaps with any existing intervals, ensuring the result remains a list of non-overlapping intervals sorted by start time. Each interval is represented as [start, end] (inclusive).

Constraints

0 <= intervals.length <= 10^4: Number of intervals is between 0 and 10,000.
intervals[i].length == 2: Each interval has a start and end.
0 <= start_i <= end_i <= 10^5: Start and end values are within this range.
intervals is sorted by start_i in ascending order and non-overlapping.
newInterval.length == 2: New interval has a start and end.
0 <= new_start <= new_end <= 10^5: New interval values are within this range.

Example

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Explanation: [2,5] overlaps with [1,3], merges to [1,5]; [6,9] remains separate.

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: [4,8] overlaps with [3,5],[6,7],[8,10], merges to [3,10].

Input: intervals = [], newInterval = [5,7]
Output: [[5,7]]
Explanation: Empty list, insert [5,7] directly.

Understanding the Problem

How do you solve LeetCode 57: Insert Interval in Python? For intervals = [[1,3],[6,9]] and newInterval = [2,5], insert [2,5] and merge overlaps to get [[1,5],[6,9]]. The input intervals are sorted and non-overlapping, so we need to find where newInterval fits and merge any overlaps. We’ll explore two approaches: a Linear Scan with Merging Solution (optimal and primary) and an Alternative with Binary Search (more complex but useful for insertion point). The linear scan method runs in O(n) time by leveraging the sorted nature of the input.

Solution 1: Linear Scan with Merging Approach (Primary)

Explanation

Scan the intervals linearly, adding non-overlapping intervals before newInterval, merging overlapping intervals with newInterval, and then adding remaining non-overlapping intervals after. Use the fact that intervals is sorted to process in one pass.

Here’s a flow for [[1,3],[6,9]], newInterval = [2,5]:

Before: Add [1,3] (merge with [2,5] -> [1,5])
Overlap: None
After: Add [6,9]
Result: [[1,5],[6,9]]

Initialize Result.

List to store merged intervals.

Process Before Overlap.

Add intervals ending before newInterval starts.

Merge Overlaps.

Combine newInterval with overlapping intervals.

Process After Overlap.

Add remaining intervals.

Return Result.

Step-by-Step Example

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

We need [[1,5],[6,9]].

Goal: Insert and merge new interval.
Result for Reference: [[1,5],[6,9]].
Start: intervals = [[1,3],[6,9]], newInterval = [2,5], result = [].
Step 1: Before overlap.

[1,3]: 3 ≥ 2 (overlap), no add yet.

Step 2: Merge overlaps.

[1,3]: 2 ≤ 3, merge start = min(1,2) = 1, end = max(3,5) = 5, newInterval = [1,5].
[6,9]: 6 > 5 (no overlap), stop merging.

Step 3: After overlap.

result = [[1,5]], add [6,9], result = [[1,5],[6,9]].

Finish: Return [[1,5],[6,9]].

Example 2: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]

We need [[1,2],[3,10],[12,16]].

Start: result = [].
Step 1: Before overlap.

[1,2]: 2 < 4, add [1,2], result = [[1,2]].

Step 2: Merge overlaps.

[3,5]: 3 ≤ 4, merge start = min(3,4) = 3, end = max(5,8) = 8, newInterval = [3,8].
[6,7]: 6 ≤ 8, end = max(8,7) = 8, newInterval = [3,8].
[8,10]: 8 ≤ 8, end = max(8,10) = 10, newInterval = [3,10].

Step 3: After overlap.

[12,16]: 12 > 10, add [12,16], result = [[1,2],[3,10],[12,16]].

Finish: Return [[1,2],[3,10],[12,16]].

How the Code Works (Linear Scan with Merging)

Here’s the Python code with line-by-line explanation:

def insert(intervals: list[list[int]], newInterval: list[int]) -> list[list[int]]:
    # Line 1: Initialize result
    result = []
    i = 0
    n = len(intervals)

    # Line 2: Add intervals before newInterval
    while i < n and intervals[i][1] < newInterval[0]:
        result.append(intervals[i])
        i += 1

    # Line 3: Merge overlapping intervals
    while i < n and intervals[i][0] <= newInterval[1]:
        newInterval[0] = min(newInterval[0], intervals[i][0])
        newInterval[1] = max(newInterval[1], intervals[i][1])
        i += 1

    # Line 4: Add merged interval
    result.append(newInterval)

    # Line 5: Add remaining intervals
    while i < n:
        result.append(intervals[i])
        i += 1

    # Line 6: Return merged intervals
    return result

Alternative: Binary Search Approach

Explanation

Use binary search to find the insertion point of newInterval, then merge with overlapping intervals. This is useful if the list isn’t pre-sorted, but since intervals is sorted, it’s less optimal here than linear scan. Still, it’s an insightful alternative.

Find Insertion Point.

Binary search for newInterval’s start.

Merge Left and Right.

Check overlaps on both sides.

Construct Result.

Step-by-Step Example (Alternative)

For [[1,3],[6,9]], newInterval = [2,5]:

Start: Find insertion point for 2.
Step 1: Binary search, insert between [1,3] and [6,9].
Step 2: Merge left: [1,3], 2 ≤ 3, start = min(1,2) = 1, end = max(3,5) = 5.
Step 3: Merge right: [6,9], 6 > 5, no overlap.
Step 4: Result = [[1,5],[6,9]].
Finish: Return [[1,5],[6,9]].

How the Code Works (Binary Search)

def insertBinary(intervals: list[list[int]], newInterval: list[int]) -> list[list[int]]:
    # Line 1: Handle empty case
    if not intervals:
        return [newInterval]

    # Line 2: Binary search for insertion point
    def binarySearch(target: int) -> int:
        left, right = 0, len(intervals)
        while left < right:
            mid = (left + right) // 2
            if intervals[mid][0] <= target:
                left = mid + 1
            else:
                right = mid
        return left

    # Line 3: Find position
    pos = binarySearch(newInterval[0])

    # Line 4: Merge intervals
    result = intervals[:pos]
    if pos > 0 and result[-1][1] >= newInterval[0]:
        result[-1][1] = max(result[-1][1], newInterval[1])
    else:
        result.append(newInterval)

    # Line 5: Process remaining intervals
    for i in range(pos, len(intervals)):
        if result[-1][1] >= intervals[i][0]:
            result[-1][1] = max(result[-1][1], intervals[i][1])
        else:
            result.append(intervals[i])

    # Line 6: Return merged intervals
    return result

Complexity

Linear Scan with Merging:

Time: O(n) – Single pass through sorted intervals.
Space: O(1) – Only result list (excluding output).

Binary Search:

Time: O(n) – Binary search O(log n), merging O(n).
Space: O(1) – Excluding output.

Efficiency Notes

Linear Scan is O(n) time and O(1) space, optimal for LeetCode 57 given the sorted input. Binary Search is also O(n) time due to merging, with O(log n) for insertion, but it’s overkill here since the input is already sorted.

Key Insights

Tips to master LeetCode 57:

Sorted Advantage: Use pre-sorted input for O(n).
Overlap Check: Start ≤ end defines merging.
Three Phases: Before, merge, after.

Additional Example

For intervals = [[1,5]], newInterval = [2,7]:

Goal: [[1,7]].
Linear Scan: Merge [1,5] with [2,7] -> [1,7].
Result: [[1,7]].

Edge Cases

Empty List: [], [1,2] – Return [[1,2]].
No Overlap: [[1,2]], [3,4] – Return [[1,2],[3,4]].
Full Overlap: [[1,10]], [2,3] – Return [[1,10]].

Final Thoughts

The Linear Scan with Merging solution is a winner for LeetCode 57 in Python—simple, efficient, and perfect for sorted intervals. For a related challenge, try LeetCode 56: Merge Intervals to deepen your interval skills! Ready to insert? Solve LeetCode 57 on LeetCode now and test it with [[1,3],[6,9]] and [2,5] to master merging. Dive in and slot it in!