Merge Intervals | Leetcode 56

Welcome to our deep dive on Merge Intervals (Leetcode 56). This problem is ubiquitous in tech interviews and tests your ability to parse, sort, and combine bounding coordinates.

Problem Statement

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example: intervals = [[1,3],[2,6],[8,10],[15,18]] => Output: [[1,6],[8,10],[15,18]] (Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].)

Approach: Sort then Sweep O(N log N)

The absolute most important step when dealing with arrays of random intervals is to Sort them by their start points. Once the list is strictly sorted horizontally from left to right, we can guarantee that any overlapping intervals will be immediately adjacent to each other!

1. Sort the input array intervals ascending by the start element.
2. Initialize an empty merged list.
3. Iterate through the intervals one by one.
   • If merged is empty, or the start of the current interval is strictly GREATER than the end of the last interval added to merged, there is no overlap. Add the current interval to merged safely.
   • Else, there IS an overlap! We don't add a new interval. Instead, we mutate the end value of the last interval in merged to become max(last.end, current.end).

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if not intervals: return []
        
        # Sort by the starting mathematical coordinate
        intervals.sort(key=lambda x: x[0])
        merged = []
        
        for curr in intervals:
            # If empty, or NO overlap with the last merged element
            if not merged or merged[-1][1] < curr[0]:
                merged.append(curr)
            else:
                # OVERLAP! Update the end boundary of the last merged element
                merged[-1][1] = max(merged[-1][1], curr[1])
                
        return merged

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (56)