Insert Interval

Problem Statement

You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and end of the ith interval. You are also given a new interval newInterval = [newStart, newEnd] that may overlap with some of the existing intervals.

Insert newInterval into intervals such that intervals is still sorted and non-overlapping (merge overlapping intervals as necessary). Return the resulting array of intervals.

What to notice first

• Three phases: (1) add non-overlapping intervals before newInterval, (2) merge overlapping intervals, (3) add remaining non-overlapping intervals.
• No need to sort; input is already sorted.
• Overlapping condition: interval.end >= newInterval.start AND interval.start <= newInterval.end.

Examples

intervals	newInterval	Output	Explanation
[[1,2],[3,5],[6,9]]	[2,5]	[[1,5],[6,9]]	[2,5] overlaps with [1,2] and [3,5], merge to [1,5]
[[1,5]]	[0,0]	[[0,0],[1,5]]	[0,0] doesn’t overlap, add before
[[1,5]]	[5,7]	[[1,7]]	[5,7] overlaps at boundary, merge
[[1,2],[3,5],[6,9]]	[10,11]	[[1,2],[3,5],[6,9],[10,11]]	[10,11] doesn’t overlap, append

Constraints

• 0 <= intervals.length <= 10^4
• intervals[i].length == 2
• 0 <= starti <= endi <= 10^5
• newInterval.length == 2
• 0 <= newStart <= newEnd <= 10^5
• intervals is sorted by start and does not contain overlapping intervals

Real-World Applications

Where this pattern appears

• Calendar event scheduling — insert new events while merging overlaps.
• Database range queries — insert new time ranges while maintaining non-overlapping constraints.
• Memory allocation — track free memory blocks and insert new allocations.
• Stock trading systems — manage price ranges and insert new trading intervals.

Complexity Comparison

Approach	Time	Space	Notes
Greedy Three-Phase	O(n)	O(n)	Single pass through intervals; merge during iteration
Iterative Merge	O(n)	O(n)	Explicit three phases; clearer logic

Approach 1: Greedy Three-Phase (Recommended)

★ Recommended

Divide the problem into three phases:

1. Add all intervals that end before newInterval starts.
2. Merge all overlapping intervals with newInterval.
3. Add remaining intervals that start after the merged interval ends.

This is efficient because the input is pre-sorted and non-overlapping.

⏱ Time O(n) Single scan through intervals 💾 Space O(n) Result list storage

Step-by-step Example

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

Phase	Action	Result
1	Add [1,2] (ends before 2)	[[1,2]]
2	Merge [2,5] with [3,5] → [2,5]	[[1,2], [2,5]]
3	Merge [2,5] with [6,9]? No (6 > 5)	[[1,2], [2,5]]
Final	Add [6,9]	[[1,2], [2,5], [6,9]]

Pseudocode

function insert(intervals, newInterval):
    result = []
    i = 0
    newStart, newEnd = newInterval

    // Phase 1: Add non-overlapping intervals before
    while i < len(intervals) and intervals[i][1] < newStart:
        result.append(intervals[i])
        i += 1

    // Phase 2: Merge overlapping intervals
    while i < len(intervals) and intervals[i][0] <= newEnd:
        newStart = min(newStart, intervals[i][0])
        newEnd = max(newEnd, intervals[i][1])
        i += 1
    result.append([newStart, newEnd])

    // Phase 3: Add remaining intervals
    while i < len(intervals):
        result.append(intervals[i])
        i += 1

    return result

Solution Code

Python

insert_interval_greedy.py

from typing import List

def insert(intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
    """Greedy approach: O(n) time, O(n) space"""
    result, i, new_start, new_end = [], 0, newInterval[0], newInterval[1]
    while i < len(intervals) and intervals[i][1] < new_start:
        result.append(intervals[i])
        i += 1
    while i < len(intervals) and intervals[i][0] <= new_end:
        new_start = min(new_start, intervals[i][0])
        new_end = max(new_end, intervals[i][1])
        i += 1
    result.append([new_start, new_end])
    while i < len(intervals):
        result.append(intervals[i])
        i += 1
    return result

C++

insert_interval_greedy.cpp

#include <vector>
using namespace std;

vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
    vector<vector<int>> result;
    int i = 0, new_start = newInterval[0], new_end = newInterval[1];
    while (i < intervals.size() && intervals[i][1] < new_start) {
        result.push_back(intervals[i++]);
    }
    while (i < intervals.size() && intervals[i][0] <= new_end) {
        new_start = min(new_start, intervals[i][0]);
        new_end = max(new_end, intervals[i][1]);
        i++;
    }
    result.push_back({new_start, new_end});
    while (i < intervals.size()) {
        result.push_back(intervals[i++]);
    }
    return result;
}

Java

InsertIntervalGreedy.java

import java.util.*;

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> result = new ArrayList<>();
        int i = 0;
        int newStart = newInterval[0];
        int newEnd = newInterval[1];

        // Add non-overlapping intervals before newInterval
        while (i < intervals.length && intervals[i][1] < newStart) {
            result.add(intervals[i]);
            i++;
        }

        // Merge overlapping intervals
        while (i < intervals.length && intervals[i][0] <= newEnd) {
            newStart = Math.min(newStart, intervals[i][0]);
            newEnd = Math.max(newEnd, intervals[i][1]);
            i++;
        }
        result.add(new int[]{newStart, newEnd});

        // Add remaining non-overlapping intervals
        while (i < intervals.length) {
            result.add(intervals[i]);
            i++;
        }

        return result.toArray(new int[result.size()][]);
    }
}

JavaScript

insert_interval_greedy.js

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

Rust

insert_interval_greedy.rs

pub fn insert(intervals: Vec<Vec<i32>>, newInterval: Vec<i32>) -> Vec<Vec<i32>> {
    let mut result = vec![];
    let mut i = 0;
    let mut new_start = newInterval[0];
    let mut new_end = newInterval[1];
    while i < intervals.len() && intervals[i][1] < new_start {
        result.push(intervals[i].clone());
        i += 1;
    }
    while i < intervals.len() && intervals[i][0] <= new_end {
        new_start = new_start.min(intervals[i][0]);
        new_end = new_end.max(intervals[i][1]);
        i += 1;
    }
    result.push(vec![new_start, new_end]);
    while i < intervals.len() {
        result.push(intervals[i].clone());
        i += 1;
    }
    result
}

Go

insert_interval_greedy.go

package main

func insert(intervals [][]int, newInterval []int) [][]int {
    result := [][]int{}
    i, new_start, new_end := 0, newInterval[0], newInterval[1]
    for i < len(intervals) && intervals[i][1] < new_start {
        result = append(result, intervals[i])
        i++
    }
    for i < len(intervals) && intervals[i][0] <= new_end {
        if intervals[i][0] < new_start { new_start = intervals[i][0] }
        if intervals[i][1] > new_end { new_end = intervals[i][1] }
        i++
    }
    result = append(result, []int{new_start, new_end})
    for i < len(intervals) {
        result = append(result, intervals[i])
        i++
    }
    return result
}

Approach 2: Iterative Merge

✓ Simple

Identical algorithm to Approach 1 but written with explicit three-phase structure. More verbose but clarifies the three distinct merge phases.

⏱ Time O(n) Three single-pass loops 💾 Space O(n)

Pseudocode

function insert(intervals, newInterval):
    result = []
    i = 0
    newStart, newEnd = newInterval

    // Phase 1: Add intervals ending before new interval starts
    while i < len(intervals) and intervals[i][1] < newStart:
        result.append(intervals[i])
        i += 1

    // Phase 2: Merge overlapping intervals
    while i < len(intervals) and intervals[i][0] <= newEnd:
        newStart = min(newStart, intervals[i][0])
        newEnd = max(newEnd, intervals[i][1])
        i += 1
    result.append([newStart, newEnd])

    // Phase 3: Append remaining non-overlapping intervals
    while i < len(intervals):
        result.append(intervals[i])
        i += 1

    return result

Solution Code

Python

insert_interval_iterative.py

from typing import List

def insert(intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
    """Iterative approach: O(n) time, O(n) space"""
    result = []
    for interval in intervals:
        if interval[1] < newInterval[0]:
            result.append(interval)
        elif interval[0] > newInterval[1]:
            result.append(newInterval)
            newInterval = interval
        else:
            newInterval[0] = min(newInterval[0], interval[0])
            newInterval[1] = max(newInterval[1], interval[1])
    result.append(newInterval)
    return result

C++

insert_interval_iterative.cpp

#include <vector>
using namespace std;

vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
    vector<vector<int>> result;
    for (auto& interval : intervals) {
        if (interval[1] < newInterval[0]) {
            result.push_back(interval);
        } else if (interval[0] > newInterval[1]) {
            result.push_back(newInterval);
            newInterval = interval;
        } else {
            newInterval[0] = min(newInterval[0], interval[0]);
            newInterval[1] = max(newInterval[1], interval[1]);
        }
    }
    result.push_back(newInterval);
    return result;
}

Java

InsertIntervalIterative.java

import java.util.*;

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> result = new ArrayList<>();
        int i = 0;
        int newStart = newInterval[0];
        int newEnd = newInterval[1];

        // Phase 1: Add all intervals that end before newInterval starts
        while (i < intervals.length && intervals[i][1] < newStart) {
            result.add(intervals[i]);
            i++;
        }

        // Phase 2: Merge all overlapping intervals
        while (i < intervals.length && intervals[i][0] <= newEnd) {
            newStart = Math.min(newStart, intervals[i][0]);
            newEnd = Math.max(newEnd, intervals[i][1]);
            i++;
        }
        result.add(new int[]{newStart, newEnd});

        // Phase 3: Add remaining intervals
        while (i < intervals.length) {
            result.add(intervals[i]);
            i++;
        }

        return result.toArray(new int[result.size()][]);
    }
}

JavaScript

insert_interval_iterative.js

function insert(intervals, newInterval) {
    const result = [];
    for (const interval of intervals) {
        if (interval[1] < newInterval[0]) {
            result.push(interval);
        } else if (interval[0] > newInterval[1]) {
            result.push([...newInterval]);
            newInterval = interval;
        } else {
            newInterval[0] = Math.min(newInterval[0], interval[0]);
            newInterval[1] = Math.max(newInterval[1], interval[1]);
        }
    }
    result.push(newInterval);
    return result;
}

Rust

insert_interval_iterative.rs

pub fn insert(intervals: Vec<Vec<i32>>, mut newInterval: Vec<i32>) -> Vec<Vec<i32>> {
    let mut result = vec![];
    for interval in intervals {
        if interval[1] < newInterval[0] {
            result.push(interval);
        } else if interval[0] > newInterval[1] {
            result.push(newInterval);
            newInterval = interval;
        } else {
            newInterval[0] = newInterval[0].min(interval[0]);
            newInterval[1] = newInterval[1].max(interval[1]);
        }
    }
    result.push(newInterval);
    result
}

Go

insert_interval_iterative.go

package main

func insert(intervals [][]int, newInterval []int) [][]int {
    result := [][]int{}
    for _, interval := range intervals {
        if interval[1] < newInterval[0] {
            result = append(result, interval)
        } else if interval[0] > newInterval[1] {
            result = append(result, newInterval)
            newInterval = interval
        } else {
            if interval[0] < newInterval[0] { newInterval[0] = interval[0] }
            if interval[1] > newInterval[1] { newInterval[1] = interval[1] }
        }
    }
    result = append(result, newInterval)
    return result
}

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

insert_interval_space_optimized.py

"""
Solution for Insert Interval
"""

def solve():
    """Implementation for approach 3 of Insert Interval"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

insert_interval_space_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Insert Interval
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

InsertIntervalSpaceOptimized.java

/**
 * Solution for Insert Interval
 * Approach 3
 */
public class InsertIntervalSpaceOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

insert_interval_space_optimized.js

/**
 * Solution for Insert Interval
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

insert_interval_space_optimized.rs

/// Solution for Insert Interval
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

insert_interval_space_optimized.go

package main

import "fmt"

// Solution for Insert Interval
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Common Mistakes

Watch for these pitfalls

• Sorting the result: The input is already sorted, so never sort again—it wastes O(n log n).
• Off-by-one errors in phase boundaries: Ensure intervals[i][1] < newStart (strictly less) and intervals[i][0] <= newEnd (less or equal).
• Not updating newStart during merge: Always take the minimum start; it expands the merged interval.
• Forgetting to check phase 1 condition: If phase 1 loop is skipped, newInterval should still be added.

Interview Tips

Key trade-offs to discuss

• Why three phases? Breaking into phases makes logic clear and avoids re-sorting.
• Can you do this without modifying the list? Yes, but you’d still need O(n) space for the result.
• What if intervals overlapped in the input? Merge them first (LeetCode 56), then insert.
• What if newInterval is already in the list? The algorithm handles it naturally by merging.