NUHMAN.com

Introduction

LeetCode 57: Insert Interval is a follow-up to the classic Merge Intervals problem. It tests your ability to insert a new interval into a sorted, non-overlapping list of intervals, merging overlaps as needed.

This is a key problem for mastering interval merging and handling dynamic insertion in sorted structures.

Problem Statement

You are given an array of non-overlapping intervals sorted by their start times. Also given a new interval, insert it into the correct position and merge any overlapping intervals.

Return the resulting array of non-overlapping intervals sorted by start time.

Example 1:

go

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

Example 2:

go

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

Constraints

• 0 <= intervals.length <= 10⁴
• intervals[i].length == 2
• 0 <= start_i <= end_i <= 10⁴
• intervals is sorted by start_i
• 0 <= newInterval[0] <= newInterval[1] <= 10⁴

Approach: Linear Scan + Merge Logic

We'll approach the problem in three phases:

1. Add all intervals before the new interval (no overlap).
2. Merge all overlapping intervals with the new interval.
3. Add remaining intervals after the new merged interval.

Go Implementation

go

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

    // 1. Add all intervals that come before newInterval
    for i < n && intervals[i][1] < newInterval[0] {
        result = append(result, intervals[i])
        i++
    }

    // 2. Merge overlaps with newInterval
    for i < n && intervals[i][0] <= newInterval[1] {
        newInterval[0] = min(newInterval[0], intervals[i][0])
        newInterval[1] = max(newInterval[1], intervals[i][1])
        i++
    }
    result = append(result, newInterval)

    // 3. Add remaining intervals after newInterval
    for i < n {
        result = append(result, intervals[i])
        i++
    }

    return result
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Example Walkthrough

Input:

go

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

Steps:

• Before overlap: [1,2]
• Overlapping: [3,5],[6,7],[8,10] → merged to [3,10]
• After: [12,16]

Final result: [[1,2],[3,10],[12,16]]

Time and Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(n)

Efficient single pass through the list.

Edge Cases

• Empty interval list → return the newInterval alone.
• New interval doesn’t overlap with any → simple insertion.
• All intervals are merged into one large interval.

Key Takeaways

• Understand merging logic and maintain order of intervals.
• Use a greedy, three-phase traversal approach.
• Common in real-world problems like calendar apps and event scheduling.