<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:
    def numIslands(self, grid: List[List[str]]) -> int:
        '''
        Consider 2 steps: 
        1. Loop through the island, and remove it if it is connected to adjacent lands
            a) If a piece of land (i,j) is connect towards the left (i,j-1) or up, it should not be double-counted
            b) Finally leaving 1 piece of land as the "index" of the island to be counted.
        2. Sum up the list to get the total number of island (This should be very fast). (Or count them along the way)
        # This could have issue if there are two branches...

        Consider the alternative steps:
        0. The total island is: Total pieces of lands - adjacency pairs (i.e. each non counting land must be connected )
        1. For each adjacent pair, we should reduce the number of  by one, because this should not be counted...

        # Still could be double counted. 
        Consider another alternative steps... Consider positions as equivalent classes... Each extending, and then merge. Record the equivalent classes.
        '''
        # First catch the empty case
        if len(grid) == 0 or len(grid[0])==0:
            return 0
        # Find the size of the grid and loop through the rows and columns
        m, n = len(grid), len(grid[0])
        #new_grid = [[0,]*m]*n
        #print(new_grid)
        class_equiv_dict = {}
        n_islands = 0
        class_i = 2
        for i in range(m):
            for j in range(n):
                current_class = int(grid[i][j])
                # Create a new class if not already
                if current_class == 0:
                    grid[i][j] = current_class
                    continue;
                elif current_class == 1:
                    grid[i][j] = class_i
                    current_class = class_i
                    class_equiv_dict[class_i] = [class_i]
                    class_i+=1
                    n_islands+=1
                
                if type(class_equiv_dict[current_class]) is int:
                    current_class = class_equiv_dict[current_class]
                current_class_list = class_equiv_dict[current_class] 
                #print(i,j, current_class, type(class_equiv_dict[current_class]) is int)
                #print(class_equiv_dict)
                # Pass on the class index:
                if not(i+1>=m):
                    next_class = int(grid[i+1][j])
                    if next_class == 1:
                        grid[i+1][j] = current_class                    
                    elif next_class>1:
                        if type(class_equiv_dict[next_class]) is int:
                            next_class = class_equiv_dict[next_class]
                        # Check if already equivalent
                        if next_class in current_class_list:
                            pass
                        # If not already equivalent, establish equivalence relation
                        else:
                            n_islands-=1
                            class_equiv_dict[current_class] += class_equiv_dict[next_class]
                            for item in class_equiv_dict[next_class]:
                                class_equiv_dict[item] = current_class
                            # To-do Further save space if we only save the smallest indices.
                    #print("next_class", i+1, j, grid[i+1][j])
                if not(j+1>=n):
                    next_class = int(grid[i][j+1])
                    if next_class == 1:
                        grid[i][j+1] = current_class
                    elif next_class>1:
                        if type(class_equiv_dict[next_class]) is int:
                            next_class = class_equiv_dict[next_class]
                        # Check if already equivalent
                        if next_class in current_class_list:
                            pass
                        else:
                            n_islands-=1
                            class_equiv_dict[current_class] += class_equiv_dict[next_class]
                            for item in class_equiv_dict[next_class]:
                                class_equiv_dict[item] = current_class
                            # To-do Further save space if we only save the smallest indices.
                    #print("next_class", i, j+1, grid[i][j+1])
        '''
        print(n_islands)
        #print(grid)
        for item in grid:
            print(item)
        print(class_equiv_dict)
        '''
        return n_islands




20546