This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#57) before relying on it.

Insert Interval

An interactive visualization of how the three-phase approach inserts a new interval into a sorted, non-overlapping list and merges any overlaps. Watch the algorithm scan, merge, and build the result on a timeline.

Intervals LeetCode 57 ↗ Medium

The Problem

You are given an array of non-overlapping intervals intervals where intervals[i] = [start_i, end_i], sorted in ascending order by start_i. You are also given an interval newInterval = [start, end].

Insert newInterval into intervals such that intervals is still sorted in ascending order and does not have any overlapping intervals. Merge overlapping intervals if necessary.

Example: For intervals = [[1,3],[6,9]] and newInterval = [2,5], the result is [[1,5],[6,9]] because [1,3] and [2,5] overlap and merge into [1,5].

Interactive Visualization

Intervals (e.g. 1-3, 6-9)

New Interval (e.g. 2-5)

Preset

Speed:

Phase 1: Before

Phase 2: Merge

Phase 3: After

Timeline

Result

Result will build up as the algorithm runs...

Code

fun insert(intervals: Array<IntArray>, newInterval: IntArray): List<IntArray> {    val result = mutableListOf<IntArray>()    var i = 0    val n = intervals.size    // Phase 1: add intervals before newInterval    while (i < n && intervals[i][1] < newInterval[0]) {        result.add(intervals[i])        i++    }    // Phase 2: merge overlapping intervals    while (i < n && intervals[i][0] <= newInterval[1]) {        newInterval[0] = minOf(newInterval[0], intervals[i][0])        newInterval[1] = maxOf(newInterval[1], intervals[i][1])        i++    } result.add(newInterval)    // Phase 3: add remaining intervals    while (i < n) {        result.add(intervals[i])        i++    }    return result}

def insert(intervals, newInterval):    result = []    i = 0    n = len(intervals)    # Phase 1: add intervals before newInterval    while i < n and intervals[i][1] < newInterval[0]:        result.append(intervals[i])        i += 1    # Phase 2: 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    result.append(newInterval)    # Phase 3: add remaining intervals    while i < n:        result.append(intervals[i])        i += 1    return result

Status & Log

Press Step or Play to begin.

How It Works

Three-Phase Approach

The algorithm processes the sorted intervals in a single pass using three consecutive phases. Because the intervals are already sorted and non-overlapping, we can determine each interval's relationship to the new interval by comparing endpoints.

Phase 1: Add Intervals Before

Scan from left to right. While the current interval ends before the new interval starts (i.e. intervals[i][1] < newInterval[0]), there is no overlap. Append these intervals directly to the result.

Phase 2: Merge Overlapping Intervals

Now we have reached intervals that overlap with the new interval. While the current interval starts at or before the new interval ends (i.e. intervals[i][0] <= newInterval[1]), merge by expanding newInterval: take the minimum of the starts and the maximum of the ends. After all overlapping intervals are consumed, append the (possibly expanded) merged interval to the result.

Phase 3: Add Remaining Intervals

Any remaining intervals start after the merged interval ends, so they cannot overlap. Append them all directly to the result.

Complexity

Time O(n)

Space O(n)

We iterate through all n intervals exactly once, and the result array can hold at most n + 1 intervals. No sorting is needed because the input is already sorted.