LeetMotion
You are given an array of intervals where intervals[i] = [starti, endi]. Your goal is to merge all overlapping intervals and return an array of the non-overlapping intervals that cover exactly the same elements as the original input.
Two intervals are considered overlapping if the start time of one interval is less than or equal to the end time of the other. For example, [1, 4] and [4, 5] overlap because they both include the number 4.
1 ≤ intervals.length ≤ 10⁴intervals[i].length == 20 ≤ starti ≤ endi ≤ 10⁴If we do not sort the array, checking for overlaps becomes a graph problem. Think of each interval as a node in a graph. If two intervals overlap, we draw an undirected edge between them.
Any group of nodes connected by edges forms a single "connected component." All intervals in a single component will ultimately merge into a single large interval spanning the minimum start time and the maximum end time of that entire component.
i and j if intervals[i] overlaps with intervals[j].A.start <= B.end AND B.start <= A.end.import collections
class Solution:
def overlap(self, a, b):
return a[0] <= b[1] and b[0] <= a[1]
def merge(self, intervals: list[list[int]]) -> list[list[int]]:
graph = collections.defaultdict(list)
n = len(intervals)
# 1. Build the graph based on overlaps
for i in range(n):
for j in range(i + 1, n):
if self.overlap(intervals[i], intervals[j]):
graph[i].append(j)
graph[j].append(i)
# 2. Find components
visited = set()
ans = []
for i in range(n):
if i not in visited:
stack = [i]
visited.add(i)
min_start = intervals[i][0]
max_end = intervals[i][1]
# DFS to explore the full connected component
while stack:
node = stack.pop()
min_start = min(min_start, intervals[node][0])
max_end = max(max_end, intervals[node][1])
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
stack.append(neighbor)
ans.append([min_start, max_end])
return ansclass Solution {
private boolean overlap(int[] a, int[] b) {
return a[0] <= b[1] && b[0] <= a[1];
}
public int[][] merge(int[][] intervals) {
int n = intervals.length;
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (overlap(intervals[i], intervals[j])) {
graph.get(i).add(j);
graph.get(j).add(i);
}
}
}
boolean[] visited = new boolean[n];
List<int[]> ans = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (!visited[i]) {
Queue<Integer> q = new LinkedList<>();
q.offer(i);
visited[i] = true;
int minStart = intervals[i][0];
int maxEnd = intervals[i][1];
while (!q.isEmpty()) {
int node = q.poll();
minStart = Math.min(minStart, intervals[node][0]);
maxEnd = Math.max(maxEnd, intervals[node][1]);
for (int neighbor : graph.get(node)) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.offer(neighbor);
}
}
}
ans.add(new int[]{minStart, maxEnd});
}
}
return ans.toArray(new int[ans.size()][]);
}
}Time Complexity: O(N²) because we compare every interval against every other interval to build the edges of the graph.
Space Complexity: O(N²) for the adjacency list (in the worst case, every interval overlaps with every other interval).
Comparing every element to everything else is what caused the O(N²) bottleneck. If we sort the intervals by their start times, a magical property emerges: any interval can only overlap with the immediately preceding intervals in the sorted list.
By processing them left-to-right, we only ever need to look at the most recently merged interval to decide if the current interval overlaps. It's a greedy approach: we push intervals onto an ans list, and continuously merge the top interval with incoming ones as long as they overlap.
intervals array based on the start value.ans to store our finalized, merged intervals.interval in the sorted list:ans is empty, OR if the current interval's start is strictly greater than the end of the last interval in ans, there is no overlap. Append the current interval to ans.ans to be the max() of its current end and the incoming interval's end.ans array.class Solution:
def merge(self, intervals: list[list[int]]) -> list[list[int]]:
# Sort by the start time
intervals.sort(key=lambda x: x[0])
ans = []
for interval in intervals:
# If the list of merged intervals is empty
# or if the current interval does not overlap with the previous, append it.
if not ans or ans[-1][1] < interval[0]:
ans.append(interval)
else:
# Otherwise, there is overlap, so we merge the current and previous intervals.
ans[-1][1] = max(ans[-1][1], interval[1])
return ansclass Solution {
public int[][] merge(int[][] intervals) {
// Sort by the start time
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
List<int[]> ans = new ArrayList<>();
for (int[] interval : intervals) {
// If the list of merged intervals is empty
// or if the current interval does not overlap with the previous, append it.
if (ans.isEmpty() || ans.get(ans.size() - 1)[1] < interval[0]) {
ans.add(interval);
} else {
// Otherwise, there is overlap, so we merge the current and previous intervals.
ans.get(ans.size() - 1)[1] = Math.max(ans.get(ans.size() - 1)[1], interval[1]);
}
}
return ans.toArray(new int[ans.size()][]);
}
}Time Complexity: O(N log N) because we must sort the intervals. The linear sweep takes O(N), so the sorting dominates.
Space Complexity: O(N) or O(log N) depending on the sorting algorithm implementation in your language. The space used for the answer array is strictly O(N) but typically omitted in aux space analysis.
A very common beginner mistake is trying to modify the intervals array directly by popping elements as you merge them. Modifying a list while you are actively iterating over it changes the indices and causes skipped elements or out-of-bounds exceptions.
# Wrong: Mutating the list during traversal
intervals.sort()
for i in range(len(intervals) - 1):
if intervals[i][1] >= intervals[i+1][0]:
intervals[i][1] = max(intervals[i][1], intervals[i+1][1])
# This shifts all elements left, messing up the loop index!
intervals.pop(i+1)
# Correct: Always build a new result array
ans = []
for interval in intervals:
# append or merge with the last element in 'ans'
...The greedy sweep-line logic only works if the intervals are processed from earliest start time to latest. If you encounter [[1,4], [0,2]] without sorting, the algorithm will see that ans[-1][1] (4) > interval[0] (0) and try to merge them into [1,4] — but the true minimum start time was 0, resulting in an incorrect answer of [1,4] instead of [0,4].
# Wrong: Missing the sort step
ans = []
for interval in intervals:
if not ans or ans[-1][1] < interval[0]:
...
# Correct: Sort first!
intervals.sort(key=lambda x: x[0])
ans = []
for interval in intervals:
...When you detect an overlap, it's tempting to set the new end time as interval[1]. But what if the first interval completely engulfs the second one? For example, merging [1, 5] and [2, 3]. If you blindly set the end time to 3, you've just shrunk your interval!
# Wrong: Blind assignment ans[-1][1] = interval[1] # Correct: Take the maximum of both ends ans[-1][1] = max(ans[-1][1], interval[1])
Discussion
…