#64 · Intervals

Insert Interval

Given sorted, non-overlapping intervals and a new interval, insert the new interval and merge any overlaps, returning a sorted list of non-overlapping intervals.

MediumLeetCode

Being examined
New / inserted
Kept / merged / answer
Removed / conflict
Untouched

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Sorted disjoint intervals

Because the input is sorted and non-overlapping, the intervals that touch the new one form one contiguous block: everything before it ends too early, everything after it starts too late. The merged interval has the minimum of the starts and the maximum of the ends of that block.

Memory layout

An array of [start, end] pairs in order.

Operation	Cost
linear scan	O(n)
find the block with binary search	O(log n), plus O(n) to copy the result

Why it fits

The input order already does the sorting work, so there is no need to sort again: one pass suffices.
Overlap is simple to test: two intervals overlap exactly when neither ends before the other starts.
Because only the first and last overlapping intervals can extend the merged range, a binary search for the block boundaries is enough.

Why alternatives degrade

Append and re-sort:: Correct, but it ignores the existing order and costs O(n log n) instead of O(n).
Checking every pair:: Quadratic work, although the sorted order makes overlaps contiguous.
Interval tree:: Helpful when many inserts and queries happen on the same data, but heavy for a single insert.

Four approaches, from naive to production

1 · beginner

Append, sort, then merge

time O(n log n)space O(n)

Add the new interval to the list, sort everything by start, and run the standard merge pass over it.

vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
    vector<vector<int>> all = intervals; all.push_back(newInterval); sort(all.begin(), all.end());
    vector<vector<int>> result;
    for (auto& iv : all) {
        int start = iv[0], end = iv[1];
        vector<int>* last = result.empty() ? nullptr : &result.back();
        if (last != nullptr && start <= (*last)[1]) (*last)[1] = max((*last)[1], end);
        else result.push_back({start, end});
    }
    return result;
}

public int[][] insert(int[][] intervals, int[] newInterval) {
    List<int[]> all = new ArrayList<>();
    for (int[] iv : intervals) all.add(iv);
    all.add(newInterval);
    all.sort((a, b) -> a[0] - b[0]);
    List<int[]> result = new ArrayList<>();
    for (int[] iv : all) {
        int start = iv[0], end = iv[1];
        int[] last = result.isEmpty() ? null : result.get(result.size() - 1);
        if (last != null && start <= last[1]) last[1] = Math.max(last[1], end);
        else result.add(new int[]{start, end});
    }
    return result.toArray(new int[0][]);
}

def insert(intervals, new_interval):
    all_iv = sorted(intervals + [new_interval], key=lambda p: p[0])
    result = []
    for start, end in all_iv:
        last = result[-1] if result else None
        if last is not None and start <= last[1]: last[1] = max(last[1], end)
        else: result.append([start, end])
    return result

function insert(intervals: number[][], newInterval: number[]): number[][] {
  const all = [...intervals, newInterval].sort((a, b) => a[0] - b[0]);
  const result: number[][] = [];
  for (const [start, end] of all) {
    const last = result[result.length - 1];
    if (last !== undefined && start <= last[1]) last[1] = Math.max(last[1], end);
    else result.push([start, end]);
  }
  return result;
}

Flaws & bottlenecks

Discards the fact that the input is already sorted.
Allocates a new sorted list and a result list.
The sort dominates the cost.

Interviewer cross-questions

What information are you ignoring?

Say: The input is sorted and disjoint. That means the new interval only interacts with a contiguous block, so no sort is needed.

Is this ever the right answer?

Say: For a quick prototype or when the input is not guaranteed to be sorted, yes. It reuses a merge routine you already have.

How do you remove the sort?

Say: Walk the list once: copy intervals before the new one, merge the overlapping ones, copy the rest.

2 · intermediate

Three phases: before, overlap, after

time O(n)space O(n) for the result

One index and three while loops: copy intervals that end before the new one starts, merge all intervals that start no later than the merged end, then copy the rest.

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

public int[][] insert(int[][] intervals, int[] newInterval) {
    List<int[]> result = new ArrayList<>();
    int i = 0;
    int n = intervals.length;
    while (i < n && intervals[i][1] < newInterval[0]) {
        result.add(intervals[i]);
        i++;
    }
    int start = newInterval[0], end = newInterval[1];
    while (i < n && intervals[i][0] <= end) {
        start = Math.min(start, intervals[i][0]);
        end = Math.max(end, intervals[i][1]);
        i++;
    }
    result.add(new int[]{start, end});
    while (i < n) {
        result.add(intervals[i]);
        i++;
    }
    return result.toArray(new int[0][]);
}

def insert(intervals, new_interval):
    result = []
    i = 0
    n = len(intervals)
    while i < n and intervals[i][1] < new_interval[0]:
        result.append(intervals[i])
        i += 1
    start, end = new_interval
    while i < n and intervals[i][0] <= end:
        start = min(start, intervals[i][0])
        end = max(end, intervals[i][1])
        i += 1
    result.append([start, end])
    while i < n:
        result.append(intervals[i])
        i += 1
    return result

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

Flaws & bottlenecks

Three loops sharing one index are easy to get wrong (off-by-one on the comparisons).
Still touches every interval even when the new one belongs at the very end.
The shared state (start, end) is spread across the middle loop.

Interviewer cross-questions

Why is the overlap test intervals[i][0] <= end?

Say: An interval overlaps the merged interval if it starts no later than the current merged end. The merged end grows as intervals are absorbed, so it is re-read on every iteration.

Why can the first loop use < and not <=?

Say: An interval that ends exactly where the new one starts touches it and must be merged, so only strictly earlier ends count as "before".

What if the new interval is entirely after all of them?

Say: The first loop copies everything, the second loop does nothing, and the new interval is appended: it works without a special case.

3 · advanced

One loop with three cases

time O(n)space O(n) for the result

For each interval: if it ends before the new one starts, keep it; if it starts after the new one ends, write the merged interval (once) and then the interval; otherwise absorb it into the new interval.

vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
    vector<vector<int>> result;
    int start = newInterval[0], end = newInterval[1];
    bool placed = false;
    for (auto& iv : intervals) {
        if (iv[1] < start) {
            result.push_back(iv);
        } else if (iv[0] > end) {
            if (!placed) {
                result.push_back({start, end});
                placed = true;
            }
            result.push_back(iv);
        } else {
            start = min(start, iv[0]);
            end = max(end, iv[1]);
        }
    }
    if (!placed) result.push_back({start, end});
    return result;
}

public int[][] insert(int[][] intervals, int[] newInterval) {
    List<int[]> result = new ArrayList<>();
    int start = newInterval[0], end = newInterval[1];
    boolean placed = false;
    for (int[] iv : intervals) {
        if (iv[1] < start) {
            result.add(iv);
        } else if (iv[0] > end) {
            if (!placed) {
                result.add(new int[]{start, end});
                placed = true;
            }
            result.add(iv);
        } else {
            start = Math.min(start, iv[0]);
            end = Math.max(end, iv[1]);
        }
    }
    if (!placed) result.add(new int[]{start, end});
    return result.toArray(new int[0][]);
}

def insert(intervals, new_interval):
    result = []
    start, end = new_interval
    placed = False
    for iv in intervals:
        if iv[1] < start:
            result.append(iv)
        elif iv[0] > end:
            if not placed:
                result.append([start, end])
                placed = True
            result.append(iv)
        else:
            start = min(start, iv[0])
            end = max(end, iv[1])
    if not placed: result.append([start, end])
    return result

function insert(intervals: number[][], newInterval: number[]): number[][] {
  const result: number[][] = [];
  let [start, end] = newInterval;
  let placed = false;
  for (const iv of intervals) {
    if (iv[1] < start) {
      result.push(iv);
    } else if (iv[0] > end) {
      if (!placed) {
        result.push([start, end]);
        placed = true;
      }
      result.push(iv);
    } else {
      start = Math.min(start, iv[0]);
      end = Math.max(end, iv[1]);
    }
  }
  if (!placed) result.push([start, end]);
  return result;
}

Flaws & bottlenecks

The placed flag is easy to forget, giving a missing or duplicated merged interval.
It still has to look at every interval.
Mixes three concerns in one loop, which is harder to read than the phase version.

Interviewer cross-questions

Why do you need the placed flag?

Say: The merged interval must be written exactly once, at the first interval that lies after it, or at the end if there is none.

What are the three cases?

Say: Entirely before the new interval, entirely after it, or overlapping it. These are exhaustive and exclusive for sorted disjoint input.

Can you avoid copying the untouched intervals?

Say: Only with an in-place structure (linked list or gap buffer). With an array, shifting costs as much as copying.

4 · expert

Binary search for the overlapping block

time O(log n) search + O(n) copyspace O(n) for the result

Binary-search the first interval that ends at or after the new start and the first interval that starts after the new end. Everything between them is replaced by one merged interval whose bounds come from just the first and last of them.

vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
    int n = intervals.size();
    int lo = 0, hi = n;
    while (lo < hi) {
        int mid = (lo + hi) >> 1;
        if (intervals[mid][1] < newInterval[0]) lo = mid + 1;
        else hi = mid;
    }
    int first = lo;
    hi = n;
    while (lo < hi) {
        int mid = (lo + hi) >> 1;
        if (intervals[mid][0] <= newInterval[1]) lo = mid + 1;
        else hi = mid;
    }
    int last = lo;
    int start = newInterval[0], end = newInterval[1];
    if (first < last) {
        start = min(start, intervals[first][0]);
        end = max(end, intervals[last - 1][1]);
    }
    vector<vector<int>> result(intervals.begin(), intervals.begin() + first);
    result.push_back({start, end});
    result.insert(result.end(), intervals.begin() + last, intervals.end());
    return result;
}

public int[][] insert(int[][] intervals, int[] newInterval) {
    int n = intervals.length;
    int lo = 0, hi = n;
    while (lo < hi) {
        int mid = (lo + hi) >> 1;
        if (intervals[mid][1] < newInterval[0]) lo = mid + 1;
        else hi = mid;
    }
    int first = lo;
    hi = n;
    while (lo < hi) {
        int mid = (lo + hi) >> 1;
        if (intervals[mid][0] <= newInterval[1]) lo = mid + 1;
        else hi = mid;
    }
    int last = lo;
    int start = newInterval[0], end = newInterval[1];
    if (first < last) {
        start = Math.min(start, intervals[first][0]);
        end = Math.max(end, intervals[last - 1][1]);
    }
    List<int[]> result = new ArrayList<>(Arrays.asList(intervals).subList(0, first));
    result.add(new int[]{start, end});
    result.addAll(Arrays.asList(intervals).subList(last, n));
    return result.toArray(new int[0][]);
}

def insert(intervals, new_interval):
    n = len(intervals)
    lo, hi = 0, n
    while lo < hi:
        mid = (lo + hi) >> 1
        if intervals[mid][1] < new_interval[0]: lo = mid + 1
        else: hi = mid
    first = lo
    hi = n
    while lo < hi:
        mid = (lo + hi) >> 1
        if intervals[mid][0] <= new_interval[1]: lo = mid + 1
        else: hi = mid
    last = lo
    start, end = new_interval
    if first < last:
        start = min(start, intervals[first][0])
        end = max(end, intervals[last - 1][1])
    result = intervals[:first] + [[start, end]] + intervals[last:]
    return result

function insert(intervals: number[][], newInterval: number[]): number[][] {
  const n = intervals.length;
  let lo = 0, hi = n;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (intervals[mid][1] < newInterval[0]) lo = mid + 1;
    else hi = mid;
  }
  const first = lo;
  hi = n;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (intervals[mid][0] <= newInterval[1]) lo = mid + 1;
    else hi = mid;
  }
  const last = lo;
  let start = newInterval[0], end = newInterval[1];
  if (first < last) {
    start = Math.min(start, intervals[first][0]);
    end = Math.max(end, intervals[last - 1][1]);
  }
  return [...intervals.slice(0, first), [start, end], ...intervals.slice(last)];
}

Flaws & bottlenecks

The copy of the output is still linear, so the end-to-end gain is small unless the data structure supports cheap splicing.
Two binary searches with different comparisons are easy to confuse.
Needs the input to be genuinely sorted and disjoint (otherwise the search gives wrong boundaries).

Interviewer cross-questions

When does this actually pay off?

Say: When the intervals live in a structure with O(log n) splice (a balanced tree or a skip list) and you perform many inserts: then each insert is O(log n) overall.

Why are only the first and last overlapping intervals needed for the bounds?

Say: The intervals are sorted and disjoint, so the first overlapping interval has the smallest start and the last has the largest end among the block.

What happens when nothing overlaps?

Say: first equals last, the merge keeps the new interval unchanged, and the slices put it at the right position.

Synchronized code walkthrough

Showing: Append, sort, then merge — shares the player above; click any step to jump.

vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
    vector<vector<int>> all = intervals; all.push_back(newInterval); sort(all.begin(), all.end());
    vector<vector<int>> result;
    for (auto& iv : all) {
        int start = iv[0], end = iv[1];
        vector<int>* last = result.empty() ? nullptr : &result.back();
        if (last != nullptr && start <= (*last)[1]) (*last)[1] = max((*last)[1], end);
        else result.push_back({start, end});
    }
    return result;
}

public int[][] insert(int[][] intervals, int[] newInterval) {
    List<int[]> all = new ArrayList<>();
    for (int[] iv : intervals) all.add(iv);
    all.add(newInterval);
    all.sort((a, b) -> a[0] - b[0]);
    List<int[]> result = new ArrayList<>();
    for (int[] iv : all) {
        int start = iv[0], end = iv[1];
        int[] last = result.isEmpty() ? null : result.get(result.size() - 1);
        if (last != null && start <= last[1]) last[1] = Math.max(last[1], end);
        else result.add(new int[]{start, end});
    }
    return result.toArray(new int[0][]);
}

def insert(intervals, new_interval):
    all_iv = sorted(intervals + [new_interval], key=lambda p: p[0])
    result = []
    for start, end in all_iv:
        last = result[-1] if result else None
        if last is not None and start <= last[1]: last[1] = max(last[1], end)
        else: result.append([start, end])
    return result

function insert(intervals: number[][], newInterval: number[]): number[][] {
  const all = [...intervals, newInterval].sort((a, b) => a[0] - b[0]);
  const result: number[][] = [];
  for (const [start, end] of all) {
    const last = result[result.length - 1];
    if (last !== undefined && start <= last[1]) last[1] = Math.max(last[1], end);
    else result.push([start, end]);
  }
  return result;
}

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

public int[][] insert(int[][] intervals, int[] newInterval) {
    List<int[]> result = new ArrayList<>();
    int i = 0;
    int n = intervals.length;
    while (i < n && intervals[i][1] < newInterval[0]) {
        result.add(intervals[i]);
        i++;
    }
    int start = newInterval[0], end = newInterval[1];
    while (i < n && intervals[i][0] <= end) {
        start = Math.min(start, intervals[i][0]);
        end = Math.max(end, intervals[i][1]);
        i++;
    }
    result.add(new int[]{start, end});
    while (i < n) {
        result.add(intervals[i]);
        i++;
    }
    return result.toArray(new int[0][]);
}

def insert(intervals, new_interval):
    result = []
    i = 0
    n = len(intervals)
    while i < n and intervals[i][1] < new_interval[0]:
        result.append(intervals[i])
        i += 1
    start, end = new_interval
    while i < n and intervals[i][0] <= end:
        start = min(start, intervals[i][0])
        end = max(end, intervals[i][1])
        i += 1
    result.append([start, end])
    while i < n:
        result.append(intervals[i])
        i += 1
    return result

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

vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
    vector<vector<int>> result;
    int start = newInterval[0], end = newInterval[1];
    bool placed = false;
    for (auto& iv : intervals) {
        if (iv[1] < start) {
            result.push_back(iv);
        } else if (iv[0] > end) {
            if (!placed) {
                result.push_back({start, end});
                placed = true;
            }
            result.push_back(iv);
        } else {
            start = min(start, iv[0]);
            end = max(end, iv[1]);
        }
    }
    if (!placed) result.push_back({start, end});
    return result;
}

public int[][] insert(int[][] intervals, int[] newInterval) {
    List<int[]> result = new ArrayList<>();
    int start = newInterval[0], end = newInterval[1];
    boolean placed = false;
    for (int[] iv : intervals) {
        if (iv[1] < start) {
            result.add(iv);
        } else if (iv[0] > end) {
            if (!placed) {
                result.add(new int[]{start, end});
                placed = true;
            }
            result.add(iv);
        } else {
            start = Math.min(start, iv[0]);
            end = Math.max(end, iv[1]);
        }
    }
    if (!placed) result.add(new int[]{start, end});
    return result.toArray(new int[0][]);
}

def insert(intervals, new_interval):
    result = []
    start, end = new_interval
    placed = False
    for iv in intervals:
        if iv[1] < start:
            result.append(iv)
        elif iv[0] > end:
            if not placed:
                result.append([start, end])
                placed = True
            result.append(iv)
        else:
            start = min(start, iv[0])
            end = max(end, iv[1])
    if not placed: result.append([start, end])
    return result

function insert(intervals: number[][], newInterval: number[]): number[][] {
  const result: number[][] = [];
  let [start, end] = newInterval;
  let placed = false;
  for (const iv of intervals) {
    if (iv[1] < start) {
      result.push(iv);
    } else if (iv[0] > end) {
      if (!placed) {
        result.push([start, end]);
        placed = true;
      }
      result.push(iv);
    } else {
      start = Math.min(start, iv[0]);
      end = Math.max(end, iv[1]);
    }
  }
  if (!placed) result.push([start, end]);
  return result;
}

vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
    int n = intervals.size();
    int lo = 0, hi = n;
    while (lo < hi) {
        int mid = (lo + hi) >> 1;
        if (intervals[mid][1] < newInterval[0]) lo = mid + 1;
        else hi = mid;
    }
    int first = lo;
    hi = n;
    while (lo < hi) {
        int mid = (lo + hi) >> 1;
        if (intervals[mid][0] <= newInterval[1]) lo = mid + 1;
        else hi = mid;
    }
    int last = lo;
    int start = newInterval[0], end = newInterval[1];
    if (first < last) {
        start = min(start, intervals[first][0]);
        end = max(end, intervals[last - 1][1]);
    }
    vector<vector<int>> result(intervals.begin(), intervals.begin() + first);
    result.push_back({start, end});
    result.insert(result.end(), intervals.begin() + last, intervals.end());
    return result;
}

public int[][] insert(int[][] intervals, int[] newInterval) {
    int n = intervals.length;
    int lo = 0, hi = n;
    while (lo < hi) {
        int mid = (lo + hi) >> 1;
        if (intervals[mid][1] < newInterval[0]) lo = mid + 1;
        else hi = mid;
    }
    int first = lo;
    hi = n;
    while (lo < hi) {
        int mid = (lo + hi) >> 1;
        if (intervals[mid][0] <= newInterval[1]) lo = mid + 1;
        else hi = mid;
    }
    int last = lo;
    int start = newInterval[0], end = newInterval[1];
    if (first < last) {
        start = Math.min(start, intervals[first][0]);
        end = Math.max(end, intervals[last - 1][1]);
    }
    List<int[]> result = new ArrayList<>(Arrays.asList(intervals).subList(0, first));
    result.add(new int[]{start, end});
    result.addAll(Arrays.asList(intervals).subList(last, n));
    return result.toArray(new int[0][]);
}

def insert(intervals, new_interval):
    n = len(intervals)
    lo, hi = 0, n
    while lo < hi:
        mid = (lo + hi) >> 1
        if intervals[mid][1] < new_interval[0]: lo = mid + 1
        else: hi = mid
    first = lo
    hi = n
    while lo < hi:
        mid = (lo + hi) >> 1
        if intervals[mid][0] <= new_interval[1]: lo = mid + 1
        else: hi = mid
    last = lo
    start, end = new_interval
    if first < last:
        start = min(start, intervals[first][0])
        end = max(end, intervals[last - 1][1])
    result = intervals[:first] + [[start, end]] + intervals[last:]
    return result

function insert(intervals: number[][], newInterval: number[]): number[][] {
  const n = intervals.length;
  let lo = 0, hi = n;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (intervals[mid][1] < newInterval[0]) lo = mid + 1;
    else hi = mid;
  }
  const first = lo;
  hi = n;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (intervals[mid][0] <= newInterval[1]) lo = mid + 1;
    else hi = mid;
  }
  const last = lo;
  let start = newInterval[0], end = newInterval[1];
  if (first < last) {
    start = Math.min(start, intervals[first][0]);
    end = Math.max(end, intervals[last - 1][1]);
  }
  return [...intervals.slice(0, first), [start, end], ...intervals.slice(last)];
}