LeetCode 57: Insert Interval – Java Solution & Intuitive Guide

Having trouble with LeetCode 57: Insert Interval? This detailed walkthrough shows you how to insert and merge a new interval into a sorted list of non-overlapping intervals. With a clear explanation and efficient Java code, you’ll be ready to solve this problem in interviews or while sharpening your algorithm skills.

Problem Overview

You’re given a sorted list of non-overlapping intervals and a newInterval. Your task is to insert the new interval into the list and merge any overlaps, ensuring the result remains sorted and non-overlapping.

Example:
Input: intervals = [[1,3], [6,9]], newInterval = [2,5]
Output: [[1,5], [6,9]]
Explanation: [2,5] overlaps with [1,3], so they are merged into [1,5].

Efficient Solution Strategy

The idea is to divide the work into three simple phases:

1. Add All Intervals Before: Insert intervals that end before the new interval starts.
2. Merge Overlapping Intervals: Merge intervals that overlap with the new interval.
3. Add All Remaining Intervals: Add intervals that come after the new interval ends.

Since the list is already sorted, this can be done in a single pass.

Step-by-Step Walkthrough

Let’s try two examples:

Example 1
Input: intervals = [[1,3], [6,9]], newInterval = [2,5]

• [1,3] overlaps with [2,5] → merge into [1,5]
• [6,9] does not overlap → add it directly
  Result: [[1,5], [6,9]]

Example 2
Input: intervals = [[1,2], [5,6]], newInterval = [3,4]

• [1,2] ends before 3 → add it
• [3,4] doesn’t overlap with anything → add it
• [5,6] starts after 4 → add it
  Result: [[1,2], [3,4], [5,6]]

Java Code Implementation

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

        // Add all intervals before the newInterval
        while (i < n && intervals[i][1] < newInterval[0]) {
            merged.add(intervals[i++]);
        }

        // Merge overlapping intervals with newInterval
        while (i < n && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
            newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
            i++;
        }
        merged.add(newInterval);

        // Add all remaining intervals
        while (i < n) {
            merged.add(intervals[i++]);
        }

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

Why It Works

• Time Complexity: O(n) – Every interval is visited once
• Space Complexity: O(n) – Stores the merged result

Because the input is sorted, we avoid re-sorting and merge in one clean pass.

Edge Cases to Watch For

1. newInterval comes before all intervals
2. newInterval comes after all intervals
3. newInterval overlaps multiple intervals
4. Input list is empty

Visualizing the Flow

Input: [[1,2], [5,6]], newInterval = [3,4]
Step 1: Add [1,2]
Step 2: Merge (none to merge) → Add [3,4]
Step 3: Add [5,6]
Result: [[1,2], [3,4], [5,6]]

Comparison with LeetCode 56 (Merge Intervals)

• LeetCode 56: You must sort the intervals first
• LeetCode 57: The intervals are already sorted, so we skip sorting and merge directly

Conclusion

Insert Interval is a classic interval-based problem. By breaking it down into clear steps—before, merge, and after—you can handle any case efficiently. This prepares you for other interval challenges like LeetCode 986 (Interval List Intersections) or LeetCode 759 (Employee Free Time).

Next Step: Modify the code to handle unsorted intervals as a bonus challenge!