Insert interval

You're sitting in a Google phone screen when the interviewer asks: "Given a sorted list of non-overlapping intervals and a new interval, insert it so the list stays sorted and non-overlapping." You've seen merge intervals before, but this twist, a pre-sorted list and a single insertion, calls for a different approach. This problem is a favorite at Google, Amazon, and Twitter because it tests whether you can recognize a greedy single-pass opportunity instead of reaching for a heavier sorting-based solution.

TL;DR

Iterate through the sorted intervals once. For each interval, check three conditions: if it ends before the insert starts, add it directly; if it starts after the insert ends, add the insert and swap; otherwise, merge by expanding the insert to cover both. After the loop, add whatever insert holds. This runs in O(n) time and O(n) space.

Why This Problem Matters

Insert interval sits at the intersection of array manipulation and greedy algorithms. It shows up regularly in 2026 interviews because it rewards candidates who think carefully about boundary conditions rather than brute-forcing a sort-and-merge approach. If you've already tackled merge intervals, this problem reinforces the same merging logic with the added twist that the input is pre-sorted, which should simplify your solution, not complicate it.

Understanding the Problem

Given: A sorted list of non-overlapping intervals and one new interval to insert. Goal: Return a new list of non-overlapping intervals with the new interval merged in, maintaining sorted order.

Here's the test case from the problem:

insertInterval([[1,4],[7,9]], [2,6]) -> [[1,6],[7,9]]
insertInterval([[0,1],[4,5]], [2,3]) -> [[0,1],[2,3],[4,5]]

The first call merges [2,6] with [1,4] because they overlap (the end of [1,4] is 4, which is >= the start of [2,6] which is 2). The second call inserts [2,3] between [0,1] and [4,5] with no merging needed.

The Three Relationships

Every existing interval has exactly one of three relationships to the insert interval:

1. Before: The existing interval ends before the insert starts. No overlap, add it to the output as-is.
2. Overlap: The intervals intersect. Merge them by expanding the insert to cover both.
3. After: The existing interval starts after the insert ends. The insert goes into the output first, and the current interval becomes the new "insert" for subsequent processing.

This three-way classification is the core idea. Everything else follows from it.

Edge Cases

• Empty intervals list: No comparisons, just return the insert interval.
• Insert before everything: The insert ends before the first interval starts.
• Insert after everything: The insert starts after the last interval ends.
• Insert contained within an existing interval: The merge produces the original interval unchanged.
• Insert absorbs all intervals: Every interval overlaps, producing one large merged interval.

Solution Approach

Because the intervals are already sorted, we can process them left-to-right in a single pass. There's no need to sort or use a heap. At each step, we classify the current interval into one of the three cases and take the appropriate action.

The clever part of this algorithm is the "swap trick" in Case 3. When we encounter an interval that comes entirely after the insert, we add the insert to the output and then reassign insert to point to the current interval. This means the final out.add(insert) after the loop always adds the correct trailing interval, regardless of whether any merging happened.

Tracing Through the Primary Example

For intervals = [[1,4],[7,9]] and insert = [2,6]:

Step 1: Compare [1,4] with insert = [2,6]. Is 4 < 2? No. Is 1 > 6? No. So they overlap. Merge: insert = [min(2,1), max(6,4)] = [1,6].

Step 2: Compare [7,9] with insert = [1,6]. Is 9 < 1? No. Is 7 > 6? Yes, so [7,9] comes after insert. Add [1,6] to output, set insert = [7,9].

After loop: Add insert = [7,9] to output. Result: [[1,6],[7,9]].

A Multi-Merge Example

For intervals = [[1,2],[3,5],[6,7],[8,10],[12,14]] and insert = [5,9]:

The insert interval [5,9] overlaps with [3,5], [6,7], and [8,10], absorbing all three into one merged interval [3,10]. Intervals [1,2] and [12,14] pass through untouched.

No-Overlap Insertion

For intervals = [[0,1],[4,5]] and insert = [2,3]:

The insert fits cleanly between the two existing intervals. The swap trick places [2,3] in the output when [4,5] triggers the "after" case, then [4,5] gets added after the loop.

Implementation

Prefer a different language? Jump to solutions in other languages.

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Solution {
  public List<List<Integer>> insertInterval(
    List<List<Integer>> intervals,
    List<Integer> insert
  ) {
    LinkedList<List<Integer>> out = new LinkedList<>();

    for (List<Integer> interval : intervals) {
      if (interval.get(1) < insert.get(0)) {
        // Case 1: current interval ends before insert starts
        out.add(interval);
      } else if (interval.get(0) > insert.get(1)) {
        // Case 3: current interval starts after insert ends
        out.add(insert);
        insert = interval;
      } else {
        // Case 2: overlap, merge into insert
        int start = Math.min(insert.get(0), interval.get(0));
        int end = Math.max(insert.get(1), interval.get(1));
        insert = Arrays.asList(start, end);
      }
    }

    // Add whatever insert holds (either the merged interval or the last swapped interval)
    out.add(insert);
    return out;
  }
}

The loop body is just three branches, each doing a small, obvious operation. No index tracking, no nested loops, no sorting. The insert variable acts as a running accumulator that absorbs overlapping intervals as we scan left to right.

Why LinkedList and Not ArrayList?

A LinkedList is used here because we only ever append to the end. In practice, an ArrayList would work just as well for this problem since both have amortized O(1) appends. The choice is stylistic, not algorithmic.

Handling Edge Cases

Empty Intervals List

When intervals is empty, the loop body never executes. The final out.add(insert) adds the insert interval as the only element. No special-case code needed.

Insert Fully Contained

When insert = [1,2] is fully inside [0,5], the overlap branch fires and merges them into [min(1,0), max(2,5)] = [0,5]. The result is identical to the original interval.

Complexity Analysis

Time: O(n)

Each interval is visited exactly once. The comparison and potential merge at each step are O(1) operations. Appending to the output list is amortized O(1). Total work: O(n) where n is the number of intervals.

Space: O(n)

The output list stores at most n + 1 intervals (all originals plus the inserted one, if no merging occurs). In the worst case where every interval merges with the insert, the output holds fewer intervals but still scales linearly.

Comparison with Merge Intervals

Common Pitfalls

1. Forgetting the final append: After the loop, insert still holds either the merged interval or the last swapped interval. Omitting out.add(insert) loses the final element every time.

2. Checking overlap before checking "before" and "after": Overlap detection requires checking that neither the "before" nor "after" condition holds. If you try to detect overlap directly, you'll write more complex conditions. Checking the two non-overlapping cases first and using else for overlap is cleaner.

3. Not handling the swap in the "after" case: When an interval falls entirely after the insert, you need to add the insert to the output and reassign insert to the current interval. Forgetting the reassignment means the current interval is lost.

4. Mutating the input list: Some implementations try to insert and remove elements from the input list directly. This leads to index management issues and is harder to get right. Building a new output list is simpler.

Interview Tips

When you get this problem in an interview, start by confirming the constraints: the intervals are sorted and non-overlapping. These two properties are what make the single-pass approach possible.

Walk through the three cases on a whiteboard before writing code. Draw the intervals as horizontal bars on a number line and show how the insert can land before, overlap with, or come after each one. Interviewers like to see that you understand the geometry of the problem before diving into implementation.

If you're asked about follow-ups, common ones include:

• "What if the intervals aren't sorted?" (Sort first, then apply the same logic, making it O(n log n).)
• "What if you need to insert multiple intervals?" (Either insert one at a time, or merge all intervals together from scratch.)
• "Can you do this without extra space?" (Not cleanly; the new-list approach is preferred.)

Key Takeaways

• The three-case classification (before, overlap, after) is the foundation of this algorithm. Recognizing that sorted input enables a single-pass greedy approach is the main insight.
• The swap trick in the "after" case eliminates the need for a separate post-loop check or index tracking. Whatever insert holds at the end of the loop is always the right interval to append.
• Merging uses min for the start and max for the end. This handles partial overlaps, full containment, and exact boundary matches uniformly.
• Building a new output list instead of modifying the input avoids index management bugs and is the standard approach interviewers expect.
• Test with an empty list, no-overlap insertion, single-merge, multi-merge, and full-containment cases to cover all branches of the algorithm.

Related Problems and Practice

Once you're comfortable with insert interval, try these related problems to build your interval manipulation skills:

• Merge Intervals - handles unsorted, overlapping intervals with a sort-first approach
• Meeting Rooms - checks whether a person can attend all meetings given time intervals
• Interval List Intersections - finds the intersection of two sorted interval lists

Consistent practice with interval problems builds the pattern recognition needed for 2026 technical interviews. This problem and hundreds of others are available on Firecode, where over 50,000 users have prepared for interviews at companies like Google, Amazon, and Twitter.

Happy coding!

Solutions in Other Languages

Python

from typing import List


class Solution:
    def insert_interval(self,
                        intervals: List[List[int]],
                        insert: List[int]) -> List[List[int]]:
        out = []
        for interval in intervals:
            if interval[1] < insert[0]:
                out.append(interval)
            elif interval[0] > insert[1]:
                out.append(insert)
                insert = interval
            else:
                start = min(insert[0], interval[0])
                end = max(insert[1], interval[1])
                insert = [start, end]

        out.append(insert)
        return out

JavaScript

class Solution {
  insertInterval(intervals, insert) {
    const out = [];
    for (let i = 0; i < intervals.length; i++) {
      const interval = intervals[i];
      if (interval[1] < insert[0]) out.push(interval);
      else if (interval[0] > insert[1]) {
        out.push(insert);
        insert = interval;
      } else {
        const start = Math.min(insert[0], interval[0]);
        const end = Math.max(insert[1], interval[1]);
        insert = [start, end];
      }
    }
    out.push(insert);
    return out;
  }
}

TypeScript

class Solution {
  insertInterval(intervals: number[][], insert: number[]): number[][] {
    const out: number[][] = [];
    for (let i = 0; i < intervals.length; i++) {
      const interval = intervals[i];
      if (interval[1] < insert[0]) out.push(interval);
      else if (interval[0] > insert[1]) {
        out.push(insert);
        insert = interval;
      } else {
        const start = Math.min(insert[0], interval[0]);
        const end = Math.max(insert[1], interval[1]);
        insert = [start, end];
      }
    }
    out.push(insert);
    return out;
  }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>

class Solution {
public:
  std::vector<std::vector<int>> insertInterval(
      std::vector<std::vector<int>> &intervals,
      std::vector<int> &insert
  ) {
    std::vector<std::vector<int>> out;

    for (auto &interval : intervals) {
      if (interval[1] < insert[0]) {
        out.push_back(interval);
      } else if (interval[0] > insert[1]) {
        out.push_back(insert);
        insert = interval;
      } else {
        insert[0] = std::min(insert[0], interval[0]);
        insert[1] = std::max(insert[1], interval[1]);
      }
    }

    out.push_back(insert);
    return out;
  }
};

Note that the C++ version modifies insert in-place during merges rather than creating a new vector each time, which avoids unnecessary allocations.

Go

package solution

func (s *Solution) InsertInterval(intervals [][]int, insert []int) [][]int {
	out := make([][]int, 0)

	for _, interval := range intervals {
		if interval[1] < insert[0] {
			out = append(out, interval)
		} else if interval[0] > insert[1] {
			out = append(out, insert)
			insert = interval
		} else {
			insert[0] = min(insert[0], interval[0])
			insert[1] = max(insert[1], interval[1])
		}
	}

	out = append(out, insert)
	return out
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

Go requires explicit min/max helper functions (prior to Go 1.21, which added built-in min and max).

Scala

import scala.collection.mutable

class Solution {
  def insertInterval(
    intervals: List[List[Int]], insert: List[Int]
  ): List[List[Int]] = {
    var ins = insert
    val out = mutable.ListBuffer[List[Int]]()
    for (interval <- intervals) {
      if (interval(1) < ins.head) out.append(interval)
      else if (interval.head > ins(1)) {
        out.append(ins)
        ins = interval
      } else {
        val start = Math.min(ins.head, interval.head)
        val end = Math.max(ins(1), interval(1))
        ins = List(start, end)
      }
    }
    out.append(ins)
    out.toList
  }
}

Kotlin

class Solution {
  fun insertInterval(
    intervals: List<List<Int>>,
    insert: List<Int>
  ): List<List<Int>> {
    val out = mutableListOf<List<Int>>()
    var newInsert = insert
    for (interval in intervals) {
      if (interval[1] < newInsert[0]) {
        out.add(interval)
      } else if (interval[0] > newInsert[1]) {
        out.add(newInsert)
        newInsert = interval
      } else {
        val start = minOf(newInsert[0], interval[0])
        val end = maxOf(newInsert[1], interval[1])
        newInsert = listOf(start, end)
      }
    }
    out.add(newInsert)
    return out
  }
}

Swift

import Foundation

class Solution {
    func insertInterval(_ intervals: [[Int]], _ insert: [Int]) -> [[Int]] {
        var out: [[Int]] = []
        var newInsert = insert
        for interval in intervals {
            if interval[1] < newInsert[0] {
                out.append(interval)
            } else if interval[0] > newInsert[1] {
                out.append(newInsert)
                newInsert = interval
            } else {
                newInsert = [min(newInsert[0], interval[0]), max(newInsert[1], interval[1])]
            }
        }
        out.append(newInsert)
        return out
    }
}

Ruby

class Solution
  def insert_interval(intervals, insert)
    out = []
    intervals.each do |interval|
      if interval[1] < insert[0]
        out << interval
      elsif interval[0] > insert[1]
        out << insert
        insert = interval
      else
        start_val = [insert[0], interval[0]].min
        end_val = [insert[1], interval[1]].max
        insert = [start_val, end_val]
      end
    end
    out << insert
    out
  end
end

Rust

pub struct Solution;

impl Solution {
    pub fn insert_interval(&self, intervals: Vec<Vec<i32>>, insert: Vec<i32>) -> Vec<Vec<i32>> {
        let mut out: Vec<Vec<i32>> = Vec::new();
        let mut insert = insert;
        for interval in &intervals {
            if interval[1] < insert[0] {
                out.push(interval.clone());
            } else if interval[0] > insert[1] {
                out.push(insert);
                insert = interval.clone();
            } else {
                let start = insert[0].min(interval[0]);
                let end = insert[1].max(interval[1]);
                insert = vec![start, end];
            }
        }
        out.push(insert);
        out
    }
}

Rust requires explicit ownership handling. The insert variable is reassigned by value on each merge or swap, and existing intervals are cloned when moved into the output vector.

C#

public class Solution {
    public List<List<int>> InsertInterval(List<List<int>> intervals, List<int> insert) {
        var output = new List<List<int>>();
        foreach (var interval in intervals) {
            if (interval[1] < insert[0]) output.Add(interval);
            else if (interval[0] > insert[1]) {
                output.Add(insert);
                insert = interval;
            } else {
                int start = Math.Min(insert[0], interval[0]);
                int end = Math.Max(insert[1], interval[1]);
                insert = new List<int> { start, end };
            }
        }
        output.Add(insert);
        return output;
    }
}

Dart

import 'dart:math';

class Solution {
  List<List<int>> insertInterval(
    List<List<int>> intervals,
    List<int> insert,
  ) {
    List<List<int>> out = [];
    var newInsert = insert;
    for (List<int> interval in intervals) {
      if (interval[1] < newInsert[0]) {
        out.add(interval);
      } else if (interval[0] > newInsert[1]) {
        out.add(newInsert);
        newInsert = interval;
      } else {
        int start = min(newInsert[0], interval[0]);
        int end = max(newInsert[1], interval[1]);
        newInsert = [start, end];
      }
    }
    out.add(newInsert);
    return out;
  }
}

PHP

<?php

class Solution {
    public function insertInterval(array $intervals, array $insert): array {
        $out = [];
        foreach ($intervals as $interval) {
            if ($interval[1] < $insert[0]) $out[] = $interval;
            elseif ($interval[0] > $insert[1]) {
                $out[] = $insert;
                $insert = $interval;
            } else {
                $insert = [min($insert[0], $interval[0]), max($insert[1], $interval[1])];
            }
        }
        $out[] = $insert;
        return $out;
    }
}