Solve intervals and distinct islands

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/

Merge Intervals and Count Islands

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

Examples

Example 1

Input: intervals = [[1,3],[2,6],[8,10],[15,18]], grid = [[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]
Output: {"merged": [[1,6],[8,10],[15,18]], "distinct_islands": 1}

Explanation: Intervals merge to [[1,6],[8,10],[15,18]]. The grid has two identical 2x2 islands, so there is 1 distinct shape.

Example 2

Input: intervals = [[1,4],[4,5]], grid = [[1,0,0,0],[1,1,0,1],[0,0,0,1]]
Output: {"merged": [[1,5]], "distinct_islands": 2}

Explanation: Intervals touching at 4 merge to [1,5]. The grid has an L-shaped island and a vertical 2-cell island, which are different shapes.

Hints

1. Sort intervals by start; scan and merge when next.start <= current.end.
2. For islands, use DFS or BFS to traverse each component.
3. Normalize an island's shape by recording cell coordinates relative to the first cell visited in that island.
4. Store canonical shapes (e.g., sorted tuples of relative coordinates) in a set to count distinct shapes.

Approach

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 + mn), where k = len(intervals) and mn is the number of grid cells
• Space complexity: O(k + m*n) in the worst case for merged results, visited set, and shape storage