1. Can there be other numbers in the grid?
2. What is the range of m and n?
3. What is considered an island? Do diagonals count?
4. What causes an island to be separate from another island?

1. Initial thought is that this seems like a graph problem and we want to find the number of distinct components. Let's hold that thought before diving deeper.
2. The brute force solution would be to go through each grid position and see if it is an island or water. If it is water, we move on. If it is an island, we keep track of that but we need to see if the island is bigger than the current spot. This leads itself into a graph traversal algorithm; lets go with depth-first search to avoid a queue and since we don't need the benefits of breadth-first. The key thing here is to keep track of visited spots so we don't wind up in an endless recursion.
3. Is there a better solution? Finding distinct sets can be done via the union-find data structure. Since this problem gives us a static grid, we don't get the true benefits of union-find which lets us easily adjust for dynamic updates. We can stick with the graph traversal since both solution would require us to reach all indexes in the grid anyway and the traversal is easier to implement.
4. One final note is that the grid looks like an adjacency matrix but it isn't quite one. We know from the problem statement that each grid position will have 4 potential edges (up, down, left, right).

def numIslands(self, grid: List[List[str]]) -> int:
        
        visited = set()
        num_islands = 0
        DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        
        def _dfsForIsland(position, visited):
            if position not in visited and grid[position[0]][position[1]] == '1':
                visited.add(position)
                for dir in DIRS:
                    new_position = (position[0] + dir[0], position[1] + dir[1])
                    if new_position[0] >= 0 and new_position[0] < len(grid) and new_position[1] >= 0 and new_position[1] < len(grid[0]):
                        _dfsForIsland(new_position, visited)
            
            
        for row in range(len(grid)):
            for column in range(len(grid[0])):
                position = (row, column)
                if position in visited:
                    continue
                if grid[row][column] == '1':
                    
                    _dfsForIsland(position, visited)
                    num_islands += 1
                    
        return num_islands

1. All 0s
2. All 1s
3. Test diagonal cases
4. One row grid
5. One column grid

m = rows in grid
n = columns in grid

We visit each node at least once in the double for loop. We can reach a node another time while we traverse as far as we can to explore each island. However, we can reach more than that so it becomes O(2mn) which becomes O(mn).

Space is O(mn) due to the stack space of recursion.

1. BFS has better space complexity than DFS while sharing the same complexity. In retrospect, this should have been considered during design.
2. Here is an interesting union-find solution.
3. An interesting option is to not used a visited set but modify the grid in-place to prevent unlimited recursion.