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 Take-home Project rounds at Uber.

What role is this question designed for?

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

Count connected islands using Union-Find

Quick Overview

This question evaluates understanding of union-find (disjoint set) data structures and graph connectivity concepts for counting connected components in grid-based problems.

Count connected islands using Union-Find

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

You are given an `m x n` grid of characters where `'1'` represents land and `'0'` represents water. An island is a group of horizontally or vertically adjacent land cells. Return the number of islands in the grid. Constraints/notes: - Adjacency is 4-directional (up/down/left/right), not diagonal. - Aim to solve using a Union-Find (Disjoint Set Union) approach (even though DFS/BFS also works). Example: Grid: 1 1 0 0 1 0 1 0 1 Output: 3

Quick Answer: This question evaluates understanding of union-find (disjoint set) data structures and graph connectivity concepts for counting connected components in grid-based problems.

You are given an m x n grid of characters where '1' represents land and '0' represents water. An island is a group of horizontally or vertically adjacent land cells. Diagonal cells are not connected. Return the total number of islands in the grid. You should solve this using a Union-Find (Disjoint Set Union) approach.

Constraints

0 <= m, n <= 300
grid[i][j] is either '0' or '1'
Adjacency is 4-directional only: up, down, left, right

Examples

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

Expected Output: 3

Explanation: The top-left three land cells form one island, the land at (2,0) forms a second island, and the land at (2,2) forms a third island.

Input: []

Expected Output: 0

Explanation: An empty grid contains no land, so there are no islands.

Input: [['0']]

Expected Output: 0

Explanation: A single water cell does not form an island.

Input: [['1']]

Expected Output: 1

Explanation: A single land cell is one island.

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

Expected Output: 5

Explanation: All five land cells are only diagonally adjacent, so each one is a separate island.

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

Expected Output: 2

Explanation: The cells in the top-left form one island, and the connected group on the right forms the second island.

Hints

Treat each land cell as a node in a Disjoint Set Union structure. A cell at (r, c) can be mapped to a 1D id like r * n + c.
You can start with the number of land cells, then reduce the count each time a union merges two previously separate land components.

Last updated: Apr 19, 2026

Loading coding console...