Coding Patterns: Merge Intervals
In Coding Patterns series, we will try to recognize common patterns underlying behind each algorithm question, using real examples from Leetcode.
Previous posts were about Sliding Window, Two Pointers and Fast & Slow Pointers patterns and today, we will introduce Merge Intervals pattern which is very useful to solve the problems involve intervals, overlapping items that need to be merged etc.
Problem: Merge Intervals
LeetCode 56 - Merge Intervals [medium]
Given a collection of intervals, merge all overlapping intervals.
Example 1:
Input: [[1, 3], [2, 6], [8, 10], [15, 18]]
Output: [[1, 6], [8, 10], [15, 18]]
Explanation: Since intervals [1, 3] and [2, 6] overlaps, merge them into [1, 6].
Example 2:
Input: [[1, 4], [4, 5]]
Output: [[1, 5]]
Explanation: Intervals [1, 4] and [4, 5] are considered overlapping.
Merge Intervals Solution
Given two intervals A and B, there will be six different ways the two intervals can relate to each other:
If a.start <= b.start, only 1, 2 and 3 are possible from the above scenarios.
Our goal is to merge the intervals whenever they overlap. For the two overlapping scenarios 2 and 3, this is how we will merge them:
We are going to merge them into a new interval c such that;
c.start = a.start
c.end = max(a.end, b.end)
Here is what our code will look like:
class Solution:
def merge(self, intervals):
if len(intervals) < 2:
return intervals
intervals.sort(key=lambda x: x[0])
merged = []
start = intervals[0][0]
end = intervals[0][1]
for i in range(1, len(intervals)):
interval = intervals[i]
if interval[0] <= end: # overlapping intervals
end = max(interval[1], end)
else: # non-overlapping interval, add the previous interval and reset
merged.append([start, end])
start = interval[0]
end = interval[1]
merged.append([start, end]) # add the last interval
return merged
Time Complexity: O(N * log N) where N is the total number of intervals. In the beginning, since we sort the intervals, our algorithm will take O(N * log N) to run.
Space Complexity: O(N), as we need to return a list containing all the merged intervals.
How to identify?
This approach is quite useful when dealing with intervals, overlapping items or merging intervals.
When the problem involves these clue words, you should think about Merge Intervals pattern.