Intervals

Insert Interval

Given sorted non-overlapping intervals and a new interval: collect all intervals that come before (no overlap), merge all that overlap with the new one, then collect the rest.

O(n)

say this out loud

The list is already sorted, so I walk it in three phases: everything ending before, the block that overlaps and merges, then everything after. No sort needed.

How It Works

Insert Interval adds one new range into an already sorted, non-overlapping list while preserving both properties. The list splits naturally into three zones: intervals ending before the new one starts are copied unchanged; intervals overlapping the new one are absorbed by widening the new interval's start and end to cover them; intervals starting after the merged range ends are copied unchanged.

Because the input is already sorted, one linear pass handles all three zones in order, no re-sorting needed, so the cost is O(n) time rather than the O(n log n) a full merge-from-scratch would spend. The zone boundaries are pure comparisons: interval.end < new.start for the left zone, interval.start > new.end for the right.

Step-by-Step Visualization

Insert [4,8] into the sorted, already merged list [1,2], [3,5], [6,7], [8,10]

inserting[4, 8]

1/8

Code

Java

static int[][] insert(int[][] intervals, int[] newInterval) {
  List<int[]> result = new ArrayList<>();
  int start = newInterval[0], end = newInterval[1];
  int i = 0;

  while (i < intervals.length && intervals[i][1] < start)
    result.add(intervals[i++]);

  while (i < intervals.length && 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 < intervals.length) result.add(intervals[i++]);
  return result.toArray(new int[0][]);
}

Tips & Gotchas

1Three phases: add intervals before new one, merge overlapping, add remaining

2Intervals before: end < newStart. After: start > newEnd

3Everything else overlaps and must be merged

Practice Problems

1Insert Interval
2Merge Intervals
3My Calendar I
4Data Stream as Disjoint Intervals

About the Intervals Pattern

Problems involving ranges [start, end]. Meetings, schedules, overlapping segments. The key first step is almost always: sort by start time (or end time). Then process them linearly.

Key insight

When you see 'subarray', 'contiguous', or 'in-place', think arrays. The key is reducing brute-force O(n²) to O(n) using sliding window, two pointers, or prefix sums.

Common Array Interview Problems

Two Sum
Best Time to Buy & Sell Stock
Maximum Subarray
Merge Intervals
Product of Array Except Self
Container With Most Water

Frequently Asked Questions

Why not just append the new interval and rerun the merge algorithm?

That works but costs O(n log n) for a sort the input has already paid for. Exploiting the pre-sorted structure keeps insertion at O(n), and in an interview it demonstrates that you noticed the invariant instead of reaching for a generic hammer.

How does the overlap-absorption step actually update the new interval?

While the current interval's start is at most the new interval's end, they overlap, so set newStart = min(newStart, interval.start) and newEnd = max(newEnd, interval.end) and advance. When the loop exits, the widened interval is emitted once, followed by the untouched tail.