LeetCode 56: Merge Intervals

Date: February 07, 2026
Category: Arrays
Time Taken: 30 minutes
Difficulty: Medium

---

Problem Statement

Given an array of intervals where intervals[i] = [start<sub>i</sub>, end<sub>i</sub>], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Link: Merge Intervals

---

Brute Force Approach

The brute-force method involves checking every interval in the list for overlapping intervals, which results in a time complexity of O(N²). Therefore, this is not an efficient solution.

---

Optimized Approach:

• The best way to solve this problem is to first sort the list based on the first value of each interval. This allows us to solve it in one pass.

• Next, we create a list to store the merged intervals, starting with the first interval from the original list.

• We run a for loop starting from the first index, checking if the current interval’s first value is smaller than the last value of the previous interval in the list. If it is, we update the last value of the previous interval with the maximum of the last values from either the current or previous interval.

• If the current interval’s last value is not smaller, we simply add the interval to our new list, as it cannot overlap with the previous intervals.

• This solution has a time complexity of O(N log N), with N for iterating through each value and log N for sorting. The space complexity is O(N) for the new list.

Solution Code

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        # Sort the array so we can solve the problem in a single pass
        intervals.sort(key = lambda x: x[0])
        merged = [intervals[0]]
        for current in intervals[1:]:
            last_end = merged[-1][1]
            if current[0] <= last_end:
                merged[-1][1] = max(last_end, current[1])
            else:
                merged.append(current)
        return merged

Complexity:

Time: O(N logN) Space: O(N)

---

Key Takeaway: Just the whole logic.

Pattern: Prefix Sum

Series: 90 Days of Data Engineering Progress: 36/90 problems completed

Tags: #DEQuest #LeetCode #Python #DataEngineering #BuildInPublic