57. Insert Interval

At a Glance

Topic: intervals
Pattern: Merge Intervals
Difficulty: Medium
Companies: Google, LinkedIn, Facebook, Amazon, Microsoft
Frequency: High
LeetCode: 57

Problem (one-liner)

Given sorted, disjoint intervals and a new interval newInterval, insert and merge so the result stays sorted and merged. Input: intervals, newInterval. Output: merged interval list.

Recognition Cues

Insert then merge overlaps
Three phases: before (no touch), overlap region, after
Same merge logic as Merge Intervals once inserted

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Insert then run merge — O(n) time / O(n) space.
Single pass three-way merge — O(n) time / O(n) space. <- pick this in interview.

Optimal Solution

Go

package main

func insert(intervals [][]int, newInterval []int) [][]int {
	result := make([][]int, 0, len(intervals)+1)
	newStart := newInterval[0]
	newEnd := newInterval[1]
	index := 0
	for index < len(intervals) && intervals[index][1] < newStart {
		result = append(result, intervals[index])
		index++
	}
	for index < len(intervals) && intervals[index][0] <= newEnd {
		if intervals[index][0] < newStart {
			newStart = intervals[index][0]
		}
		if intervals[index][1] > newEnd {
			newEnd = intervals[index][1]
		}
		index++
	}
	result = append(result, []int{newStart, newEnd})
	for index < len(intervals) {
		result = append(result, intervals[index])
		index++
	}
	return result
}

JavaScript

function insert(intervals, newInterval) {
	const result = [];
	let newStart = newInterval[0];
	let newEnd = newInterval[1];
	let index = 0;
	while (index < intervals.length && intervals[index][1] < newStart) {
		result.push(intervals[index]);
		index++;
	}
	while (index < intervals.length && intervals[index][0] <= newEnd) {
		newStart = Math.min(newStart, intervals[index][0]);
		newEnd = Math.max(newEnd, intervals[index][1]);
		index++;
	}
	result.push([newStart, newEnd]);
	while (index < intervals.length) {
		result.push(intervals[index]);
		index++;
	}
	return result;
}