How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Snapchat.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Snapchat during technical interviews.

Compute islands in a binary grid | Snapchat Coding Question

Quick Overview

This question evaluates a candidate's competency in modeling grids as graphs, detecting connected components, applying graph traversal algorithms (DFS/BFS) and disjoint-set (Union-Find) data structures, and analyzing algorithmic time and space complexity.

Compute islands in a binary grid

Company: Snapchat

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

You are given an m-by-n grid of characters where '1' represents land and '0' represents water. Count the number of connected land masses (islands) using 4-directional connectivity (up, down, left, right) and return that count. Also implement a variant that returns the sizes of all islands in descending order. Discuss and compare DFS, BFS, and Union-Find approaches, including their time and space complexities.

Quick Answer: This question evaluates a candidate's competency in modeling grids as graphs, detecting connected components, applying graph traversal algorithms (DFS/BFS) and disjoint-set (Union-Find) data structures, and analyzing algorithmic time and space complexity.

Number of Islands

You are given an `m x n` 2D grid `grid` of characters where `'1'` represents land and `'0'` represents water. An **island** is a group of `'1'`s connected **4-directionally** (up, down, left, right). You may assume all four edges of the grid are surrounded by water. Return the number of islands. **Example 1:** ``` Input: grid = [ ['1','1','1','1','0'], ['1','1','0','1','0'], ['1','1','0','0','0'], ['0','0','0','0','0'] ] Output: 1 ``` **Example 2:** ``` Input: grid = [ ['1','1','0','0','0'], ['1','1','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1'] ] Output: 3 ``` This is a classic flood-fill / connected-components problem. Iterate over every cell; when you find an unvisited `'1'`, increment your island counter and flood-fill (DFS, BFS, or Union-Find) to mark the entire connected component as visited so it is only counted once. DFS and BFS both run in O(m·n) time; Union-Find runs in O(m·n·α(m·n)) which is effectively linear.

Constraints

1 <= m, n <= 300
grid[i][j] is '0' or '1'
The grid may be empty (treat as 0 islands)

Examples

Input: ([['1','1','1','1','0'],['1','1','0','1','0'],['1','1','0','0','0'],['0','0','0','0','0']],)

Expected Output: 1

Explanation: All land cells are connected 4-directionally into a single island.

Input: ([['1','1','0','0','0'],['1','1','0','0','0'],['0','0','1','0','0'],['0','0','0','1','1']],)

Expected Output: 3

Explanation: A 2x2 block, a single cell, and a horizontal pair form three separate islands.

Input: ([['0','0','0'],['0','0','0']],)

Expected Output: 0

Explanation: All water means no islands.

Input: ([['1']],)

Expected Output: 1

Explanation: A single land cell is one island.

Input: ([],)

Expected Output: 0

Explanation: Empty grid has no islands.

Input: ([['1','0','1','0','1']],)

Expected Output: 3

Explanation: Three isolated land cells separated by water are three islands.

Hints

Scan the grid cell by cell. The first time you hit an unvisited '1', you've discovered a new island.
From that cell, flood-fill (DFS or BFS) to all 4-directionally connected '1' cells and mark them visited so the same island is never re-counted.
Three standard approaches: DFS (recursive or stack), BFS (queue), or Union-Find. All are effectively O(m·n); Union-Find shines when edges/cells stream in dynamically.

Island Sizes in Descending Order

Building on the Number of Islands problem: given the same `m x n` grid of `'1'` (land) and `'0'` (water) characters with 4-directional connectivity, return a list of the **sizes** of every island, sorted in **descending** order. The size of an island is the number of land cells it contains. **Example:** ``` Input: grid = [ ['1','1','0','0','0'], ['1','1','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1'] ] Output: [4, 2, 1] ``` The 2x2 block has size 4, the horizontal pair has size 2, and the lone cell has size 1. The approach mirrors counting islands: flood-fill each connected component, but instead of just incrementing a counter, count the cells in each component. Collect all sizes, then sort descending. This is the natural generalization the interviewer asked for as a follow-up.

Constraints

1 <= m, n <= 300
grid[i][j] is '0' or '1'
The grid may be empty (return an empty list)
Return sizes sorted in non-increasing order

Examples

Input: ([['1','1','1','1','0'],['1','1','0','1','0'],['1','1','0','0','0'],['0','0','0','0','0']],)

Expected Output: [9]

Explanation: One island made of 9 connected land cells.

Input: ([['1','1','0','0','0'],['1','1','0','0','0'],['0','0','1','0','0'],['0','0','0','1','1']],)

Expected Output: [4, 2, 1]

Explanation: Sizes 4 (2x2 block), 2 (horizontal pair), and 1 (lone cell), sorted descending.

Input: ([['0','0','0'],['0','0','0']],)

Expected Output: []

Explanation: No land means no islands and an empty list.

Input: ([['1']],)

Expected Output: [1]

Explanation: A single land cell forms one island of size 1.

Input: ([],)

Expected Output: []

Explanation: Empty grid yields an empty list.

Input: ([['1','0','1','0','1']],)

Expected Output: [1, 1, 1]

Explanation: Three isolated cells, each an island of size 1.

Hints

This is the count-islands flood-fill, but track how many cells each component contains instead of just whether it exists.
Each time you discover a new unvisited '1', run a DFS/BFS and count every land cell you mark; append that count to a sizes list.
After collecting all sizes, sort the list in descending order before returning it.

Quick Overview