Insert Interval LeetCode Solution: The Three-Phase Approach

If Merge Intervals (#56) is the bread-and-butter interval problem, Insert Interval (#57) is its natural companion. Both problems rely on the same overlap logic — comparing start and end points to decide whether two intervals should be combined — but Insert Interval applies that logic to a more constrained scenario: you are given an already-sorted, non-overlapping list and need to insert exactly one new interval.

This matters for interviews because solving both problems back to back demonstrates mastery of interval manipulation. Merge Intervals sorts first, then sweeps. Insert Interval skips the sort because the input is already ordered, and instead uses a clean three-phase approach that processes intervals before, during, and after the overlap zone.

The insert interval leetcode problem is a medium-difficulty staple that appears frequently in technical screens. Understanding the three-phase pattern makes it a five-minute solve once you see the structure.

You are given a list of non-overlapping intervals sorted by their start times, and a new interval to insert. Return the list after inserting the new interval, merging any overlapping intervals so the result remains sorted and non-overlapping.

For example, given intervals [[1,3],[6,9]] and newInterval [2,5], the output is [[1,5],[6,9]]. The new interval [2,5] overlaps with [1,3] because 2 is between 1 and 3, so they merge into [1,5]. The interval [6,9] does not overlap and stays unchanged.

The constraints guarantee the input list is already sorted and contains no overlaps. This is the key difference from Merge Intervals — you do not need to sort first. Your job is to find where the new interval fits, merge any overlaps it creates, and return the updated list.

The cleanest way to solve insert interval leetcode is to split the problem into three phases. Each phase is a simple while loop with a clear condition, making the code easy to write and easy to verify.

Phase 1 — Before: iterate through intervals whose end is strictly less than the new interval's start. These intervals have no overlap with the new interval, so add them directly to the result. They sit entirely to the left of the insertion point.

Phase 2 — Merge: iterate through intervals whose start is less than or equal to the new interval's end. These intervals overlap with the new interval. For each overlapping interval, expand the new interval by taking the minimum of both starts and the maximum of both ends. When this loop finishes, add the merged interval to the result.

Phase 3 — After: all remaining intervals have a start greater than the new interval's end. They sit entirely to the right and cannot overlap. Add them directly to the result.

The implementation translates the three-phase approach directly into code. Use a single index variable to walk through the intervals array, and a result array to collect output. Each phase advances the index with its own while loop.

In Phase 1, while i is in bounds and intervals[i][1] < newInterval[0], push intervals[i] to result and increment i. This collects every interval that ends before the new one starts.

In Phase 2, while i is in bounds and intervals[i][0] <= newInterval[1], update newInterval[0] to the minimum of newInterval[0] and intervals[i][0], and update newInterval[1] to the maximum of newInterval[1] and intervals[i][1]. Then increment i. After the loop, push the merged newInterval to result.

In Phase 3, push all remaining intervals from index i onward to result. Return result. The entire algorithm runs in O(n) time with O(n) space for the output array — you visit each interval exactly once.

Let us trace through the classic example: intervals = [[1,3],[6,9]], newInterval = [2,5]. We want to insert [2,5] into this sorted list.

Phase 1 — Before: check intervals[0] = [1,3]. Is 3 < 2? No, so Phase 1 ends immediately with nothing added. No intervals sit entirely before the new one.

Phase 2 — Merge: check intervals[0] = [1,3]. Is 1 <= 5? Yes, so we have overlap. Merge: newInterval becomes [min(2,1), max(5,3)] = [1,5]. Move to i = 1. Check intervals[1] = [6,9]. Is 6 <= 5? No, so Phase 2 ends. Push the merged interval [1,5] to result.

Phase 3 — After: push intervals[1] = [6,9] to result. Final answer: [[1,5],[6,9]]. The interval [1,3] was absorbed into [2,5] to produce [1,5], while [6,9] passed through untouched.

Notice how the merge step used min(2,1) = 1 for the start, not just the new interval's start. The existing interval [1,3] actually extended the merged result to the left. This is the detail that catches people.

The three-phase approach handles every edge case naturally because each phase has a clear boundary condition. Understanding these cases builds confidence that your solution is correct.

Insert at the beginning: if the new interval ends before the first existing interval starts, Phase 1 adds nothing, Phase 2 adds nothing (no overlap), and the new interval is pushed before everything in Phase 3. Insert at the end works symmetrically — Phase 1 adds all existing intervals, Phase 2 finds no overlap, and the new interval is appended.

New interval overlaps everything: Phase 1 adds nothing because the first interval overlaps. Phase 2 absorbs every interval into the merged result. Phase 3 adds nothing because no intervals remain. The result is a single merged interval.

No overlap at all: the new interval fits in a gap between two existing intervals. Phase 1 adds all intervals before the gap, Phase 2 finds no overlap and pushes the new interval as-is, and Phase 3 adds all intervals after the gap. Empty input list: Phase 1 and Phase 2 skip entirely, the new interval is pushed, and that is the result.

Insert Interval teaches the three-phase interval processing pattern — a technique that appears whenever you need to modify a sorted interval list without re-sorting. The before-merge-after structure is reusable for problems like removing intervals, splitting intervals, or adding availability windows.

More importantly, it reinforces the overlap detection logic shared with Merge Intervals. Two intervals overlap when start_a <= end_b and start_b <= end_a. Once you internalize this condition, both problems become straightforward applications of the same rule.

This problem is also a great example of how sorted input simplifies an algorithm. Merge Intervals requires an O(n log n) sort as a preprocessing step. Insert Interval gives you sorted order for free, reducing the problem to a single O(n) pass. Recognizing when the input guarantees order is an important interview skill.

Review Insert Interval alongside Merge Intervals with YeetCode flashcards. When you can recall the three-phase pattern and the overlap condition from memory, you are prepared for any interval question an interviewer can throw at you.