Solve island and frequency problems
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
##### 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/
Quick Answer: These problems evaluate graph traversal and connected-component identification in 2D grids plus frequency analysis and selection in arrays, covering concepts such as DFS/BFS, Union-Find, hashing, heaps and bucket sort.
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
Hints
- Traverse the grid and use BFS/DFS to compute each island's area.
- Collect all island areas, then count frequencies with a hash map.
- Use a heap to extract top-k by (frequency desc, area desc), e.g., push (-freq, -area).
- Return early for k == 0 or when the grid is empty.