Quick Overview

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.

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/

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

  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.

Loading coding console...

Show the approach

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