Insert Interval

Problem

Given a non-overlapping list of intervals sorted by start, insert a new interval and merge if necessary. Return the resulting list.

Constraints

• 0 ≤ intervals.length ≤ 10⁴
• intervals sorted by start, non-overlapping

Approach — Core Patterns

This is a Core Patterns problem. The idea: pick the data structure best matched to the constraints and solve it in one clean pass. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: see the walkthrough below.

Solution code

Python

class Solution:
    def insert(self, intervals, newInterval):
        res = []
        s, e = newInterval
        i, n = 0, len(intervals)
        while i < n and intervals[i][1] < s:
            res.append(intervals[i]); i += 1
        while i < n and intervals[i][0] <= e:
            s = min(s, intervals[i][0]); e = max(e, intervals[i][1]); i += 1
        res.append([s, e])
        while i < n:
            res.append(intervals[i]); i += 1
        return res

Java

import java.util.*;

class Solution {
    public int[][] insert(int[][] intervals, int[] ni) {
        List<int[]> out = new ArrayList<>();
        int i = 0, n = intervals.length;
        while (i < n && intervals[i][1] < ni[0]) out.add(intervals[i++]);
        while (i < n && intervals[i][0] <= ni[1]) {
            ni[0] = Math.min(ni[0], intervals[i][0]);
            ni[1] = Math.max(ni[1], intervals[i][1]);
            i++;
        }
        out.add(ni);
        while (i < n) out.add(intervals[i++]);
        return out.toArray(new int[out.size()][]);
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.