Solving Insert Interval in Python: Step-by-Step Guide

Introduction to Insert Interval

The Insert Interval problem is a classic algorithmic challenge frequently encountered in coding interviews and real-world scheduling applications. Given a list of non-overlapping intervals sorted by their start times, and a new interval, your task is to insert the new interval into the list while merging any overlapping intervals. The result must remain a list of non-overlapping intervals sorted by start time.

This problem tests your understanding of array manipulation, interval merging logic, and edge-case handling. Mastering it builds a strong foundation for solving more complex interval-based problems such as meeting room scheduling, calendar conflict detection, and range queries.

Why Insert Interval Matters

Interval problems appear in many practical domains. Calendar applications need to merge overlapping events when a new meeting is added. Database systems use interval merging to optimize range queries. Version control systems merge commit ranges, and genomic sequencing tools merge overlapping DNA segments. Understanding how to efficiently insert and merge intervals is therefore a transferable skill with broad applicability.

From an interview perspective, the Insert Interval problem is a favorite among top tech companies because it evaluates multiple skills at once: linear traversal, conditional logic, in-place versus copy-based manipulation, and clean code organization. A well-structured solution demonstrates algorithmic thinking and attention to edge cases.

Understanding the Problem Statement

Before writing code, let's clearly define the problem. You are given:

• An array intervals where each element is a pair [start, end], representing a non-overlapping interval.
• The intervals are sorted in ascending order by their start times.
• A new interval newInterval = [start, end] that needs to be inserted.

Your goal is to return a new list of intervals where newInterval has been inserted into intervals, and any overlapping intervals have been merged. Two intervals [a, b] and [c, d] overlap if c <= b and a <= d. Since the input is sorted, this simplifies to checking whether new_start <= current_end.

Example Walkthrough

Consider intervals = [[1, 3], [6, 9]] and newInterval = [2, 5]. The new interval overlaps with [1, 3] because 2 <= 3. We merge them into [1, 5]. The interval [6, 9] does not overlap, so it remains unchanged. The final result is [[1, 5], [6, 9]].

Step-by-Step Approach

The cleanest solution processes the intervals in three logical phases. This avoids nested loops and keeps the time complexity at O(n), where n is the number of intervals.

Phase 1: Add All Intervals Before the New Interval

Traverse the existing intervals and add every interval that ends before the new interval starts. These intervals cannot overlap with the new interval, so they are appended to the result unchanged.

Phase 2: Merge Overlapping Intervals

Continue traversing. For each interval that overlaps with the new interval, update the new interval's start to the minimum of both starts and its end to the maximum of both ends. Keep merging until you encounter an interval that starts after the new interval ends.

Phase 3: Add the Merged New Interval and Remaining Intervals

Append the merged new interval to the result. Then append all remaining intervals from the original list, since they come after the new interval and cannot overlap with it.

Complete Python Implementation

Here is the full implementation following the three-phase approach described above.

from typing import List

def insert(intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
    result = []
    i = 0
    n = len(intervals)
    new_start, new_end = newInterval

    # Phase 1: Add all intervals that end before the new interval starts
    while i < n and intervals[i][1] < new_start:
        result.append(intervals[i])
        i += 1

    # Phase 2: Merge all overlapping intervals with the new interval
    while i < n and intervals[i][0] <= new_end:
        new_start = min(new_start, intervals[i][0])
        new_end = max(new_end, intervals[i][1])
        i += 1

    # Append the merged new interval
    result.append([new_start, new_end])

    # Phase 3: Add the remaining intervals
    while i < n:
        result.append(intervals[i])
        i += 1

    return result

Notice how each while loop advances the index i independently. This separation of concerns makes the code easy to read, test, and debug. Each phase has a single responsibility, which is a hallmark of clean code.

Testing the Solution

Let's verify the implementation with several test cases covering common scenarios and edge cases.

if __name__ == "__main__":
    # Test 1: Basic overlap
    print(insert([[1, 3], [6, 9]], [2, 5]))
    # Expected: [[1, 5], [6, 9]]

    # Test 2: No overlap, insert in the middle
    print(insert([[1, 2], [5, 6]], [3, 4]))
    # Expected: [[1, 2], [3, 4], [5, 6]]

    # Test 3: New interval covers all existing intervals
    print(insert([[1, 2], [3, 4], [5, 6]], [0, 7]))
    # Expected: [[0, 7]]

    # Test 4: Empty intervals list
    print(insert([], [4, 8]))
    # Expected: [[4, 8]]

    # Test 5: New interval at the beginning
    print(insert([[3, 5], [7, 9]], [1, 2]))
    # Expected: [[1, 2], [3, 5], [7, 9]]

    # Test 6: New interval at the end
    print(insert([[1, 2], [3, 5]], [6, 8]))
    # Expected: [[1, 2], [3, 5], [6, 8]]

    # Test 7: Multiple merges
    print(insert([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8]))
    # Expected: [[1, 2], [3, 10], [12, 16]]

Run these tests to confirm that every phase of the algorithm behaves correctly. Each test case exercises a different branch of the logic, ensuring robust coverage.

Complexity Analysis

The time complexity is O(n) because we traverse the list of intervals exactly once. Each interval is visited in exactly one of the three phases, and the index i never resets or backtracks.

The space complexity is O(n) in the worst case, which occurs when no merging happens and the result contains all original intervals plus the new one. This is the output space, so the algorithm is optimal in terms of auxiliary space, using only a few scalar variables beyond the result list.

Best Practices

Keep the Three Phases Separate

Resist the temptation to merge all logic into a single loop with complex conditionals. The three-phase structure is easier to reason about and less error-prone. Each phase has a clear precondition and postcondition, which makes the code self-documenting.

Use Descriptive Variable Names

Instead of indexing into newInterval repeatedly, unpack it into new_start and new_end. This improves readability and reduces the chance of indexing mistakes. Similarly, use intervals[i][0] and intervals[i][1] consistently to represent start and end values.

Handle Edge Cases Explicitly

Always test empty input, single-element input, insertion at the beginning, insertion at the end, and complete overlap. These edge cases reveal off-by-one errors and boundary condition bugs that are easy to overlook during initial development.

Leverage Type Hints

Adding type hints like List[List[int]] improves code clarity and enables static analysis tools to catch type-related bugs early. In a collaborative codebase, type hints serve as lightweight documentation for other developers.

Avoid Modifying the Input

The solution creates a new result list rather than modifying the input in place. This is a safer default because callers may not expect their data to be mutated. If in-place modification is required for memory-constrained environments, document that behavior clearly and ensure the caller understands the trade-offs.

Common Pitfalls to Avoid

One frequent mistake is using the wrong comparison operator. Checking intervals[i][1] <= new_start instead of < would incorrectly merge intervals that merely touch at a boundary. For example, [1, 2] and [2, 3] are typically considered non-overlapping, so use strict inequality when appropriate.

Another pitfall is forgetting to append the merged new interval after the merging loop. Since the merging loop only updates new_start and new_end without adding anything to the result, the merged interval must be appended explicitly before processing the remaining intervals.

Finally, avoid resetting the index i between phases. The algorithm relies on the fact that i carries over from one phase to the next, ensuring each interval is processed exactly once. Resetting i would either cause duplicate processing or skip intervals entirely.

Conclusion

The Insert Interval problem is a deceptively simple challenge that rewards careful phase-based thinking and penalizes hasty, tangled logic. By breaking the solution into three clear phases—adding non-overlapping intervals before the new one, merging overlapping intervals, and appending the remaining intervals—you produce code that is efficient, readable, and easy to test. The O(n) time complexity is optimal since every interval must be examined at least once, and the clean separation of concerns makes the implementation robust against edge cases. Whether you are preparing for a coding interview or building a real-world scheduling feature, mastering this pattern will serve you well across a wide range of interval-based problems.