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

What role is this question designed for?

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

Count Islands After Land Additions | Uber Coding Question

Count Islands After Land Additions

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given an initially empty `m x n` grid filled with water. Land is added one cell at a time. Implement a function that receives: - `m`: number of rows - `n`: number of columns - `positions`: a list of coordinates `[row, col]` indicating cells that are converted from water to land After each land addition, return the current number of islands. An island is a group of land cells connected horizontally or vertically. If the same cell is added more than once, the island count should not change for that operation. Example: ```text m = 3, n = 3 positions = [[0,0], [0,1], [1,2], [2,1], [1,1]] Output: [1, 1, 2, 3, 1] ``` Design an efficient solution suitable for large grids and many land-addition operations.

Quick Answer: This question evaluates understanding of dynamic connectivity, incremental graph updates, and algorithmic efficiency when maintaining connected components under repeated modifications.

You are given an initially empty m x n grid of water. Land is added one cell at a time according to the list positions, where each element is [row, col]. After each operation, return the current number of islands in the grid. An island is a group of land cells connected horizontally or vertically. If a cell is added more than once, that operation does not change the island count. Your solution should be efficient enough for large grids and many additions.

Constraints

1 <= m, n <= 10^4
0 <= len(positions) <= 10^5
0 <= row < m and 0 <= col < n for every position
positions may contain duplicate coordinates

Examples

Input: (3, 3, [[0, 0], [0, 1], [1, 2], [2, 1], [1, 1]])

Expected Output: [1, 1, 2, 3, 1]

Explanation: The first two additions form one island, then two separate islands are created, and the final addition connects all land into a single island.

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

Expected Output: [1, 1, 1]

Explanation: Adding the same single cell multiple times does not change the island count after the first addition.

Input: (2, 2, [])

Expected Output: []

Explanation: No land additions means there are no intermediate island counts to report.

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

Expected Output: [1, 2, 1, 1, 1]

Explanation: Two separate islands are created, then merged into one by [0, 1]. Adding [1, 0] keeps everything connected, and the duplicate final addition changes nothing.

Input: (1, 3, [[0, 0], [0, 2], [0, 1]])

Expected Output: [1, 2, 1]

Explanation: The middle cell connects the two end cells into one island.

Hints

Recomputing the number of islands with a full BFS or DFS after every addition will be too slow.
Use a Disjoint Set Union (Union-Find) structure to connect newly added land with its existing neighboring land cells and maintain the island count incrementally.

Quick Overview

This question evaluates understanding of dynamic connectivity, incremental graph updates, and algorithmic efficiency when maintaining connected components under repeated modifications.