Skip to main content

🟨 Insert Interval (#57)

🔗 Problem Link​

📋 Problem Statement​

You are given an array of non-overlapping intervals where intervals[i] = [starti, endi] and a new interval newInterval = [start, end].

Insert newInterval into intervals such that intervals is still sorted in ascending order and no overlapping intervals. Return the resulting intervals.

💡 Examples​

Example 1​

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

Example 2​

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]

🔑 Key Insights & Approach​

Core Observation: Add intervals before newInterval, merge overlapping with newInterval, add intervals after.

Why Three Phases?

  • O(n) time, O(n) space
  • Process before, during, after overlap
  • Clean separation of logic

Pattern: "Interval Insertion" pattern.

🐍 Solution: Python​

Approach: Three-Phase Processing​

Time Complexity: O(n) | Space Complexity: O(n)

from typing import List

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

        # Add all intervals before newInterval
        while i < n and intervals[i][1] < newInterval[0]:
            result.append(intervals[i])
            i += 1

        # Merge overlapping intervals with newInterval
        while i < n and intervals[i][0] <= newInterval[1]:
            newInterval[0] = min(newInterval[0], intervals[i][0])
            newInterval[1] = max(newInterval[1], intervals[i][1])
            i += 1

        result.append(newInterval)

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

        return result

🔵 Solution: Golang​

Approach: Three Phases​

Time Complexity: O(n) | Space Complexity: O(n)

func insert(intervals [][]int, newInterval []int) [][]int {
    result := [][]int{}
    i := 0
    n := len(intervals)

    for i < n && intervals[i][1] < newInterval[0] {
        result = append(result, intervals[i])
        i++
    }

    for i < n && intervals[i][0] <= newInterval[1] {
        newInterval[0] = min(newInterval[0], intervals[i][0])
        newInterval[1] = max(newInterval[1], intervals[i][1])
        i++
    }

    result = append(result, newInterval)

    for i < n {
        result = append(result, intervals[i])
        i++
    }

    return result
}

func min(a, b int) int { if a < b { return a }; return b }
func max(a, b int) int { if a > b { return a }; return b }

📚 References​