You are given a n,m which means the row and column of the 2D matrix and an array of  size k denoting the number of operations. Matrix elements is 0 if there is water or 1 if there is land. Originally, the 2D matrix is all 0 which means there is no land in the matrix. The array has k operator(s) and each operator has two integer A[i][0], A[i][1] means that you can change the cell matrix[A[i][0]][A[i][1]] from sea to island. Return how many island are there in the matrix after each operation.You need to return an array of size k.
Note : An island means group of 1s such that they share a common side.
 
Example 1:
Input: n = 4
m = 5
k = 4
A = {{1,1},{0,1},{3,3},{3,4}}
Output: 1 1 2 2
Explanation:
0.  00000
    00000
    00000
    00000
1.  00000
    01000
    00000
    00000
2.  01000
    01000
    00000
    00000
3.  01000
    01000
    00000
    00010
4.  01000
    01000
    00000
    00011
 
 
Example 2:
Input: n = 4
m = 5
k = 4
A = {{0,0},{1,1},{2,2},{3,3}}
Output: 1 2 3 4
Explanation:
0.  00000
    00000
    00000
    00000
1.  10000
    00000
    00000
    00000
2.  10000
    01000
    00000
    00000
3.  10000
    01000
    00100
    00000
4.  10000
    01000
    00100
    00010
 
Your Task:
You don't need to read or print anything. Your task is to complete the function numOfIslands() which takes an integer n denoting no. of rows in the matrix, an integer m denoting the number of columns in the matrix and a 2D array of size k denoting  the number of operators.
Expected Time Complexity: O(m * n)
Expected Auxiliary Space: O(m * n)
Constraints:
1 <= n,m <= 100
1 <= k <= 1000

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Spanning trees

Starter code: #User function Template for python3



from typing import List

class Solution:

    def numOfIslands(self, rows: int, cols : int, operators : List[List[int]]) -> List[int]:

        # code here

Solutions:
from typing import List

def findPar(node, parent):
	if node == parent[node]:
		return node
	parent[node] = findPar(parent[node], parent)
	return parent[node]

def union(u, v, rank, parent):
	(ult_u, ult_v) = (findPar(u, parent), findPar(v, parent))
	if ult_u == ult_v:
		return True
	if rank[ult_u] < rank[ult_v]:
		parent[ult_u] = ult_v
	elif rank[ult_v] < rank[ult_u]:
		parent[ult_v] = ult_u
	else:
		parent[ult_v] = ult_u
		rank[ult_u] += 1
	return False

class Solution:

	def numOfIslands(self, rows: int, cols: int, operators: List[List[int]]) -> List[int]:
		(rank, parent) = ([0] * (rows * cols), [i for i in range(rows * cols)])
		vis = [[0 for _ in range(cols)] for _ in range(rows)]
		dirc = [[-1, 0], [1, 0], [0, 1], [0, -1]]
		res = []
		cnt = 0
		for pair in operators:
			cnt += 1
			(r, c) = pair
			if vis[r][c] == 1:
				cnt -= 1
				res.append(cnt)
				continue
			vis[r][c] = 1
			u = r * cols + c
			for i in dirc:
				(x, y) = (r + i[0], c + i[1])
				v = x * cols + y
				if x < 0 or y < 0 or x >= rows or (y >= cols):
					continue
				if vis[x][y] == 1:
					if union(u, v, rank, parent) == False:
						cnt -= 1
			res.append(cnt)
		return res


class DisjointSet:

	def __init__(self, n):
		self.parent = [i for i in range(n + 1)]
		self.size = [1 for i in range(n + 1)]

	def findUParent(self, node):
		if node == self.parent[node]:
			return node
		self.parent[node] = self.findUParent(self.parent[node])
		return self.parent[node]

	def unionByRank(self, u, v):
		up_u = self.findUParent(u)
		up_v = self.findUParent(v)
		if up_u == up_v:
			return
		if self.rank[up_u] < self.rank[up_v]:
			self.parent[up_u] = up_v
		elif self.rank[up_v] < self.rank[up_u]:
			self.parent[up_v] = up_u
		else:
			self.parent[up_v] = up_u
			self.rank[up_u] += 1
		return

	def unionBySize(self, u, v):
		up_u = self.findUParent(u)
		up_v = self.findUParent(v)
		if up_u == up_v:
			return
		if self.size[up_u] < self.size[up_v]:
			self.parent[up_u] = up_v
			self.size[up_v] += self.size[up_u]
		else:
			self.parent[up_v] = up_u
			self.size[up_u] += self.size[up_v]
		return
from typing import List

class Solution:

	def numOfIslands(self, rows: int, cols: int, operators: List[List[int]]) -> List[int]:
		ds = DisjointSet(rows * cols)
		dr = [-1, 1, 0, 0]
		dc = [0, 0, -1, 1]
		vis = [[0 for j in range(cols)] for i in range(rows)]
		res = []
		count = 0
		for i in range(len(operators)):
			r = operators[i][0]
			c = operators[i][1]
			if vis[r][c] == 1:
				res.append(count)
				continue
			vis[r][c] = 1
			count += 1
			nodenum = r * cols + c
			for k in range(len(dr)):
				nr = r + dr[k]
				nc = c + dc[k]
				if 0 <= nr < rows and 0 <= nc < cols and (vis[nr][nc] == 1):
					if ds.findUParent(nodenum) != ds.findUParent(nr * cols + nc):
						count -= 1
						ds.unionBySize(nodenum, nr * cols + nc)
			res.append(count)
		return res


from typing import List

class UnionFind:

	def __init__(self):
		self.parent = {}
		self.rank = {}
		self.size = {}

	def unionByRank(self, a, b):
		(a, b) = (self.find(a), self.find(b))
		if a == b:
			return
		if self.rank[a] == self.rank[b]:
			self.rank[a] += 1
		elif self.rank[b] > self.rank[a]:
			(a, b) = (b, a)
		self.parent[b] = a

	def unionBySize(self, a, b):
		(a, b) = (self.find(a), self.find(b))
		if a == b:
			return
		if self.size[a] < self.size[b]:
			self.parent[a] = b
			self.size[b] += self.size[a]
		else:
			self.parent[b] = a
			self.size[a] += self.size[b]

	def find(self, x):
		if x not in self.parent:
			self.parent[x] = x
			self.rank[x] = 0
			self.size[x] = 1
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

class Solution:

	def isValid(self, r, c, n, m):
		if r >= 0 and c >= 0 and (r < n) and (c < m):
			return True
		return False

	def numOfIslands(self, rows: int, cols: int, operators: List[List[int]]) -> List[int]:
		vis = [[0 for _ in range(cols)] for _ in range(rows)]
		cnt = 0
		ans = []
		ds = UnionFind()
		for ele in operators:
			row = ele[0]
			col = ele[1]
			if vis[row][col] == 1:
				ans.append(cnt)
				continue
			vis[row][col] = 1
			cnt += 1
			dr = [-1, 0, 1, 0]
			dc = [0, 1, 0, -1]
			for i in range(4):
				adjr = row + dr[i]
				adjc = col + dc[i]
				if self.isValid(adjr, adjc, n, m):
					if vis[adjr][adjc] == 1:
						nodeNo = row * m + col
						adjNodeNo = adjr * m + adjc
						if ds.find(nodeNo) != ds.find(adjNodeNo):
							cnt -= 1
							ds.unionBySize(nodeNo, adjNodeNo)
			ans.append(cnt)
		return ans