Solve intervals and distinct islands
Company: TikTok
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
##### Question
LeetCode 56. Merge Intervals LeetCode 694. Number of Distinct Islands
https://leetcode.com/problems/merge-intervals/description/ https://leetcode.com/problems/number-of-distinct-islands/description/
Quick Answer: This question evaluates skills in interval manipulation and identification of distinct connected components in grids, testing competencies in data structure usage, algorithmic reasoning, and spatial pattern recognition within the Coding & Algorithms domain.
Implement a function that solves two tasks at once. Given (1) a list of integer intervals [start, end] and (2) a binary grid, return both the merged intervals and the number of distinct island shapes. Intervals are closed and must be merged if they overlap or touch (i.e., next.start <= current.end). The merged result must be sorted by start. In the grid, an island is a maximal group of 1s connected 4-directionally. Two islands are the same shape if one can be translated to match the other; rotations and reflections are considered different. Return a dictionary with keys 'merged' and 'distinct_islands'.
Constraints
- 0 <= len(intervals) <= 100000
- -10^9 <= start <= end <= 10^9
- 0 <= m, n and m * n <= 100000 for grid dimensions
- grid[i][j] is 0 or 1
- Intervals are closed and touching intervals merge (e.g., [1,4] and [4,5] -> [1,5])
- Return merged intervals sorted by start; islands counted by 4-directional connectivity; equality ignores translation only
Solution
def merge_and_count(intervals, grid):
def merge_intervals(iv):
if not iv:
return []
iv = sorted(iv, key=lambda x: (x[0], x[1]))
merged = []
cs, ce = iv[0]
for s, e in iv[1:]:
if s <= ce: # overlap or touch
if e > ce:
ce = e
else:
merged.append([cs, ce])
cs, ce = s, e
merged.append([cs, ce])
return merged
def num_distinct_islands(g):
m = len(g)
if m == 0:
return 0
visited = set()
shapes = set()
for r in range(m):
row_len = len(g[r])
for c in range(row_len):
if g[r][c] == 1 and (r, c) not in visited:
stack = [(r, c)]
visited.add((r, c))
r0, c0 = r, c
shape = []
while stack:
cr, cc = stack.pop()
shape.append((cr - r0, cc - c0))
for dr, dc in ((1,0), (-1,0), (0,1), (0,-1)):
nr, nc = cr + dr, cc + dc
if 0 <= nr < m:
nr_len = len(g[nr])
if 0 <= nc < nr_len and g[nr][nc] == 1 and (nr, nc) not in visited:
visited.add((nr, nc))
stack.append((nr, nc))
shape.sort()
shapes.add(tuple(shape))
return len(shapes)
merged = merge_intervals(intervals)
distinct = num_distinct_islands(grid)
return {"merged": merged, "distinct_islands": distinct}
Explanation
Intervals are sorted and scanned to merge overlapping or touching segments. For islands, a DFS explores each connected component; each island's cells are normalized by subtracting the starting cell's coordinates and sorting the relative positions to obtain a canonical representation. Distinct canonical shapes are counted via a set.
Time complexity: O(k log k + m*n), where k = len(intervals) and m*n is the number of grid cells. Space complexity: O(k + m*n) in the worst case for merged results, visited set, and shape storage.
Hints
- Sort intervals by start; scan and merge when next.start <= current.end.
- For islands, use DFS or BFS to traverse each component.
- Normalize an island's shape by recording cell coordinates relative to the first cell visited in that island.
- Store canonical shapes (e.g., sorted tuples of relative coordinates) in a set to count distinct shapes.