Insert Interval

Why it belongs on this sheet

This is the natural follow-up after merge intervals and checks if you can reason through cases without losing order.

Pattern

Three interval zones

Approach

Add all intervals that end before the new one starts. Then merge all intervals that overlap the new interval. Finally append the remaining intervals.

Java solution

import java.util.ArrayList;
import java.util.List;

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

    while (i < intervals.length && intervals[i][1] < newInterval[0]) {
      answer.add(intervals[i++]);
    }

    while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
      newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
      newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
      i++;
    }

    answer.add(newInterval);

    while (i < intervals.length) {
      answer.add(intervals[i++]);
    }

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

Complexity

• Time: O(n)
• Space: O(n) for the output

Interview note

The three-phase structure is the cleanest way to explain this problem under pressure.