Jovian
⭐️
Sign In

DSA Course Project - Count the Islands using DFS

Assignment 4 - Final Course Project for jovian.ai Data Structures and Algorithms in Python course

https://jovian.ai/learn/data-structures-and-algorithms-in-python

This notebook solves the following problem using Depth First Search:

Given a boolean 2D matrix, find the number of islands. A group of connected 1s forms an island.

Source: https://www.geeksforgeeks.org/find-number-of-islands/

In [7]:
project_name = 'Count the Islands using DFS' # give it an appropriate name
In [8]:
!pip install jovian --upgrade --quiet
In [9]:
import jovian
from timeit import default_timer as timer
from textwrap import dedent
import math
In [10]:
jovian.commit(project=project_name)
[jovian] Detected Colab notebook... [jovian] Uploading colab notebook to Jovian... [jovian] Capturing environment.. [jovian] Committed successfully! https://jovian.ai/gtaljaard/count-the-islands-using-dfs

Problem Statement

Given a boolean 2D matrix, find the number of islands. A group of connected 1s forms an island. For example, the below matrix contains 5 islands

Example:

$ \begin{align*} \pmb{Input: } \pmb{ mat[][]} = {} & \begin{bmatrix} \pmb{1, 1, 0, 0, 0} \\ \pmb{0, 1, 0, 0, 1} \\ \pmb{1, 0, 0, 1, 1} \\ \pmb{0, 0, 0, 0, 0} \\ \pmb{1, 0, 1, 0, 1} \end{bmatrix}. \end{align*} $

$ \begin{align*} \pmb{Output : } \pmb{5} \end{align*} $

Source: https://www.geeksforgeeks.org/find-number-of-islands/

The Method

Here's the systematic strategy we'll apply for solving problems:

  1. State the problem clearly. Identify the input & output formats.
  2. Come up with some example inputs & outputs. Try to cover all edge cases.
  3. Come up with a correct solution for the problem. State it in plain English.
  4. Implement the solution and test it using example inputs. Fix bugs, if any.
  5. Analyze the algorithm's complexity and identify inefficiencies, if any.
  6. Apply the right technique to overcome the inefficiency. Repeat steps 3 to 6.

This approach is explained in detail in Lesson 1 of the course. Let's apply this approach step-by-step.

Solution

1. State the problem clearly. Identify the input & output formats.

Given a 2D matrix consisting of 1's and 0's, find the number of islands. A group of connected 1s forms an island.

Example:

$ \begin{align*} \pmb{Input: } \pmb{ mat[][]} = {} & \begin{bmatrix} \pmb{0, 0, 0, 0, 1} \\ \pmb{0, 1, 0, 0, 0} \\ \pmb{1, 0, 0, 0, 0} \\ \pmb{0, 0, 0, 0, 0} \\ \pmb{0, 0, 0, 0, 1} \end{bmatrix}. \end{align*} $

$ \begin{align*} \pmb{Output : } \pmb{3} \end{align*} $



Based on the above, we can now create a signature of our function:

In [11]:
# Create a function signature here. The body of the function can contain a single statement: pass
def check_Islands(matrix):
    pass

Save and upload your work before continuing.

In [12]:
import jovian
In [13]:
jovian.commit()
[jovian] Detected Colab notebook... [jovian] Uploading colab notebook to Jovian... [jovian] Capturing environment.. [jovian] Committed successfully! https://jovian.ai/gtaljaard/count-the-islands-using-dfs

2. Come up with some example inputs & outputs. Try to cover all edge cases.

Our function should be able to handle any set of valid inputs we pass into it.

We'll express our test cases as dictionaries, to test them easily. Each dictionary will contain 2 keys: input (a dictionary itself containing one key for each argument to the function and output (the expected result from the function).

In [14]:
#Original problem statement 2D binary matrix containing 5 islands
test0 = {
    'input': {
        'mat': [[1, 1, 0, 0, 0],
                [0, 1, 0, 0, 1],
                [1, 0, 0, 1, 1],
                [0, 0, 0, 0, 0],
                [1, 0, 1, 0, 1]]
    },
    'output': 5
}
In [15]:
#All 1's
test1 = {
    'input': {
        'mat': [[1, 1, 1, 1, 1],
                [1, 1, 1, 1, 1],
                [1, 1, 1, 1, 1],
                [1, 1, 1, 1, 1],
                [1, 1, 1, 1, 1]]
    },
    'output': 1
}
In [16]:
#All 0
test2 = {
    'input': {
        'mat': [[0, 0, 0, 0, 0],
                [0, 0, 0, 0, 0],
                [0, 0, 0, 0, 0],
                [0, 0, 0, 0, 0],
                [0, 0, 0, 0, 0]]
    },
    'output': 0
}
In [17]:
# 1 on diagonal
test3 = {
    'input': {
        'mat': [[1, 0, 0, 0, 0],
                [0, 1, 0, 0, 0],
                [0, 0, 1, 0, 0],
                [0, 0, 0, 1, 0],
                [0, 0, 0, 0, 1]]
    },
    'output': 1
}
In [18]:
# 2 islands
test4 = {
    'input': {
        'mat': [[1, 0, 0, 0, 0],
                [0, 0, 0, 0, 0],
                [0, 0, 1, 0, 0],
                [0, 0, 0, 1, 0],
                [0, 0, 0, 0, 1]]
    },
    'output': 2
}
In [19]:
# 3 islands
test5 = {
    'input': {
        'mat': [[0, 0, 0, 0, 1],
                [0, 0, 0, 0, 0],
                [0, 0, 0, 0, 0],
                [0, 0, 0, 0, 0],
                [1, 0, 0, 0, 1]]
    },
    'output': 3
}
In [20]:
# 4 islands
test6 = {
    'input': {
        'mat': [[0, 1, 0, 0, 0],
                [0, 1, 0, 0, 1],
                [1, 0, 0, 1, 1],
                [0, 0, 0, 0, 0],
                [1, 0, 1, 0, 0]]
    },
    'output': 4
}
In [21]:
# 1 islands
test7 = {
    'input': {
        'mat': [[0, 1, 0, 0, 0],
                [0, 1, 0, 0, 1],
                [1, 0, 1, 1, 1],
                [0, 1, 1, 0, 0],
                [1, 0, 1, 0, 0]]
    },
    'output': 1
}
In [22]:
# 1 islands - doughnut shape - we have a round island, with a lake in the middle
test8 = {
    'input': {
        'mat': [[0, 0, 1, 0, 0],
                [0, 1, 0, 1, 0],
                [1, 0, 0, 0, 1],
                [0, 1, 0, 1, 0],
                [0, 0, 1, 0, 0]]
    },
    'output': 1
}
In [23]:
# 1 islands - J shape - DFS has to explore edge to edge, and come back up again around the curve of the J
test9 = {
    'input': {
        'mat': [[1, 1, 1, 1, 1],
                [0, 0, 0, 1, 0],
                [0, 0, 0, 1, 0],
                [0, 1, 0, 1, 0],
                [0, 0, 1, 1, 0]]
    },
    'output': 1
}
In [24]:
# empty matrix
test10 = {
    'input': {
        'mat': [[],[]]
    },
    'output': 0
}

Create one test case for each of the scenarios listed above. We'll store our test cases in an array called tests.

In [25]:
tests = [test0, test1, test2, test3, test4, test5, test6, test7, test8, test9, test10]
In [26]:
tests
Out[26]:
[{'input': {'mat': [[1, 1, 0, 0, 0],
    [0, 1, 0, 0, 1],
    [1, 0, 0, 1, 1],
    [0, 0, 0, 0, 0],
    [1, 0, 1, 0, 1]]},
  'output': 5},
 {'input': {'mat': [[1, 1, 1, 1, 1],
    [1, 1, 1, 1, 1],
    [1, 1, 1, 1, 1],
    [1, 1, 1, 1, 1],
    [1, 1, 1, 1, 1]]},
  'output': 1},
 {'input': {'mat': [[0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0]]},
  'output': 0},
 {'input': {'mat': [[1, 0, 0, 0, 0],
    [0, 1, 0, 0, 0],
    [0, 0, 1, 0, 0],
    [0, 0, 0, 1, 0],
    [0, 0, 0, 0, 1]]},
  'output': 1},
 {'input': {'mat': [[1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0],
    [0, 0, 0, 1, 0],
    [0, 0, 0, 0, 1]]},
  'output': 2},
 {'input': {'mat': [[0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [1, 0, 0, 0, 1]]},
  'output': 3},
 {'input': {'mat': [[0, 1, 0, 0, 0],
    [0, 1, 0, 0, 1],
    [1, 0, 0, 1, 1],
    [0, 0, 0, 0, 0],
    [1, 0, 1, 0, 0]]},
  'output': 4},
 {'input': {'mat': [[0, 1, 0, 0, 0],
    [0, 1, 0, 0, 1],
    [1, 0, 1, 1, 1],
    [0, 1, 1, 0, 0],
    [1, 0, 1, 0, 0]]},
  'output': 1},
 {'input': {'mat': [[0, 0, 1, 0, 0],
    [0, 1, 0, 1, 0],
    [1, 0, 0, 0, 1],
    [0, 1, 0, 1, 0],
    [0, 0, 1, 0, 0]]},
  'output': 1},
 {'input': {'mat': [[1, 1, 1, 1, 1],
    [0, 0, 0, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 1, 1, 0]]},
  'output': 1},
 {'input': {'mat': [[], []]}, 'output': 0}]

3. Come up with a correct solution for the problem. State it in plain English.

Problem - Given a boolean 2D matrix, find the number of islands. A group of connected 1's forms an island.

We traverse the matrix of size n*m, and if we find a "1" we recursively check if surrounding cells are 1 until we have discovered the complete island. We then increase the island count.

MAIN FUNCTION

  1. island_count = 0
  2. Visit each cell in matrix of size n*m, starting at position (0,0) and ending at position (n,m).
  3. For each cell (i,j) in matrix check:
  4. IF the cell(i,j) is an island
    1. THEN Start depth first search (DFS) at cell (i,j) using function count_islands_dfs(matrix, i, j)
    2. When DFS call returns, islands_count = island_count + 1.
  5. If all cells have been evaluated, return island_count.

DISCOVER ISLANDS USING DFS RECURSION

function count_islands_dfs(matrix, i, j)

function count_islands_dfs is a recursive function which will evaluate each adjacent neighbour cell of cell (i,j).

  1. IF cell (i,j) is an island, and is a valid cell (ie at edges you cannot visit cells outside of matrix), and has not been visited
    1. Designate cell as visited, by setting value to -1
    2. Recursively call DFS function count_islands_dfs for neighbour cells
  2. ELSE continue to next neighbour of original cell (i,j).
  3. When DFS recursive calls are finished exit DFS

IS A CELL VALID FOR EVALUATION? - HELPER FUNCTION

function ValidCell(matrix, x,y)

A cell can be evaluated recursively if:

  1. it is inside the edges of the matrix
  2. is an island
  3. has not been visited before
In [27]:
jovian.commit()
[jovian] Detected Colab notebook... [jovian] Uploading colab notebook to Jovian... [jovian] Capturing environment.. [jovian] Committed successfully! https://jovian.ai/gtaljaard/count-the-islands-using-dfs

4. Implement the solution and test it using example inputs. Fix bugs, if any.

In [28]:
#Check if cells next to current cell are island components using depth first search in a recursive manner

#Check if the value at position x,y is an island ie is the value == 1
#If the value as position is and Island, mark it as -1 so we do not visit it again
#Check if immediate surrounding cells are islands, recursively
def count_islands_dfs(matrix, x, y):
   if (matrix[x][y] == 1): #Is it an Island?
      matrix[x][y] = -1    #Mark it as visited, so we do not visit again
      #Check surrounding cells - are they Islands?
      #Is a surrounding cell is an island, recursively count islands
      if(valid_cell(matrix, x + 1, y)):
                count_islands_dfs(matrix, x + 1, y)
      if(valid_cell(matrix, x, y + 1)):
                count_islands_dfs(matrix, x , y + 1)
      if(valid_cell(matrix, x - 1, y)):
                count_islands_dfs(matrix, x - 1 , y)
      if(valid_cell(matrix, x, y - 1)):
                count_islands_dfs(matrix, x , y - 1)    
      if(valid_cell(matrix, x + 1, y + 1)):
                count_islands_dfs(matrix, x + 1 , y + 1)     
      if(valid_cell(matrix, x - 1, y - 1)):
                count_islands_dfs(matrix, x - 1 , y - 1)          
      if(valid_cell(matrix, x + 1, y - 1)):
                count_islands_dfs(matrix, x + 1 , y - 1)          
      if(valid_cell(matrix, x - 1, y + 1)):
                count_islands_dfs(matrix, x - 1 , y + 1)          
In [29]:
#Is the cell we want to check as an Island actually a valid cell in the ranges of the matrix?
#Have we visited the cell before, in which case it would have been marked as -1
#Is the cell an Island ie is the value == 1?
def valid_cell(matrix, x, y):
  return x>=0 and y>=0 and x<len(matrix) and y<len(matrix[0]) and matrix[x][y]!=-1 and matrix[x][y]==1
In [30]:
#Check valid_cell function for correctness
mat = [[1, 1, 0, 0, 0],
       [0, 1, 0, 0, 1],
       [1, 0, 0, 1, 1],
       [0, 0, 0, 0, 0],
       [1, 0, 1, 0, 1]]

valid_cell(mat,4,4)
Out[30]:
True
In [31]:
#MAIN FUNCTION
#Given a boolean 2D matrix, find the number of islands. A group of connected 1's forms an island.
#We traverse the matrix, and if we find a "1" we recursively check if surrounding cells are 1 until we have discovered the complete island. We then increase the island count.

def check_Islands(mat):       
  print('Input matrix in check_Islands function ', mat)
  island_count = 0

  start = timer()

  for i in range(len(mat)):
      for j in range (len(mat[i])):
          if(mat[i][j] == 1):        
              count_islands_dfs(mat,i,j)
              island_count = island_count + 1
  
  end = timer()
  runtime = math.ceil((end - start)*1e6)/1000
 
  print('Time taken ', runtime)
  print('Islands counted ', island_count)
  print('Original matrix after operations', mat)
  print('.')
  return island_count
In [32]:

#Check the matrix originally provided in the question containing 5 islands for correctness
mat = [[1, 1, 0, 0, 0],
       [0, 1, 0, 0, 1],
       [1, 0, 0, 1, 1],
       [0, 0, 0, 0, 0],
       [1, 0, 1, 0, 1]]

check_Islands(mat)
Input matrix in check_Islands function [[1, 1, 0, 0, 0], [0, 1, 0, 0, 1], [1, 0, 0, 1, 1], [0, 0, 0, 0, 0], [1, 0, 1, 0, 1]] Time taken 0.074 Islands counted 5 Original matrix after operations [[-1, -1, 0, 0, 0], [0, -1, 0, 0, -1], [-1, 0, 0, -1, -1], [0, 0, 0, 0, 0], [-1, 0, -1, 0, -1]] .
Out[32]:
5
In [33]:
from jovian.pythondsa import evaluate_test_cases
In [34]:
evaluate_test_cases(check_Islands, tests)
TEST CASE #0 Input matrix in check_Islands function [[1, 1, 0, 0, 0], [0, 1, 0, 0, 1], [1, 0, 0, 1, 1], [0, 0, 0, 0, 0], [1, 0, 1, 0, 1]] Time taken 0.073 Islands counted 5 Original matrix after operations [[-1, -1, 0, 0, 0], [0, -1, 0, 0, -1], [-1, 0, 0, -1, -1], [0, 0, 0, 0, 0], [-1, 0, -1, 0, -1]] . Input: {'mat': [[-1, -1, 0, 0, 0], [0, -1, 0, 0, -1], [-1, 0, 0, -1, -1], [0, 0, 0, 0, 0], [-1, 0, -1, 0, -... Expected Output: 5 Actual Output: 5 Execution Time: 0.302 ms Test Result: PASSED TEST CASE #1 Input matrix in check_Islands function [[1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1]] Time taken 0.172 Islands counted 1 Original matrix after operations [[-1, -1, -1, -1, -1], [-1, -1, -1, -1, -1], [-1, -1, -1, -1, -1], [-1, -1, -1, -1, -1], [-1, -1, -1, -1, -1]] . Input: {'mat': [[-1, -1, -1, -1, -1], [-1, -1, -1, -1, -1], [-1, -1, -1, -1, -1], [-1, -1, -1, -1, -1], [-1... Expected Output: 1 Actual Output: 1 Execution Time: 0.373 ms Test Result: PASSED TEST CASE #2 Input matrix in check_Islands function [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]] Time taken 0.009 Islands counted 0 Original matrix after operations [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]] . Input: {'mat': [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]} Expected Output: 0 Actual Output: 0 Execution Time: 6.727 ms Test Result: PASSED TEST CASE #3 Input matrix in check_Islands function [[1, 0, 0, 0, 0], [0, 1, 0, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, 1, 0], [0, 0, 0, 0, 1]] Time taken 0.048 Islands counted 1 Original matrix after operations [[-1, 0, 0, 0, 0], [0, -1, 0, 0, 0], [0, 0, -1, 0, 0], [0, 0, 0, -1, 0], [0, 0, 0, 0, -1]] . Input: {'mat': [[-1, 0, 0, 0, 0], [0, -1, 0, 0, 0], [0, 0, -1, 0, 0], [0, 0, 0, -1, 0], [0, 0, 0, 0, -1]]} Expected Output: 1 Actual Output: 1 Execution Time: 0.237 ms Test Result: PASSED TEST CASE #4 Input matrix in check_Islands function [[1, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, 1, 0], [0, 0, 0, 0, 1]] Time taken 0.042 Islands counted 2 Original matrix after operations [[-1, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, -1, 0, 0], [0, 0, 0, -1, 0], [0, 0, 0, 0, -1]] . Input: {'mat': [[-1, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, -1, 0, 0], [0, 0, 0, -1, 0], [0, 0, 0, 0, -1]]} Expected Output: 2 Actual Output: 2 Execution Time: 0.239 ms Test Result: PASSED TEST CASE #5 Input matrix in check_Islands function [[0, 0, 0, 0, 1], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [1, 0, 0, 0, 1]] Time taken 0.03 Islands counted 3 Original matrix after operations [[0, 0, 0, 0, -1], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [-1, 0, 0, 0, -1]] . Input: {'mat': [[0, 0, 0, 0, -1], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [-1, 0, 0, 0, -1]]} Expected Output: 3 Actual Output: 3 Execution Time: 0.226 ms Test Result: PASSED TEST CASE #6 Input matrix in check_Islands function [[0, 1, 0, 0, 0], [0, 1, 0, 0, 1], [1, 0, 0, 1, 1], [0, 0, 0, 0, 0], [1, 0, 1, 0, 0]] Time taken 0.08 Islands counted 4 Original matrix after operations [[0, -1, 0, 0, 0], [0, -1, 0, 0, -1], [-1, 0, 0, -1, -1], [0, 0, 0, 0, 0], [-1, 0, -1, 0, 0]] . Input: {'mat': [[0, -1, 0, 0, 0], [0, -1, 0, 0, -1], [-1, 0, 0, -1, -1], [0, 0, 0, 0, 0], [-1, 0, -1, 0, 0]]} Expected Output: 4 Actual Output: 4 Execution Time: 0.285 ms Test Result: PASSED TEST CASE #7 Input matrix in check_Islands function [[0, 1, 0, 0, 0], [0, 1, 0, 0, 1], [1, 0, 1, 1, 1], [0, 1, 1, 0, 0], [1, 0, 1, 0, 0]] Time taken 0.089 Islands counted 1 Original matrix after operations [[0, -1, 0, 0, 0], [0, -1, 0, 0, -1], [-1, 0, -1, -1, -1], [0, -1, -1, 0, 0], [-1, 0, -1, 0, 0]] . Input: {'mat': [[0, -1, 0, 0, 0], [0, -1, 0, 0, -1], [-1, 0, -1, -1, -1], [0, -1, -1, 0, 0], [-1, 0, -1, 0,... Expected Output: 1 Actual Output: 1 Execution Time: 0.251 ms Test Result: PASSED TEST CASE #8 Input matrix in check_Islands function [[0, 0, 1, 0, 0], [0, 1, 0, 1, 0], [1, 0, 0, 0, 1], [0, 1, 0, 1, 0], [0, 0, 1, 0, 0]] Time taken 0.04 Islands counted 1 Original matrix after operations [[0, 0, -1, 0, 0], [0, -1, 0, -1, 0], [-1, 0, 0, 0, -1], [0, -1, 0, -1, 0], [0, 0, -1, 0, 0]] . Input: {'mat': [[0, 0, -1, 0, 0], [0, -1, 0, -1, 0], [-1, 0, 0, 0, -1], [0, -1, 0, -1, 0], [0, 0, -1, 0, 0]]} Expected Output: 1 Actual Output: 1 Execution Time: 0.147 ms Test Result: PASSED TEST CASE #9 Input matrix in check_Islands function [[1, 1, 1, 1, 1], [0, 0, 0, 1, 0], [0, 0, 0, 1, 0], [0, 1, 0, 1, 0], [0, 0, 1, 1, 0]] Time taken 0.047 Islands counted 1 Original matrix after operations [[-1, -1, -1, -1, -1], [0, 0, 0, -1, 0], [0, 0, 0, -1, 0], [0, -1, 0, -1, 0], [0, 0, -1, -1, 0]] . Input: {'mat': [[-1, -1, -1, -1, -1], [0, 0, 0, -1, 0], [0, 0, 0, -1, 0], [0, -1, 0, -1, 0], [0, 0, -1, -1,... Expected Output: 1 Actual Output: 1 Execution Time: 0.153 ms Test Result: PASSED TEST CASE #10 Input matrix in check_Islands function [[], []] Time taken 0.002 Islands counted 0 Original matrix after operations [[], []] . Input: {'mat': [[], []]} Expected Output: 0 Actual Output: 0 Execution Time: 0.1 ms Test Result: PASSED SUMMARY TOTAL: 11, PASSED: 11, FAILED: 0
Out[34]:
[(5, True, 0.302),
 (1, True, 0.373),
 (0, True, 6.727),
 (1, True, 0.237),
 (2, True, 0.239),
 (3, True, 0.226),
 (4, True, 0.285),
 (1, True, 0.251),
 (1, True, 0.147),
 (1, True, 0.153),
 (0, True, 0.1)]
In [35]:
jovian.commit()
[jovian] Detected Colab notebook... [jovian] Uploading colab notebook to Jovian... [jovian] Capturing environment.. [jovian] Committed successfully! https://jovian.ai/gtaljaard/count-the-islands-using-dfs

5. Analyze the algorithm's complexity and identify inefficiencies, if any.

Every cell in the array has to be be visited once, and therefore the Time Complexity of matrix [m,n] is O(mn).

A matrix of size [m,n] has to be manipulated to track if each cell is part of an island. Space complexity of matrix [m,n] is O(mn).

DFS is an efficient algorithm to solve this problem. Alternative mechanisms such as BFS can be considered, but is of similar Time & Space complexity.

The function [count_islands_dfs(matrix, x, y)] has 8 'if' statements. This function can be improved and made more readable with less logic by reducing the number of 'if' statements.

In the function [check_Islands(matrix)] we destroy the input data by operating on the original data. It is best practise to make a copy and not operate on the original data. This allows the input data to be re-used and checked afterwards. This function can be improved by making a copy of the original data.

6. Apply the right technique to overcome the inefficiency. Repeat steps 3 to 6.

Create test cases

In [36]:
#Original problem statement 2D binary matrix containing 5 islands
test0 = {
    'input': {
        'mat': [[1, 1, 0, 0, 0],
                [0, 1, 0, 0, 1],
                [1, 0, 0, 1, 1],
                [0, 0, 0, 0, 0],
                [1, 0, 1, 0, 1]]
    },
    'output': 5
}
In [37]:
#All 1's
test1 = {
    'input': {
        'mat': [[1, 1, 1, 1, 1],
                [1, 1, 1, 1, 1],
                [1, 1, 1, 1, 1],
                [1, 1, 1, 1, 1],
                [1, 1, 1, 1, 1]]
    },
    'output': 1
}
In [38]:
#All 0
test2 = {
    'input': {
        'mat': [[0, 0, 0, 0, 0],
                [0, 0, 0, 0, 0],
                [0, 0, 0, 0, 0],
                [0, 0, 0, 0, 0],
                [0, 0, 0, 0, 0]]
    },
    'output': 0
}
In [39]:
# 1 on diagonal
test3 = {
    'input': {
        'mat': [[1, 0, 0, 0, 0],
                [0, 1, 0, 0, 0],
                [0, 0, 1, 0, 0],
                [0, 0, 0, 1, 0],
                [0, 0, 0, 0, 1]]
    },
    'output': 1
}
In [40]:
# 2 islands
test4 = {
    'input': {
        'mat': [[1, 0, 0, 0, 0],
                [0, 0, 0, 0, 0],
                [0, 0, 1, 0, 0],
                [0, 0, 0, 1, 0],
                [0, 0, 0, 0, 1]]
    },
    'output': 2
}
In [41]:
# 3 islands
test5 = {
    'input': {
        'mat': [[0, 0, 0, 0, 1],
                [0, 0, 0, 0, 0],
                [0, 0, 0, 0, 0],
                [0, 0, 0, 0, 0],
                [1, 0, 0, 0, 1]]
    },
    'output': 3
}
In [42]:
# 4 islands
test6 = {
    'input': {
        'mat': [[0, 1, 0, 0, 0],
                [0, 1, 0, 0, 1],
                [1, 0, 0, 1, 1],
                [0, 0, 0, 0, 0],
                [1, 0, 1, 0, 0]]
    },
    'output': 4
}
In [43]:
# 1 islands
test7 = {
    'input': {
        'mat': [[0, 1, 0, 0, 0],
                [0, 1, 0, 0, 1],
                [1, 0, 1, 1, 1],
                [0, 1, 1, 0, 0],
                [1, 0, 1, 0, 0]]
    },
    'output': 1
}
In [44]:
# 1 islands - doughnut shape - we have a round island, with a lake in the middle
test8 = {
    'input': {
        'mat': [[0, 0, 1, 0, 0],
                [0, 1, 0, 1, 0],
                [1, 0, 0, 0, 1],
                [0, 1, 0, 1, 0],
                [0, 0, 1, 0, 0]]
    },
    'output': 1
}
In [45]:
# 1 islands - J shape - DFS has to explore edge to edge, and come back up again around the curve of the J
test9 = {
    'input': {
        'mat': [[1, 1, 1, 1, 1],
                [0, 0, 0, 1, 0],
                [0, 0, 0, 1, 0],
                [0, 1, 0, 1, 0],
                [0, 0, 1, 1, 0]]
    },
    'output': 1
}
In [46]:
# empty matrix
test10 = {
    'input': {
        'mat': [[],[]]
    },
    'output': 0
}
In [47]:
tests = [test0, test1, test2, test3, test4, test5, test6, test7, test8, test9, test10]

7. Come up with a correct solution for the problem. State it in plain English.

Problem - Given a boolean 2D matrix, find the number of islands. A group of connected 1's forms an island.

We traverse the matrix of size m*n, and if we find a "1" we recursively check if surrounding cells are 1 until we have discovered the complete island. We then increase the island count.

In this improved traverse MAIN function we do not destroy the input data by operating on a copy of the original data. This is best practise and allows the input data to be re-used and checked afterwards.

In this improved DFS recursive function we used 1 'if' statement instead of 8 as in the original function

8. Implement the solution and test it using example inputs. Fix bugs, if any.

In [48]:
#Check if cells next to current cell are island components using depth first search in a recursive manner
#In this improved function we have replaced 8 'if' statements with 1 'if' to reduce function size and ensure efficient logic checking.

#Check if the value at position x,y is an island in the matrix that we have not visited before
#If the value as position is an Island, mark it as -1 so we do not visit it again
#Check if immediate surrounding cells are island components, recursively
def count_islands_dfs_improved(matrix, x, y):
    if valid_cell_improved(matrix, x , y):
      matrix[x][y] = -1
      count_islands_dfs_improved(matrix, x + 1, y)
      count_islands_dfs_improved(matrix, x , y + 1)
      count_islands_dfs_improved(matrix, x - 1 , y)
      count_islands_dfs_improved(matrix, x , y - 1)    
      count_islands_dfs_improved(matrix, x + 1 , y + 1)     
      count_islands_dfs_improved(matrix, x - 1 , y - 1)          
      count_islands_dfs_improved(matrix, x + 1 , y - 1)          
      count_islands_dfs_improved(matrix, x - 1 , y + 1)          
In [49]:
#Is the cell we want to check as an Island actually a valid cell in the ranges of the matrix?
#Have we visited the cell before, in which case it would have been marked as -1
#Is the cell an Island component ie is the value == 1?
def valid_cell_improved(matrix, x, y):
  return x>=0 and y>=0 and x<len(matrix) and y<len(matrix[0]) and matrix[x][y]!=-1 and matrix[x][y]==1
In [50]:
#MAIN FUNCTION
#Given a boolean 2D matrix, find the number of islands. A group of connected 1's forms an island.
#We traverse the matrix, and if we find a "1" we recursively check if surrounding cells are 1 until we have discovered the complete island. We then increase the island count.
#In this improved function we do not destroy the input data by operating on a copy of the original data. This is best practise and allows the input data to be re-used and checked afterwards.

def check_Islands_improved(mat):       
  print('Input matrix in check_Islands_improved function ', mat)
  island_count = 0

  #We do not destroy the input data by operating on a copy of the original data
  copy_mat = [[0 for i in range(len(mat[0]))] for j in range(len(mat))]
  for i in range(len(mat)):
      for j in range (len(mat[i])):
          copy_mat[i][j] = mat[i][j]
 
  start = timer()
 
  for i in range(len(copy_mat)):
      for j in range (len(copy_mat[i])):
          if(copy_mat[i][j] == 1):        
              count_islands_dfs_improved(copy_mat,i,j)
              island_count = island_count + 1
 
  end = timer()
  runtime = math.ceil((end - start)*1e6)/1000
 
  print('Time taken ', runtime)
  print('Islands counted ', island_count)  
  print('Original matrix', mat)
  print('Working matrix', copy_mat)
  print('.')
  return island_count
In [51]:
#Check and compare original and updated functions using the matrix originally provided in the question containing 5 islands for correctness
mat1 = [[1, 1, 0, 0, 0],
       [0, 1, 0, 0, 1],
       [1, 0, 0, 1, 1],
       [0, 0, 0, 0, 0],
       [1, 0, 1, 0, 1]]

check_Islands(mat1)

mat2 = [[1, 1, 0, 0, 0],
       [0, 1, 0, 0, 1],
       [1, 0, 0, 1, 1],
       [0, 0, 0, 0, 0],
       [1, 0, 1, 0, 1]]

check_Islands_improved(mat2)

mat3 = [[1, 1, 1, 1, 1],
       [1, 1, 1, 1, 1],
       [1, 1, 1, 1, 1],
       [1, 1, 1, 1, 1],
       [1, 1, 1, 1, 1]]

check_Islands(mat3)

mat4 = [[1, 1, 1, 1, 1],
       [1, 1, 1, 1, 1],
       [1, 1, 1, 1, 1],
       [1, 1, 1, 1, 1],
       [1, 1, 1, 1, 1]]

check_Islands_improved(mat4)

Input matrix in check_Islands function [[1, 1, 0, 0, 0], [0, 1, 0, 0, 1], [1, 0, 0, 1, 1], [0, 0, 0, 0, 0], [1, 0, 1, 0, 1]] Time taken 0.07 Islands counted 5 Original matrix after operations [[-1, -1, 0, 0, 0], [0, -1, 0, 0, -1], [-1, 0, 0, -1, -1], [0, 0, 0, 0, 0], [-1, 0, -1, 0, -1]] . Input matrix in check_Islands_improved function [[1, 1, 0, 0, 0], [0, 1, 0, 0, 1], [1, 0, 0, 1, 1], [0, 0, 0, 0, 0], [1, 0, 1, 0, 1]] Time taken 0.074 Islands counted 5 Original matrix [[1, 1, 0, 0, 0], [0, 1, 0, 0, 1], [1, 0, 0, 1, 1], [0, 0, 0, 0, 0], [1, 0, 1, 0, 1]] Working matrix [[-1, -1, 0, 0, 0], [0, -1, 0, 0, -1], [-1, 0, 0, -1, -1], [0, 0, 0, 0, 0], [-1, 0, -1, 0, -1]] . Input matrix in check_Islands function [[1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1]] Time taken 0.13 Islands counted 1 Original matrix after operations [[-1, -1, -1, -1, -1], [-1, -1, -1, -1, -1], [-1, -1, -1, -1, -1], [-1, -1, -1, -1, -1], [-1, -1, -1, -1, -1]] . Input matrix in check_Islands_improved function [[1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1]] Time taken 0.128 Islands counted 1 Original matrix [[1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1]] Working matrix [[-1, -1, -1, -1, -1], [-1, -1, -1, -1, -1], [-1, -1, -1, -1, -1], [-1, -1, -1, -1, -1], [-1, -1, -1, -1, -1]] .
Out[51]:
1
In [52]:
evaluate_test_cases(check_Islands, tests)
TEST CASE #0 Input matrix in check_Islands function [[1, 1, 0, 0, 0], [0, 1, 0, 0, 1], [1, 0, 0, 1, 1], [0, 0, 0, 0, 0], [1, 0, 1, 0, 1]] Time taken 0.05 Islands counted 5 Original matrix after operations [[-1, -1, 0, 0, 0], [0, -1, 0, 0, -1], [-1, 0, 0, -1, -1], [0, 0, 0, 0, 0], [-1, 0, -1, 0, -1]] . Input: {'mat': [[-1, -1, 0, 0, 0], [0, -1, 0, 0, -1], [-1, 0, 0, -1, -1], [0, 0, 0, 0, 0], [-1, 0, -1, 0, -... Expected Output: 5 Actual Output: 5 Execution Time: 0.175 ms Test Result: PASSED TEST CASE #1 Input matrix in check_Islands function [[1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1]] Time taken 0.18 Islands counted 1 Original matrix after operations [[-1, -1, -1, -1, -1], [-1, -1, -1, -1, -1], [-1, -1, -1, -1, -1], [-1, -1, -1, -1, -1], [-1, -1, -1, -1, -1]] . Input: {'mat': [[-1, -1, -1, -1, -1], [-1, -1, -1, -1, -1], [-1, -1, -1, -1, -1], [-1, -1, -1, -1, -1], [-1... Expected Output: 1 Actual Output: 1 Execution Time: 0.37 ms Test Result: PASSED TEST CASE #2 Input matrix in check_Islands function [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]] Time taken 0.01 Islands counted 0 Original matrix after operations [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]] . Input: {'mat': [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]} Expected Output: 0 Actual Output: 0 Execution Time: 0.22 ms Test Result: PASSED TEST CASE #3 Input matrix in check_Islands function [[1, 0, 0, 0, 0], [0, 1, 0, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, 1, 0], [0, 0, 0, 0, 1]] Time taken 0.049 Islands counted 1 Original matrix after operations [[-1, 0, 0, 0, 0], [0, -1, 0, 0, 0], [0, 0, -1, 0, 0], [0, 0, 0, -1, 0], [0, 0, 0, 0, -1]] . Input: {'mat': [[-1, 0, 0, 0, 0], [0, -1, 0, 0, 0], [0, 0, -1, 0, 0], [0, 0, 0, -1, 0], [0, 0, 0, 0, -1]]} Expected Output: 1 Actual Output: 1 Execution Time: 0.226 ms Test Result: PASSED TEST CASE #4 Input matrix in check_Islands function [[1, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, 1, 0], [0, 0, 0, 0, 1]] Time taken 0.07 Islands counted 2 Original matrix after operations [[-1, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, -1, 0, 0], [0, 0, 0, -1, 0], [0, 0, 0, 0, -1]] . Input: {'mat': [[-1, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, -1, 0, 0], [0, 0, 0, -1, 0], [0, 0, 0, 0, -1]]} Expected Output: 2 Actual Output: 2 Execution Time: 7.549 ms Test Result: PASSED TEST CASE #5 Input matrix in check_Islands function [[0, 0, 0, 0, 1], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [1, 0, 0, 0, 1]] Time taken 0.02 Islands counted 3 Original matrix after operations [[0, 0, 0, 0, -1], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [-1, 0, 0, 0, -1]] . Input: {'mat': [[0, 0, 0, 0, -1], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [-1, 0, 0, 0, -1]]} Expected Output: 3 Actual Output: 3 Execution Time: 0.155 ms Test Result: PASSED TEST CASE #6 Input matrix in check_Islands function [[0, 1, 0, 0, 0], [0, 1, 0, 0, 1], [1, 0, 0, 1, 1], [0, 0, 0, 0, 0], [1, 0, 1, 0, 0]] Time taken 0.054 Islands counted 4 Original matrix after operations [[0, -1, 0, 0, 0], [0, -1, 0, 0, -1], [-1, 0, 0, -1, -1], [0, 0, 0, 0, 0], [-1, 0, -1, 0, 0]] . Input: {'mat': [[0, -1, 0, 0, 0], [0, -1, 0, 0, -1], [-1, 0, 0, -1, -1], [0, 0, 0, 0, 0], [-1, 0, -1, 0, 0]]} Expected Output: 4 Actual Output: 4 Execution Time: 1.157 ms Test Result: PASSED TEST CASE #7 Input matrix in check_Islands function [[0, 1, 0, 0, 0], [0, 1, 0, 0, 1], [1, 0, 1, 1, 1], [0, 1, 1, 0, 0], [1, 0, 1, 0, 0]] Time taken 0.108 Islands counted 1 Original matrix after operations [[0, -1, 0, 0, 0], [0, -1, 0, 0, -1], [-1, 0, -1, -1, -1], [0, -1, -1, 0, 0], [-1, 0, -1, 0, 0]] . Input: {'mat': [[0, -1, 0, 0, 0], [0, -1, 0, 0, -1], [-1, 0, -1, -1, -1], [0, -1, -1, 0, 0], [-1, 0, -1, 0,... Expected Output: 1 Actual Output: 1 Execution Time: 0.366 ms Test Result: PASSED TEST CASE #8 Input matrix in check_Islands function [[0, 0, 1, 0, 0], [0, 1, 0, 1, 0], [1, 0, 0, 0, 1], [0, 1, 0, 1, 0], [0, 0, 1, 0, 0]] Time taken 0.072 Islands counted 1 Original matrix after operations [[0, 0, -1, 0, 0], [0, -1, 0, -1, 0], [-1, 0, 0, 0, -1], [0, -1, 0, -1, 0], [0, 0, -1, 0, 0]] . Input: {'mat': [[0, 0, -1, 0, 0], [0, -1, 0, -1, 0], [-1, 0, 0, 0, -1], [0, -1, 0, -1, 0], [0, 0, -1, 0, 0]]} Expected Output: 1 Actual Output: 1 Execution Time: 0.356 ms Test Result: PASSED TEST CASE #9 Input matrix in check_Islands function [[1, 1, 1, 1, 1], [0, 0, 0, 1, 0], [0, 0, 0, 1, 0], [0, 1, 0, 1, 0], [0, 0, 1, 1, 0]] Time taken 0.079 Islands counted 1 Original matrix after operations [[-1, -1, -1, -1, -1], [0, 0, 0, -1, 0], [0, 0, 0, -1, 0], [0, -1, 0, -1, 0], [0, 0, -1, -1, 0]] . Input: {'mat': [[-1, -1, -1, -1, -1], [0, 0, 0, -1, 0], [0, 0, 0, -1, 0], [0, -1, 0, -1, 0], [0, 0, -1, -1,... Expected Output: 1 Actual Output: 1 Execution Time: 0.323 ms Test Result: PASSED TEST CASE #10 Input matrix in check_Islands function [[], []] Time taken 0.004 Islands counted 0 Original matrix after operations [[], []] . Input: {'mat': [[], []]} Expected Output: 0 Actual Output: 0 Execution Time: 0.232 ms Test Result: PASSED SUMMARY TOTAL: 11, PASSED: 11, FAILED: 0
Out[52]:
[(5, True, 0.175),
 (1, True, 0.37),
 (0, True, 0.22),
 (1, True, 0.226),
 (2, True, 7.549),
 (3, True, 0.155),
 (4, True, 1.157),
 (1, True, 0.366),
 (1, True, 0.356),
 (1, True, 0.323),
 (0, True, 0.232)]

9. Analyze the algorithm's complexity and identify inefficiencies, if any.

DFS is an efficient algorithm to solve this problem. Although the improved functions [count_islands_dfs_improved(matrix, x, y)] and[count_islands_dfs_improved(matrix, x, y)] had logic and input data integrity improvements, the Time and Space complexity did not improve as can be seen from the timestamp. This is because the algorithm is still a DFS algorithm.

Every cell in the array has to be be visited once, and therefore the Time Complexity of matrix [m,n] is O(mn).

A matrix of size [m,n] has to be manipulated to track if each cell is part of an island. Space complexity of matrix [m,n] is O(mn).

Alternative mechanisms such as BFS can be considered, but is of similar Time & Space complexity to DFS.

The function [count_islands_dfs(matrix, x, y)] has 8 'if' statements. This function was improved and made more readable with less logic by reducing the number of 'if' statements.

In the function [count_islands_dfs(matrix, x, y)] we destroy the input data by operating on the original data. It is best practise to make a copy and not operate on the original data. This allows the input data to be re-used and checked afterwards. This function was improved by making a copy of the original data.

If you found the problem on an external platform, you can make a submission to test your solution.

Share your approach and start a discussion on the Jovian forum: https://jovian.ai/forum/c/data-structures-and-algorithms-in-python/78

In [ ]:
jovian.commit()