Insert Interval — Solution in C++, Java, Python, Go

You are given an array of non-overlapping intervals intervals where intervals[i] = [start_i, end_i] represent the start and end of the ith interval, and intervals is sorted in ascending order by start_i. You are also given an interval newInterval = [start, end] that represents the interval to be inserted.

Insert newInterval into intervals such that intervals is still sorted in ascending order by start_i and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

Note that you don't need to modify intervals in-place. You can make a new array and return it.

Examples

Example 1

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Explanation: The new interval [2,5] overlaps with [1,3], so they are merged into [1,5].

Example 2

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: The new interval [4,8] overlaps with [3,5], [6,7], and [8,10], so they are all merged into [3,10].

Example 3

Input: intervals = [], newInterval = [5,7]
Output: [[5,7]]

Constraints

0 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= start_i <= end_i <= 10^5
intervals is sorted by start_i in ascending order.
newInterval.length == 2
0 <= start <= end <= 10^5

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Linear Scan

Intuition

Since the intervals are already sorted and non-overlapping, we can solve this in a single pass. We iterate through the intervals and classify each one into three groups: intervals that come entirely before the new interval, intervals that overlap with the new interval, and intervals that come entirely after. Non-overlapping intervals before are added directly. Overlapping intervals are merged with the new interval by taking the minimum start and maximum end. Non-overlapping intervals after are added directly. This clean three-phase approach handles all cases elegantly.

Algorithm

Initialize an empty result list.
Iterate through `intervals`. For each interval:
After the loop, if `newInterval` has not been added, append it to the result.
Return the result.

TimeO(n)SpaceO(n)

Code (C++ · Java · Python · Go)

C++17

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> result;
        int i = 0;
        int n = intervals.size();

        // Add all intervals that come before newInterval
        while (i < n && intervals[i][1] < newInterval[0]) {
            result.push_back(intervals[i]);
            i++;
        }

        // Merge overlapping intervals with newInterval
        while (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.push_back(newInterval);

        // Add all intervals that come after newInterval
        while (i < n) {
            result.push_back(intervals[i]);
            i++;
        }

        return result;
    }
};

Java 21

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> result = new ArrayList<>();
        int i = 0;
        int n = intervals.length;

        // Add all intervals that come before newInterval
        while (i < n && intervals[i][1] < newInterval[0]) {
            result.add(intervals[i]);
            i++;
        }

        // Merge overlapping intervals with newInterval
        while (i < n && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
            newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
            i++;
        }
        result.add(newInterval);

        // Add all intervals that come after newInterval
        while (i < n) {
            result.add(intervals[i]);
            i++;
        }

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

Python 3.12

def insert(intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
    result = []
    i = 0
    n = len(intervals)

    # Add all intervals that come before newInterval
    while i < n and intervals[i][1] < newInterval[0]:
        result.append(intervals[i])
        i += 1

    # Merge overlapping intervals with newInterval
    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)

    # Add all intervals that come after newInterval
    while i < n:
        result.append(intervals[i])
        i += 1

    return result

Go 1.26

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

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

    // Merge overlapping intervals with newInterval
    for i < n && intervals[i][0] <= newInterval[1] {
        if intervals[i][0] < newInterval[0] {
            newInterval[0] = intervals[i][0]
        }
        if intervals[i][1] > newInterval[1] {
            newInterval[1] = intervals[i][1]
        }
        i++
    }
    result = append(result, newInterval)

    // Add all intervals that come after newInterval
    for i < n {
        result = append(result, intervals[i])
        i++
    }

    return result
}

Approach 2

Binary Search + Merge

Intuition

We can use binary search to quickly find the insertion point and the range of overlapping intervals, rather than scanning linearly. First, binary search for the first interval whose end is >= newInterval's start (left boundary). Then binary search for the last interval whose start is <= newInterval's end (right boundary). All intervals between these two indices overlap with the new interval and must be merged. Everything before and after can be kept as-is. While the overall complexity remains O(n) due to the output construction, this approach minimizes comparisons.

Algorithm

Binary search for the leftmost index `left` where `intervals[left][1] >= newInterval[0]`.
Binary search for the rightmost index `right` where `intervals[right][0] <= newInterval[1]`.
If `left > right`, no overlaps exist. Insert `newInterval` at position `left`.
Otherwise, merge all intervals from `left` to `right` with `newInterval` by taking the min of starts and max of ends.
Build the result: intervals before `left`, the merged interval, intervals after `right`.

TimeO(n)SpaceO(n)

Code (C++ · Java · Python · Go)

C++17

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        int n = intervals.size();
        // Find left: first interval with end >= newInterval[0]
        int left = lower_bound(intervals.begin(), intervals.end(), newInterval[0],
            [](const vector<int>& interval, int val) {
                return interval[1] < val;
            }) - intervals.begin();

        // Find right: last interval with start <= newInterval[1]
        int right = upper_bound(intervals.begin(), intervals.end(), newInterval[1],
            [](int val, const vector<int>& interval) {
                return val < interval[0];
            }) - intervals.begin() - 1;

        vector<vector<int>> result;
        for (int i = 0; i < left; i++) {
            result.push_back(intervals[i]);
        }

        if (left <= right) {
            newInterval[0] = min(newInterval[0], intervals[left][0]);
            newInterval[1] = max(newInterval[1], intervals[right][1]);
        }
        result.push_back(newInterval);

        for (int i = right + 1; i < n; i++) {
            result.push_back(intervals[i]);
        }

        return result;
    }
};

Java 21

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int n = intervals.length;
        // Find left: first interval with end >= newInterval[0]
        int left = 0, right = n - 1;
        int lo = 0, hi = n;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (intervals[mid][1] < newInterval[0]) lo = mid + 1;
            else hi = mid;
        }
        left = lo;

        // Find right: last interval with start <= newInterval[1]
        lo = 0;
        hi = n;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (intervals[mid][0] <= newInterval[1]) lo = mid + 1;
            else hi = mid;
        }
        right = lo - 1;

        List<int[]> result = new ArrayList<>();
        for (int i = 0; i < left; i++) {
            result.add(intervals[i]);
        }

        if (left <= right) {
            newInterval[0] = Math.min(newInterval[0], intervals[left][0]);
            newInterval[1] = Math.max(newInterval[1], intervals[right][1]);
        }
        result.add(newInterval);

        for (int i = right + 1; i < n; i++) {
            result.add(intervals[i]);
        }

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

Python 3.12

import bisect

def insert(intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
    n = len(intervals)
    # Find left: first interval with end >= newInterval[0]
    left = bisect.bisect_left([iv[1] for iv in intervals], newInterval[0])
    # Find right: last interval with start <= newInterval[1]
    right = bisect.bisect_right([iv[0] for iv in intervals], newInterval[1]) - 1

    result = intervals[:left]

    if left <= right:
        newInterval = [
            min(newInterval[0], intervals[left][0]),
            max(newInterval[1], intervals[right][1]),
        ]
    result.append(newInterval)

    result.extend(intervals[right + 1:])

    return result

Go 1.26

import "sort"

func insert(intervals [][]int, newInterval []int) [][]int {
    n := len(intervals)
    // Find left: first interval with end >= newInterval[0]
    left := sort.Search(n, func(i int) bool {
        return intervals[i][1] >= newInterval[0]
    })
    // Find right: last interval with start <= newInterval[1]
    right := sort.Search(n, func(i int) bool {
        return intervals[i][0] > newInterval[1]
    }) - 1

    result := make([][]int, 0)
    result = append(result, intervals[:left]...)

    if left <= right {
        if intervals[left][0] < newInterval[0] {
            newInterval[0] = intervals[left][0]
        }
        if intervals[right][1] > newInterval[1] {
            newInterval[1] = intervals[right][1]
        }
    }
    result = append(result, newInterval)

    if right+1 < n {
        result = append(result, intervals[right+1:]...)
    }

    return result
}

Frequently asked questions

What is the optimal time complexity of Insert Interval?

The most efficient approach in this guide ("Binary Search + Merge") runs in O(n) time and uses O(n) extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Insert Interval use?

Insert Interval is a medium-level Intervals problem involving Array, Interval. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Insert Interval be solved without extra space?

The most space-efficient approach in this guide uses O(n) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(n), while the optimized version uses O(n).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Original problem: leetcode.com

Loading editor...

Input

intervals=

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

newInterval=

[2,5]

Expected Output

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