Solving Number Of Islands Using A Depth-First Search 🏝️
Tags: algorithms, python
Published: 2020-09-10 00:18:12

Today's problem is a pretty common interview question on Leetcode called [Number Of Islands](https://leetcode.com/problems/number-of-islands/).

# The Question
> Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island 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.


# The Approach
I'll be honest, I did not immediately jump to thinking of using a Depth-First Search for this problem. I initially thought of the brute force approach of iterating through each element in the grid, and keeping track of all adjacent elements in some other data structure. I had learned about both DFS and BFS in the context of graphs and trees, so it didn't instantly click that a DFS or BFS algorithm would be appropriate here. 

Once I landed on using a DFS algorithm, I needed to figure out how to make it applicable to this particular problem. I knew I'd want to start in the upper-left corner of the grid (at coordinates 0, 0), and do _something_ once I encountered a grid space that equaled 1. If we encounter a grid space that equals 1, then we know we've hit an island, and we'll need to explore the surrounding grid elements to see just how large this island is.

The rough, overall plan of attack is to iterate through our grid, and whenever we find a '1', flip the '1' to a '0' and then run DFS on all adjacent spaces until we've exhausted the entire grid. Running DFS recursively using a starting space that equals 1 should allow us to obtain the 'total size' of the island, which we could then use to actually keep a running count of the total number of islands. 

# The Solution
Almost always, the first thing I'll do before diving into the meat of the algorithm is to think of possible edge cases. I usually don't catch all of them at this stage, but the usual edge cases I'll write first is if the input is 0, empty, null, None, etc. 

```python
def num_islands(grid: List[List[str]]) -> int:
    # variable to hold the number of islands
    island_count = 0
        
    # first check if there are values in the grid
    if not grid:
        return island_count
```

Next, I want to set the grid length and width, to ensure that my solution will never reach out of bounds. I'll do this by setting `m` and `n`, respectively.

```python
    # m will represent the number of rows in our grid
    m = len(grid)

    # n will represent the number of columns in our grid
    n = len(grid[0])
```

Now that I've got my boundaries all squared away, it's time to move onto the meat of the solution -- writing a Depth-First Search algorithm. There are plenty of great resources online with explanations and code samples of a DFS, ranging from [GeeksforGeeks](https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/), [basecs](https://medium.com/basecs/deep-dive-through-a-graph-dfs-traversal-8177df5d0f13) and more, so I won't go over the details here. 
 
```python
    def dfs(i, j):
        # check if i and j are still on the grid
        # check if the current spot doesn't already equal 1
        if(i < 0 or j < 0 or i >= m or j >= n or grid[i][j] != "1"):
            return
            
        # otherwise
        else:
            # set current grid space to 0
            grid[i][j] = 0
            # run dfs on all surrounding elements
            dfs(i - 1, j)
            dfs(i + 1, j)
            dfs(i, j - 1)
            dfs(i, j + 1)
```

I am using a helper function to implement the DFS, and the function will accept parameters `i` and `j` that represent a current grid coordinate. Let's say we encounter our first '1' at (3, 2), we would then call dfs(3, 2). 

Right off the bat we'll check if the position is valid, and check that the current spot doesn't already equal 1. If any of those cases are true, we can return out early. We then need to check if the grid space is 0 (meaning it is a water space) we can also exit out of the function. 

Otherwise, the current grid space must be equal to '1', so we will flip that to a '0' and recursively call our `dfs` helper function on all adjacent elements (up, down, left, right). 

Honestly, at this point, most of the hard work is over! 🎉 We just need to write the code to iterate through the grid and identify those 1's! 

```python
    # initial for loop to iterate through the grid
        for i in range(m):
            # iterating through each row
            for j in range(n):
                # if current grid space is 1
                if(grid[i][j] == "1"):
                    # increment island count
                    island_count += 1
                    # run dfs using the current spot as the root
                    dfs(i, j)
                # if grid space is 0
                else:
                    # continue searching
                    continue
                    
        # return count when done          
        return island_count
``` 

Here it is, in it's final form!
```python
    def num_islands(grid: List[List[str]]) -> int:
        # variable to hold the number of islands
        island_count = 0
        
        # first check if there are values in the grid
        if not grid:
            return island_count
        
        # set the lengths:
        # m represents the number of rows
        m = len(grid)
        # n represents the number of columns
        n = len(grid[0])
        
        # definition of depth-first search
        def dfs(i, j):
            # check if i and j are still on the grid
            # check if the current grid spot doesn't already equal 1
            if(i < 0 or j < 0 or i >= m or j >= n or grid[i][j] != "1"):
                return

            # otherwise
            else:
                # set current grid space to 0
                grid[i][j] = 0
                # run dfs on all surrounding elements
                dfs(i - 1, j)
                dfs(i + 1, j)
                dfs(i, j - 1)
                dfs(i, j + 1)
        
        # initial for loop to iterate through the grid
        for i in range(m):
            # iterating through each row
            for j in range(n):
                # if current grid space is 1
                if(grid[i][j] == "1"):
                    # increment island count
                    island_count += 1
                    # run dfs using the current spot as the root
                    dfs(i, j)
                # if grid space is 0
                else:
                    # continue searching
                    continue
                    
        # return count when done          
        return island_count
```

# The Complexity

The time complexity for this implementation is O(mn), where `m` is the number of rows in our grid and `n` is the number of columns.