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/
Overview: 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
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.