LeetCode 57 - Insert Interval

The problem gives us a list of intervals that are already sorted by starting value and guaranteed to be non-overlapping. Each interval represents a continuous range, written as [start, end].

leetcodemediumarray

LeetCode Problem 57

Difficulty: 🟡 Medium
Topics: Array

Solution

Problem Understanding

The problem gives us a list of intervals that are already sorted by starting value and guaranteed to be non-overlapping. Each interval represents a continuous range, written as [start, end].

We are also given one additional interval, newInterval, that must be inserted into the existing list while preserving two properties:

  1. The intervals remain sorted by start value.
  2. No intervals overlap after insertion.

If the new interval overlaps with one or more existing intervals, we must merge them into a single larger interval.

For example, suppose we already have:

[[1,3],[6,9]]

and we insert:

[2,5]

The interval [2,5] overlaps with [1,3] because their ranges intersect. After merging them, the result becomes:

[[1,5],[6,9]]

The important detail is that the original intervals are already sorted and non-overlapping. This property makes the problem much easier than arbitrary interval merging problems because we can process the intervals from left to right in a single pass.

The constraints are relatively small, with up to 10^4 intervals, but they still strongly suggest that we should aim for a linear solution. An O(n) traversal is ideal, while repeatedly inserting and resorting would be unnecessarily expensive.

Several edge cases are especially important:

  • The input interval list may be empty.
  • The new interval may belong entirely before all existing intervals.
  • The new interval may belong entirely after all existing intervals.
  • The new interval may overlap multiple intervals in sequence.
  • The new interval may already fit without merging anything.
  • The new interval may completely contain existing intervals.

Because the intervals are already sorted and non-overlapping, once we pass the overlap region, we never need to revisit earlier intervals.

Approaches

Brute Force Approach

A straightforward approach is to insert newInterval into the array, sort the entire list by starting position again, and then run the standard interval merging algorithm.

The process would look like this:

  1. Append newInterval to intervals.
  2. Sort all intervals by their starting value.
  3. Traverse the sorted intervals and merge overlapping intervals.

This works because interval merging after sorting is a well-known technique. Whenever the current interval overlaps with the previous merged interval, we extend the merged range.

The downside is that sorting dominates the runtime. Even though the original intervals are already sorted, this approach ignores that structure and performs unnecessary work.

Optimal Approach

The key observation is that the existing intervals are already sorted and non-overlapping.

That means every interval falls into one of three categories relative to newInterval:

  1. Completely before newInterval
  2. Overlapping with newInterval
  3. Completely after newInterval

Because the intervals are sorted, these categories appear in order during a left-to-right traversal.

We can therefore process the array in one pass:

  • First, add all intervals that end before newInterval starts.
  • Then merge all overlapping intervals into newInterval.
  • Finally, append the remaining intervals.

This avoids sorting entirely and achieves linear time complexity.

Approach Time Complexity Space Complexity Notes
Brute Force O(n log n) O(n) Insert, sort, then merge intervals
Optimal O(n) O(n) Single pass using interval ordering property

Algorithm Walkthrough

  1. Initialize an empty result list.

This list will store the final merged intervals in sorted order. 2. Traverse all intervals that come completely before newInterval.

An interval is completely before newInterval if:

$interval[1] < newInterval[0]$

Since these intervals do not overlap, we can safely append them directly to the result. 3. Merge all overlapping intervals.

Two intervals overlap when:

$interval[0] \le newInterval[1]$

During overlap, we expand newInterval to absorb the current interval:

  • The new start becomes the minimum start.
  • The new end becomes the maximum end.

Conceptually:

$newStart = \min(newStart, intervalStart),\quad newEnd = \max(newEnd, intervalEnd)$

This gradually builds the fully merged interval. 4. Append the merged newInterval.

After processing all overlaps, newInterval now represents the complete merged range. 5. Append all remaining intervals.

Since the intervals are sorted and non-overlapping, everything remaining must come after the merged interval and can be appended directly.

Why it works

The algorithm relies on the invariant that the input intervals are already sorted and non-overlapping.

Because of this ordering:

  • All intervals before the overlap region can be copied unchanged.
  • All overlapping intervals appear consecutively.
  • Once overlap ends, no future interval can overlap again.

This guarantees that a single left-to-right traversal correctly constructs the final merged interval list.

Python Solution

from typing import List

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        result = []
        index = 0
        n = len(intervals)

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

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

        # Add the merged interval
        result.append(newInterval)

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

        return result

The implementation follows the exact structure of the algorithm walkthrough.

The first loop copies all intervals that end before the new interval begins. These intervals cannot overlap, so they are added unchanged.

The second loop handles merging. As long as the current interval overlaps with newInterval, we expand the boundaries of newInterval using min and max.

After merging finishes, the updated newInterval represents the fully combined interval and is appended to the result.

Finally, all remaining intervals are copied directly because they occur after the merged region.

The algorithm performs only one linear traversal of the input array.

Go Solution

func insert(intervals [][]int, newInterval []int) [][]int {
    result := [][]int{}
    index := 0
    n := len(intervals)

    // Add intervals completely before newInterval
    for index < n && intervals[index][1] < newInterval[0] {
        result = append(result, intervals[index])
        index++
    }

    // Merge overlapping intervals
    for index < n && intervals[index][0] <= newInterval[1] {
        if intervals[index][0] < newInterval[0] {
            newInterval[0] = intervals[index][0]
        }

        if intervals[index][1] > newInterval[1] {
            newInterval[1] = intervals[index][1]
        }

        index++
    }

    // Add merged interval
    result = append(result, newInterval)

    // Add remaining intervals
    for index < n {
        result = append(result, intervals[index])
        index++
    }

    return result
}

The Go implementation closely mirrors the Python version.

One difference is that Go does not provide built-in min and max functions for integers, so the code uses explicit comparisons.

Slices in Go naturally handle dynamic resizing through append, making them well suited for building the result incrementally.

There are no integer overflow concerns because the interval values are bounded by 10^5.

Worked Examples

Example 1

Input:

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

Step-by-step Trace

Step Current Interval Action newInterval Result
Start - Initialize [2,5] []
1 [1,3] Overlaps, merge [1,5] []
2 [6,9] No overlap, stop merging [1,5] []
3 - Append merged interval [1,5] [[1,5]]
4 [6,9] Append remaining [1,5] [[1,5],[6,9]]

Final output:

[[1,5],[6,9]]

Example 2

Input:

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

Step-by-step Trace

Step Current Interval Action newInterval Result
Start - Initialize [4,8] []
1 [1,2] Comes before, append [4,8] [[1,2]]
2 [3,5] Overlaps, merge [3,8] [[1,2]]
3 [6,7] Overlaps, merge [3,8] [[1,2]]
4 [8,10] Overlaps, merge [3,10] [[1,2]]
5 [12,16] No overlap, stop merging [3,10] [[1,2]]
6 - Append merged interval [3,10] [[1,2],[3,10]]
7 [12,16] Append remaining [3,10] [[1,2],[3,10],[12,16]]

Final output:

[[1,2],[3,10],[12,16]]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each interval is processed at most once
Space O(n) Result array may contain all intervals

The algorithm performs a single linear traversal through the interval list. No sorting or nested iteration is required.

The additional space comes from the output list. Since the problem allows returning a new array, this space usage is expected and optimal for this approach.

Test Cases

from typing import List

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        result = []
        index = 0
        n = len(intervals)

        while index < n and intervals[index][1] < newInterval[0]:
            result.append(intervals[index])
            index += 1

        while index < n and intervals[index][0] <= newInterval[1]:
            newInterval[0] = min(newInterval[0], intervals[index][0])
            newInterval[1] = max(newInterval[1], intervals[index][1])
            index += 1

        result.append(newInterval)

        while index < n:
            result.append(intervals[index])
            index += 1

        return result

solution = Solution()

# Provided example 1
assert solution.insert([[1, 3], [6, 9]], [2, 5]) == [[1, 5], [6, 9]]

# Provided example 2
assert solution.insert(
    [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]],
    [4, 8]
) == [[1, 2], [3, 10], [12, 16]]

# Empty intervals list
assert solution.insert([], [5, 7]) == [[5, 7]]

# Insert before all intervals
assert solution.insert([[3, 5], [7, 9]], [1, 2]) == [[1, 2], [3, 5], [7, 9]]

# Insert after all intervals
assert solution.insert([[1, 2], [3, 5]], [6, 8]) == [[1, 2], [3, 5], [6, 8]]

# Merge with one interval
assert solution.insert([[1, 5]], [2, 3]) == [[1, 5]]

# Merge with all intervals
assert solution.insert([[2, 3], [5, 7], [8, 10]], [1, 12]) == [[1, 12]]

# No overlap in middle
assert solution.insert([[1, 2], [5, 6]], [3, 4]) == [[1, 2], [3, 4], [5, 6]]

# Touching intervals should merge
assert solution.insert([[1, 2], [5, 7]], [2, 5]) == [[1, 7]]

# Single interval input
assert solution.insert([[1, 5]], [6, 8]) == [[1, 5], [6, 8]]

print("All test cases passed!")
Test Why
[[1,3],[6,9]], [2,5] Basic overlap merge
[[1,2],[3,5],[6,7],[8,10],[12,16]], [4,8] Merge across multiple intervals
[], [5,7] Empty input list
[[3,5],[7,9]], [1,2] Insert before all intervals
[[1,2],[3,5]], [6,8] Insert after all intervals
[[1,5]], [2,3] New interval fully contained
[[2,3],[5,7],[8,10]], [1,12] New interval contains everything
[[1,2],[5,6]], [3,4] No overlap in the middle
[[1,2],[5,7]], [2,5] Boundary-touching intervals merge
[[1,5]], [6,8] Single interval without overlap

Edge Cases

Empty Interval List

If intervals is empty, there is nothing to merge. A buggy implementation might assume at least one interval exists and fail with an index error.

The implementation handles this naturally because all loops are skipped and newInterval is appended directly to the result.

New Interval Before or After Everything

When the new interval belongs completely outside the existing range, no merging should occur.

For example:

intervals = [[3,5],[7,9]]
newInterval = [1,2]

or:

intervals = [[1,2],[3,5]]
newInterval = [6,8]

A common bug is inserting the interval in the wrong position or failing to preserve sorted order. The algorithm avoids this by explicitly processing intervals in three ordered phases: before, overlapping, and after.

Merging Multiple Consecutive Intervals

The new interval may overlap several intervals in sequence.

Example:

intervals = [[1,2],[3,5],[6,7],[8,10]]
newInterval = [4,8]

A naive implementation might merge only the first overlap and stop too early.

The algorithm correctly continues merging as long as overlap exists, continuously expanding the interval boundaries until all overlapping intervals are absorbed.

Boundary-Touching Intervals

Intervals such as [1,2] and [2,5] are considered overlapping because they share the boundary value 2.

A subtle bug appears if the overlap condition uses < instead of <=.

The implementation correctly uses:

$interval[0] \le newInterval[1]$

This ensures touching intervals merge into a single continuous interval.