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.
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.