Number of Islands II
MST & Disjoint Set DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Dynamic Number of Islands in a Matrix after Incremental Land Addition, Disjoint Set Union, Union by Rank, Union by Size, Path Compression, Graph, Connected Components, Matrices, Two-dimensional Array Traversal, Time Complexity, Space Complexity, Data Structures, Algorithm, Optimization, query processing, union-find, graph algorithms, matrix manipulation, graph properties, DSU Applications, Connected Components.
Problem: Number of Islands II You are given an n x m 2D grid, initially filled with water (represented by 0). You are also given an array operators of size k, where each element operators[i] = [r, c] represents an operation to change the cell grid[r][c] from water to land (represented by 1). Your task is to return an array of size k, where ans[i] is the number of islands after the i th operation. An island is defined as a group of 1s that are connected horizontally or vertically (sharing a common side). Diagonal connections do not form an island. Input Format: n: An integer representing the number of rows. m: An integer representing the number of columns. operators: A list of lists, where each inner list [r, c] represents the coordinates of the cell to be converted to land. Output Format: A list of integers, where the i th element is the count of islands after the i th operation. Constraints: 1 <= n, m <= 10^5 (total cells n m could be up to 10^5) 1 <= k <= 10^4 0 <= r < n 0 <= c < m Example 1: Example 2: