DKodeTree Small Logo
DKodeTreeWhere logic takes root...!
Merge Intervals - Solution
Solutions and explanations
Link to Problem StatementView on GitHub

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        res = [intervals[0]]

        for start, end in intervals[1:]:
            prev_end = res[-1][1]
            if start <= prev_end: # overlapping
                res[-1][1] = max(prev_end, end)
            else:
                res.append([start, end])
        return res

Complexity Analysis

Here, n represents the number of intervals in the input array.

  • Time Complexity: O(n log n), dominated by the sorting step.
  • Space Complexity: O(n)
    • Output Space: O(n)
    • Sorting Space: O(1) or O(n) depending on whether sorting is done in place or not.