<p>Given an <code>m x n</code> 2D binary grid <code>grid</code> which represents a map of <code>&#39;1&#39;</code>s (land) and <code>&#39;0&#39;</code>s (water), return <em>the number of islands</em>.</p>

<p>An <strong>island</strong> is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> grid = [
  [&quot;1&quot;,&quot;1&quot;,&quot;1&quot;,&quot;1&quot;,&quot;0&quot;],
  [&quot;1&quot;,&quot;1&quot;,&quot;0&quot;,&quot;1&quot;,&quot;0&quot;],
  [&quot;1&quot;,&quot;1&quot;,&quot;0&quot;,&quot;0&quot;,&quot;0&quot;],
  [&quot;0&quot;,&quot;0&quot;,&quot;0&quot;,&quot;0&quot;,&quot;0&quot;]
]
<strong>Output:</strong> 1
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> grid = [
  [&quot;1&quot;,&quot;1&quot;,&quot;0&quot;,&quot;0&quot;,&quot;0&quot;],
  [&quot;1&quot;,&quot;1&quot;,&quot;0&quot;,&quot;0&quot;,&quot;0&quot;],
  [&quot;0&quot;,&quot;0&quot;,&quot;1&quot;,&quot;0&quot;,&quot;0&quot;],
  [&quot;0&quot;,&quot;0&quot;,&quot;0&quot;,&quot;1&quot;,&quot;1&quot;]
]
<strong>Output:</strong> 3
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 300</code></li>
	<li><code>grid[i][j]</code> is <code>&#39;0&#39;</code> or <code>&#39;1&#39;</code>.</li>
</ul>

class Solution:

    class UnionFind: 
        
        def __init__(self, n:int, parent: List) -> None:
            self.components = n
            self.parent = parent 
            self.component_size = [1 if p != 0 else 0 for p in parent]

        def union(self, a: int, b:int) -> None: 
            parent_a = self.find(a)
            parent_b = self.find(b) 
            if parent_a == parent_b: return 
            if self.component_size[parent_a] <= self.component_size[parent_b]: 
                self.parent[parent_a] = self.parent[parent_b] 
                self.component_size[parent_b] += self.component_size[parent_a]
                self.component_size[parent_a] = 0
                self.components -= 1
            else: 
                self.parent[parent_b] = self.parent[parent_a] 
                self.component_size[parent_a] += self.component_size[parent_b]
                self.component_size[parent_b] = 0
                self.components -= 1

        def find(self, i:int) -> None: 
            if self.parent[i] == i: return i 
            self.parent[i] = self.find(self.parent[i])
            return self.parent[i] 

    def numIslands(self, grid: List[List[str]]) -> int:
        # We can use BFS or DFS or Union Find 
        # build a 1D array 
        arr = [] 
        num_non_zero = 0 
        m, n = len(grid), len(grid[0])
        for i in range(m): 
            for j in range(n):
                if grid[i][j] == '1':
                    num_non_zero += 1
                    arr.append(i*n + j)
                else:
                    arr.append(-1)
        UF = self.UnionFind(num_non_zero, arr) 
        
        for i in range(m):
            for j in range(n): 
                if j+1 < n and grid[i][j] == '1' and grid[i][j+1] == '1':
                    UF.union(i*n+j, i*n+j+1)
                if i+1 < m and grid[i][j] == '1' and grid[i+1][j] == '1':
                    UF.union(i*n+j, (i+1)*n+j)
        return UF.components 











        # BFS O(MN) Time Space 
        '''
        visited = set() 
        num_islands = 0 
        m, n = len(grid), len(grid[0])
        for i in range(m):
            for j in range(n): 
                if grid[i][j] == '1' and (i, j) not in visited: 
                    num_islands +=1 
                    queue = deque([(i, j)])
                    visited.add((i, j))
                    while queue: 
                        i_, j_ = queue.popleft()
                        # exploring the neighbors 
                        for (x, y) in [(i_-1, j_), (i_+1, j_), (i_, j_-1), (i_, j_+1)]: 
                            if 0<=x<m and 0<=y<n and grid[x][y] == '1' and (x, y) not in visited: 
                                visited.add((x, y))
                                queue.append((x, y))
        return num_islands 
        '''

        #DFS 
        '''
        def dfs(i: int, j:int, grid:List[List[str]], visited: set) -> None:
            if 0<=i<len(grid) and 0<=j<len(grid[0]) and grid[i][j] == '1' and (i, j) not in visited: 
                visited.add((i, j)) 
                for x, y in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]: 
                    dfs(x, y, grid, visited)

        m, n = len(grid), len(grid[0]) 
        visited = set() 
        num_islands = 0 

        for i in range(m): 
            for j in range(n): 
                if grid[i][j] == '1' and (i, j) not in visited: 
                    num_islands += 1
                    dfs(i, j, grid, visited)
        return num_islands 
        ''' 






        




















        # dfs or bfs 
        # O(MN) space and time 

        '''
        def dfs(i, j, visited_map): 
            if 0 > i or i >= len(grid) or 0 > j or j >= len(grid[i]) or grid[i][j] != '1' or (i, j) in visited_map: 
                return 
            visited_map.add((i, j))
            for (x, y) in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]: 
                dfs(x, y, visited_map) 
        res = 0 
        visited_map = set() 
        for i in range(len(grid)): 
            for j in range(len(grid[i])): 
                if grid[i][j] == '1' and (i, j) not in visited_map: 
                    res += 1 
                    dfs(i, j, visited_map)
        return res 
        '''

        # bfs 
        res = 0 
        queue = deque([]) 
        visited_map = set() 
        m, n = len(grid), len(grid[0])
        
        for i in range(m):
            for j in range(n): 
                if grid[i][j] == '1' and (i, j) not in visited_map: 
                    res += 1
                    queue.append((i, j)) 
                    while queue: 
                        x, y = queue.popleft() 
                        if (x, y) in visited_map: continue 
                        visited_map.add((x, y))
                        for (u, v) in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]: 
                            if 0<=u<m and 0<=v<n and (u, v) not in visited_map and grid[u][v] == '1': 
                                queue.append((u, v)) 
                                
        return res 




























        
        # BFS 
        # O(MN) time and space complexity 

        num_of_islands = 0 
        queue = deque([])
        visited_map = set()
        m, n = len(grid), len(grid[0])
        for i in range(m):
            for j in range(n): 
                if grid[i][j] == '1' and (i, j) not in visited_map:
                    num_of_islands += 1 
                    queue.append((i, j)) 
                    visited_map.add((i, j)) 
                    while queue: 
                        row_idx, col_idx = queue.popleft()
                        for (x, y) in [(row_idx-1, col_idx), (row_idx+1, col_idx), (row_idx, col_idx-1), (row_idx, col_idx+1)]: 
                            if 0<=x<m and 0<=y<n and grid[x][y] == '1' and (x, y) not in visited_map: 
                                queue.append((x, y))
                                visited_map.add((x, y)) 
        return num_of_islands 

















        # Do dfs and assume that we cannot change the grid 
        # Time Complexity O(MN)
        # Space Complexity O(MN)
        def dfs(i:int, j:int, visited_map:dict) -> None: 
            if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[i]) or (i, j) in visited_map or grid[i][j] != '1': 
                return 
            visited_map.add((i,j))
            for (x, y) in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]: 
                dfs(x, y, visited_map)

        num_of_islands = 0 
        visited_map = set()
        for i in range(len(grid)): 
            for j in range(len(grid[i])): 
                if grid[i][j] == '1' and (i, j) not in visited_map: 
                    num_of_islands += 1 
                    dfs(i, j, visited_map)
        return num_of_islands

















        '''
        seen = set()
        queue = deque([])
        res = 0
        for i in range(len(grid)):
            for j in range(len(grid[i])):
                if grid[i][j] =='0' or (i,j) in seen:
                    continue
                res += 1
                queue.append((i,j))
                while queue:
                    m, n = queue.popleft()
                    for x, y in [(m+1,n),(m-1,n),(m,n+1),(m,n-1)]:
                        if (x,y) not in seen and len(grid)>x>=0 and len(grid[0])>y>=0 and grid[x][y] == '1':
                            queue.append((x,y))
                            seen.add((x,y))
        return res

        '''






# goal, find all the valid islands 
# method: DFS, BFS O(N*M) both time and space 
# Let us do DFS 
        # bfs 
        # seen = set() 
        # queue = deque([])
        # res = 0 
        # for i in range(len(grid)):
        #     for j in range(len(grid[i])): 
        #         if grid[i][j] == '0' or (i,j) in seen: 
        #             continue 
        #         res +=1 
        #         queue.append((i,j)) 
        #         while queue: 
        #             m, n = queue.popleft() 
        #             for x, y in [(m-1, n), (m+1, n), (m, n+1), (m, n-1)]: 
        #                 if 0<=x<len(grid) and 0<=y<len(grid[0]) and grid[x][y] == '1' and (x, y) not in seen: 
        #                     seen.add((x, y))
        #                     queue.append((x,y))
        # return res  





        '''
        def dfs(grid, i, j, seen): 
            if i<0 or j<0 or i>=len(grid) or j>=len(grid[i]) or grid[i][j]=='0' or (i, j) in seen: 
                return 
            seen.add((i,j))
            dfs(grid, i+1, j, seen)  
            dfs(grid, i-1, j, seen)
            dfs(grid, i, j+1, seen)
            dfs(grid, i, j-1, seen)
        res = 0 
        m, n = len(grid), len(grid[0])
        seen = set()
        for i in range(m):
            for j in range(n):
                if grid[i][j] == "0" or (i, j) in seen: 
                    continue 
                dfs(grid, i, j, seen)
                res+=1
        return res 
        ''' 
21871