Solve island and frequency problems

Question

LeetCode 200. Number of Islands – given a 2D grid, count the number of connected islands of '1's using DFS/BFS/Union-Find. LeetCode 695. Max Area of Island – return the area of the largest island (connected region of 1’s) in the grid. LeetCode 347. Top K Frequent Elements – return the k most frequent elements in an integer array using a heap / bucket sort.

https://leetcode.com/problems/number-of-islands/description/ https://leetcode.com/problems/max-area-of-island/description/ https://leetcode.com/problems/top-k-frequent-elements/description/

Top-K Frequent Island Areas

Given a 2D binary grid and an integer k, compute the size (number of cells) of every island, where an island is a maximal group of 1s connected 4-directionally (up, down, left, right). Let area values be the sizes of all islands found. Return the k area values that are most frequent among all islands, ordered by decreasing frequency; break ties by larger area first. If there are fewer than k distinct area values, return all distinct area values in that order. If there are no islands or k == 0, return an empty list.

Constraints

• 0 <= m, n <= 1000, where m = number of rows, n = number of columns
• m * n <= 200000
• All rows have equal length
• grid[i][j] is 0 or 1
• 0 <= k <= 100000
• Islands are connected 4-directionally (up, down, left, right)
• If k exceeds the number of distinct area values, return all distinct areas
• Order result by frequency descending, then by area value descending

Examples

Example 1

Input: grid = [[1,1,0,0],[1,0,0,1],[0,0,1,1],[1,0,0,0]], k = 2
Output: [3,1]

Explanation: Islands have areas [3,3,1]. Frequencies: 3 -> 2, 1 -> 1. Top-2 by frequency -> [3,1].

Example 2

Input: grid = [[1,1,0,0,0],[1,0,0,0,0],[0,0,0,1,1],[0,0,0,0,0],[1,0,0,0,0]], k = 2
Output: [3,2]

Explanation: Islands have areas [3,2,1]. All frequencies are 1, so tie-break by area value descending -> [3,2] for k=2.

Hints

1. Traverse the grid and use BFS/DFS to compute each island's area.
2. Collect all island areas, then count frequencies with a hash map.
3. Use a heap to extract top-k by (frequency desc, area desc), e.g., push (-freq, -area).
4. Return early for k == 0 or when the grid is empty.

Approach

We scan the grid and run BFS from each unvisited 1 to compute the area of that island. We collect all island areas, count their frequencies with a hash map, and then use a heap keyed by (-frequency, -area) to retrieve the k most frequent area values, breaking ties by larger area. Returning fewer than k values is allowed if there are not enough distinct area sizes.

• Time complexity: O(mn + d log d), where d is the number of distinct island areas (d <= number of islands <= mn)
• Space complexity: O(mn) for visited and BFS queue in the worst case, plus O(d) for the heap