📚 Insert Interval – Java Cheat Sheet (One Page)

📌 What Is It?

The Insert Interval pattern involves inserting a new interval into a list of sorted, non-overlapping intervals and merging if necessary.

Iterate through the intervals
Handle three cases: before, overlapping, and after the new interval
Merge overlapping intervals dynamically

🧱 Pattern Template

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

    // Add all intervals before the new interval
    while (i < intervals.length && intervals[i][1] < newInterval[0]) {
        result.add(intervals[i]);
        i++;
    }

    // Merge overlapping intervals
    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++;
    }
    result.add(newInterval);

    // Add all intervals after the new interval
    while (i < intervals.length) {
        result.add(intervals[i]);
        i++;
    }

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

✅ Use Cases

Inserting a new interval into a sorted list
Merging overlapping intervals dynamically
Handling edge cases like no overlap or full overlap

📘 Common LeetCode Problems

57: Insert Interval [Medium] Sorting, Intervals
56: Merge Intervals [Medium] Sorting, Intervals

🧪 Example: Insert Interval

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

💡 Pro Tips

Handle intervals before, overlapping, and after the new interval separately
Use a list to dynamically store the result
Edge cases: empty intervals, fully overlapping intervals