Number Of Islands

Mark as Completed

Lesson

Given a 2D grid map of ones and zeros, with ones representing land and zeros representing water, write a function to 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 surrounded by water.

Write a function called findIslands
that takes in a grid input and returns the number of islands.

Example:

const map1 = [
  [1, 1, 1, 1, 0],
  [1, 1, 0, 1, 0],
  [1, 1, 0, 0, 0],
  [0, 0, 0, 0, 0]
];
console.log(findIslands(map1)); // output: 1

const map2 = [
  [1, 1, 0, 0, 0],
  [1, 1, 0, 0, 0],
  [0, 0, 1, 0, 0],
  [0, 0, 0, 1, 1]
];
console.log(findIslands(map2)); // output: 3

Solution Walkthrough

Solution Code:

function findIslands(grid) {
  const visited = [];
  for (let i = 0; i < grid.length; i++) {
    visited[i] = [];
    for (let j = 0; j < grid[i].length; j++) {
      visited[i][j] = false;
    }
  }
  let count = 0;

  function markIsland(row, col, visited) {
    if (row < 0 || col < 0 || row >= grid.length || col >= grid[0].length) {
      return;
    }
    if (visited[row][col]) {
      return;
    }
    visited[row][col] = true;
    if (grid[row][col] === 0) {
      return;
    }
    markIsland(row - 1, col, visited);
    markIsland(row + 1, col, visited);
    markIsland(row, col - 1, visited);
    markIsland(row, col + 1, visited);
  }

  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[i].length; j++) {
      if (!visited[i][j] && grid[i][j] === 1) {
        markIsland(i, j, visited);
        count++;
      }
      visited[i][j] = true;
    }
  }

  return count;
}

The solution starts with creating a 2D array visited
with the same dimensions as the input grid
. We set each element in visited
to false initially, indicating that we haven't visited that element yet.Next, we define a helper function markIsland
that recursively marks an island and its adjacent lands as visited. The function takes the grid
, the current row
, the current col
, and the visited
array as parameters. The function checks if the current row
and col
are out of bounds, if the current element is already visited or if it is water (0). If any of these conditions are met, the function returns and does not mark the current element as an island.If the current element is a land (1) and not visited, we mark it as visited and recursively call markIsland
on its adjacent neighbors (up, down, left, and right).Finally, we loop through each element in the grid
. If the element has not been visited and is land, we mark the island using markIsland
and increment the count
of the number of islands. We set the current element in visited
to true, indicating that we have visited it.

Finally, we return the count of islands.

Big O Complexity Analysis:

The time complexity of this solution is O(N^2) where N is the total number of elements in the grid
. We have nested loops that loop through each element in the grid
, making it an O(N^2) solution.The space complexity of this solution is also O(N^2), where we create a 2D visited
array with the same dimensions as the input grid
. We also have a recursive function that can go as deep as the total number of elements in the grid
, adding to the space complexity.Note that in the worst case, if all elements in the grid
are land (1), the time and space complexity would be at its maximum.

Previous Lesson Next Lesson