Given two integers N and M which denote the size of a matrix where initially all the cells are 0s. There are also K queries each of type {x, y} that denotes a cell of the matrix whose value needs to be flipped from 0 to 1. The task is to find the number of islands of 1s after each query.
Note: An island means a group of 1s such that they share a common side.
Examples:
Input: N = 4, M = 5, K = 4, query[] = {{1, 1}, {0, 1}, {3, 3}, {3, 4}}
Output: 1 1 2 2
Explanation: The states of the matrix after each query are as shown below:
0. 00000
00000
00000
00000
1. 00000
01000
00000
00000
2. 01000
01000
00000
00000
3. 01000
01000
00000
00010
4. 01000
01000
00000
00011Input: N = 4, M = 5, K = 4, A = {{0, 0}, {1, 1}, {2, 2}, {3, 3}}
Output: 1 2 3 4
Approach: To solve the problem follow the below idea:
We can solve the question using disjoint set data structure. The idea is to consider all 1 values as individual sets. Traverse the matrix and do a union of all adjacent 1 vertices.
Follow the steps to solve this problem:
- Initialize the result (count of islands) as 0.
- Traverse each index of the 2D matrix.
- If the value at that index is 1, check all its 4 neighbors. If a neighbor is also equal to 1, take the union of the index and its neighbors.
- Now define an array of size row*column to store frequencies of all sets.
- Now traverse the matrix again.
- If the value at the index is 1, find its set.
- If the frequency of the set in the above array is 0, increment the result be 1.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Array to store the parent of each sets int p[100000]; // Function to find the parent set of x int find( int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; } // Function to convert the matrix cell // to a single integer value int index( int x, int y, int m) { return x * m + y; } // Function to return number of islands vector< int > numOfIslands( int n, int m, vector<vector< int > >& operators) { if (operators.empty()) return {}; vector< int > res; unordered_set< int > nodes; int s = operators.size(); unordered_set< int > current; // Arrays to efficiently traverse // the adjacent of each cell int dx[4] = { 0, 1, 0, -1 }; int dy[4] = { 1, 0, -1, 0 }; int total = 0; for ( auto op : operators) { int pos = index(op[0], op[1], m); nodes.insert(pos); if (current.count(pos)) { res.push_back(total); continue ; } total++; p[pos] = pos; for ( int j = 0; j < 4; j++) { int nx = op[0] + dx[j]; int ny = op[1] + dy[j]; if (!(nx >= 0 && nx < n && ny >= 0 && ny < m)) continue ; if (current.count(index(nx, ny, m))) { int apos = index(op[0], op[1], m); int bpos = index(nx, ny, m); if (find(apos) != find(bpos)) { p[find(apos)] = find(bpos); total--; } } } current.insert(index(op[0], op[1], m)); res.push_back(total); } return res; } // Driver Code int main() { int N = 4, M = 5, K = 4; vector<vector< int > > query = { { 1, 1 }, { 0, 1 }, { 3, 3 }, { 3, 4 } }; vector< int > ans; // Function Call ans = numOfIslands(N, M, query); for ( int i : ans) cout << i << " " ; return 0; } |
Java
// Java Code to implement above approach import java.util.*; public class Solution { // Array to store the parent of each sets static int [] p = new int [ 100000 ]; // Function to find the parent set of x static int find( int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; } // Function to convert the matrix cell // to a single integer value static int index( int x, int y, int m) { return x * m + y; } // Function to return number of islands static ArrayList<Integer> numOfIslands( int n, int m, int [][] operators) { if (operators.length == 0 ) return new ArrayList<>(); ArrayList<Integer> res = new ArrayList<>(); HashSet<Integer> nodes = new HashSet<>(); int s = operators.length; HashSet<Integer> current = new HashSet<>(); // Arrays to efficiently traverse // the adjacent of each cell int dx[] = { 0 , 1 , 0 , - 1 }; int dy[] = { 1 , 0 , - 1 , 0 }; int total = 0 ; for ( int [] op : operators) { int pos = index(op[ 0 ], op[ 1 ], m); nodes.add(pos); if (current.contains(pos)) { res.add(total); continue ; } total++; p[pos] = pos; for ( int j = 0 ; j < 4 ; j++) { int nx = op[ 0 ] + dx[j]; int ny = op[ 1 ] + dy[j]; if (!(nx >= 0 && nx < n && ny >= 0 && ny < m)) continue ; if (current.contains(index(nx, ny, m))) { int apos = index(op[ 0 ], op[ 1 ], m); int bpos = index(nx, ny, m); if (find(apos) != find(bpos)) { p[find(apos)] = find(bpos); total--; } } } current.add(index(op[ 0 ], op[ 1 ], m)); res.add(total); } return res; } // Driver Code public static void main(String[] args) { int N = 4 , M = 5 , K = 4 ; int [][] query = { { 1 , 1 }, { 0 , 1 }, { 3 , 3 }, { 3 , 4 } }; // Function Call ArrayList<Integer> ans = numOfIslands(N, M, query); for ( int i : ans) System.out.print(i + " " ); } } // This code is contributed by karandeep1234 |
Python3
class Solution : # Array to store the parent of each sets p = [ 0 ] * ( 100000 ) # Function to find the parent set of x @staticmethod def find( x) : if (Solution.p[x] ! = x) : Solution.p[x] = Solution.find(Solution.p[x]) return Solution.p[x] # Function to convert the matrix cell # to a single integer value @staticmethod def index( x, y, m) : return x * m + y # Function to return number of islands @staticmethod def numOfIslands( n, m, operators) : if ( len (operators) = = 0 ) : return [] res = [] nodes = set () s = len (operators) current = set () # Arrays to efficiently traverse # the adjacent of each cell dx = [ 0 , 1 , 0 , - 1 ] dy = [ 1 , 0 , - 1 , 0 ] total = 0 for op in operators : pos = Solution.index(op[ 0 ], op[ 1 ], m) nodes.add(pos) if (pos in current) : res.append(total) continue total + = 1 Solution.p[pos] = pos j = 0 while (j < 4 ) : nx = op[ 0 ] + dx[j] ny = op[ 1 ] + dy[j] if ( not (nx > = 0 and nx < n and ny > = 0 and ny < m)) : continue if (Solution.index(nx, ny, m) in current) : apos = Solution.index(op[ 0 ], op[ 1 ], m) bpos = Solution.index(nx, ny, m) if (Solution.find(apos) ! = Solution.find(bpos)) : Solution.p[Solution.find(apos)] = Solution.find(bpos) total - = 1 j + = 1 current.add(Solution.index(op[ 0 ], op[ 1 ], m)) res.append(total) return res # Driver Code @staticmethod def main( args) : N = 4 M = 5 K = 4 query = [[ 1 , 1 ], [ 0 , 1 ], [ 3 , 3 ], [ 3 , 4 ]] # Function Call ans = Solution.numOfIslands(N, M, query) for i in ans : print ( str (i) + " " , end = "") if __name__ = = "__main__" : Solution.main([]) # This code is contributed by aadityaburujwale. |
C#
// C# code using System; using System.Collections.Generic; public class GFG { // C# code to implement the approach // Array to store the parent of each sets public static int [] p = new int [100000]; // Function to find the parent set of x public static int find( int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; } // Function to convert the matrix cell // to a single integer value public static int index( int x, int y, int m) { return x * m + y; } // Function to return number of islands public static List< int > numOfIslands( int n, int m, ref List<List< int > > operators) { if (operators.Count == 0) { List< int > ans = new List< int >(); return ans; } List< int > res = new List< int >(); HashSet< int > nodes = new HashSet< int >(); int s = operators.Count; HashSet< int > current = new HashSet< int >(); // Arrays to efficiently traverse // the adjacent of each cell int [] dx = { 0, 1, 0, -1 }; int [] dy = { 1, 0, -1, 0 }; int total = 0; // for (auto op : operators) { for ( int i = 0; i < operators.Count; i++) { List< int > op = operators[i]; int pos = index(op[0], op[1], m); nodes.Add(pos); if (current.Contains(pos)) { res.Add(total); continue ; } total++; p[pos] = pos; for ( int j = 0; j < 4; j++) { int nx = op[0] + dx[j]; int ny = op[1] + dy[j]; if (!(nx >= 0 && nx < n && ny >= 0 && ny < m)) continue ; if (current.Contains(index(nx, ny, m))) { int apos = index(op[0], op[1], m); int bpos = index(nx, ny, m); if (find(apos) != find(bpos)) { p[find(apos)] = find(bpos); total--; } } } current.Add(index(op[0], op[1], m)); res.Add(total); } return res; } public static void Main( string [] args) { int N = 4, M = 5, K = 4; List<List< int > > query = new List<List< int > >(); List< int > a1 = new List< int >(); a1.Add(1); a1.Add(1); query.Add(a1); List< int > a2 = new List< int >(); a2.Add(0); a2.Add(1); query.Add(a2); List< int > a3 = new List< int >(); a3.Add(3); a3.Add(3); query.Add(a3); List< int > a4 = new List< int >(); a4.Add(3); a4.Add(4); query.Add(a4); List< int > ans = new List< int >(); // Function Call ans = numOfIslands(N, M, ref query); for ( int i = 0; i < ans.Count; i++) { Console.Write(ans[i] + " " ); } } } // This code is contributed by ksam24000. |
Javascript
// JS code implementation // Array to store the parent of each sets let p = []; // Function to find the parent set of x function find(x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; } // Function to convert the matrix cell // to a single integer value function index(x, y, m) { return x * m + y; } // Function to return number of islands function numOfIslands(n, m, operators) { if (operators.length == 0) return []; let res = []; let nodes = new Set(); let s = operators.length; let current = new Set(); // Arrays to efficiently traverse // the adjacent of each cell let dx = [0, 1, 0, -1]; let dy = [1, 0, -1, 0]; let total = 0; for (let i = 0; i < operators.length; i++) { let op = operators[i]; let pos = index(op[0], op[1], m); nodes.add(pos); if (current.has(pos)) { res.push(total); continue ; } total++; p[pos] = pos; for (let j = 0; j < 4; j++) { let nx = op[0] + dx[j]; let ny = op[1] + dy[j]; if (!(nx >= 0 && nx < n && ny >= 0 && ny < m)) continue ; if (current.has(index(nx, ny, m))) { let apos = index(op[0], op[1], m); let bpos = index(nx, ny, m); if (find(apos) != find(bpos)) { p[find(apos)] = find(bpos); total--; } } } current.add(index(op[0], op[1], m)); res.push(total); } return res; } // Driver Code let N = 4, M = 5, K = 4; let query = [[1, 1], [0, 1], [3, 3], [3, 4]]; let ans = []; // Function Call ans = numOfIslands(N, M, query); console.log(ans); // This code is contributed by ksam24000 |
1 1 2 2
Time Complexity: O(K * log(N * M)) because there are K queries and each query will take O(log(N*M)) time on average for union
Auxiliary Space: O(N * M) we are storing the union of each cell.