Practice/Microsoft/Leetcode 305. Number of Islands II

Leetcode 305. Number of Islands II

CodingMust

Problem

You start with an m × n grid where every cell is initially water. You will receive a sequence of operations, where each operation adds a piece of land at a specific coordinate [row, col].

An island is defined as a group of land cells that are connected horizontally or vertically (4-directional connectivity). After each land addition operation, determine how many distinct islands exist in the grid.

Return an array where each element represents the total number of islands after processing each operation in sequence.

Requirements

1. Process land additions sequentially in the order given
2. Count connected components of land cells (islands) after each addition
3. Handle duplicate position additions (adding land to an already-land cell should not change the island count)
4. Connect adjacent land cells horizontally and vertically (up, down, left, right)
5. Return the island count after each operation

Constraints

• 1 ≤ m, n ≤ 104
• 0 ≤ positions.length ≤ 104
• 0 ≤ row < m
• 0 ≤ col < n
• Time complexity should be efficient for repeated connectivity queries

Examples

Example 1:

` Input: m = 3, n = 3, positions = [[0,0], [0,1], [1,2], [2,1]] Output: [1, 1, 2, 3] Explanation:

• Add land at (0,0): Creates 1 island
• Add land at (0,1): Connects to (0,0), still 1 island
• Add land at (1,2): Creates separate island, now 2 islands
• Add land at (2,1): Creates another separate island, now 3 islands `

Example 2:

` Input: m = 2, n = 2, positions = [[0,0], [1,1], [0,1]] Output: [1, 2, 1] Explanation:

• Add land at (0,0): Creates 1 island
• Add land at (1,1): Creates separate island, now 2 islands
• Add land at (0,1): Connects (0,0) and (1,1), merging into 1 island `

Example 3:

` Input: m = 1, n = 1, positions = [[0,0], [0,0]] Output: [1, 1] Explanation:

• Add land at (0,0): Creates 1 island
• Add land at (0,0): Duplicate position, still 1 island `