Solutions

1. Depth First Search

O(rows * cols) time | O(rows * cols) space

Intuition

We can iterate through all cells with two nested loops.

If the cell is land, it is a part of an island, so we check this island size, keeping the largest one.

To check the size of the island we use DFS: recursively follow each land neighbour as far as it goes, counting every cell we pass.

We should also keep a set of visited cells to not traverse infinitely.

Algorithm

Create a largest integer and a visited hash set.
Iterate through the outer loop from the first row to the last row with row index.
For each outer loop iteration, iterate through the inner loop from the first column to the last column with col index.
- Count the island the cell at row row and column col belongs to with dfs, and update largest if that count is greater.
Return largest.
In the dfs function:
- If the cell is outside the grid, its value is 0, or it was visited before, return 0.
- Otherwise mark the cell as visited, and return 1 plus what dfs counts for the cells above, below, to the left and to the right.

land, size = 1

1 / 40

Code

Recursive implementation

Code

def largestIsland(grid: list[list[int]]) -> int:
    visited = set()
    largest = 0
    for row in range(len(grid)):
        for col in range(len(grid[0])):
            largest = max(largest, dfs(grid, visited, row, col))
    return largest


def dfs(grid: list[list[int]], visited: set[tuple[int, int]], row: int, col: int) -> int:
    if not (0 <= row < len(grid) and 0 <= col < len(grid[0])):
        return 0
    if grid[row][col] == 0 or (row, col) in visited:
        return 0
    visited.add((row, col))
    up = dfs(grid, visited, row - 1, col)
    down = dfs(grid, visited, row + 1, col)
    left = dfs(grid, visited, row, col - 1)
    right = dfs(grid, visited, row, col + 1)
    return 1 + up + down + left + right

/**
 * @param {number[][]} grid
 * @returns {number}
 */
var largestIsland = function (grid) {
  const visited = new Set()
  let largest = 0
  for (let row = 0; row < grid.length; row++) {
    for (let col = 0; col < grid[0].length; col++) largest = Math.max(largest, dfs(grid, visited, row, col))
  }
  return largest
}

/**
 * @param {number[][]} grid
 * @param {Set<string>} visited
 * @param {number} row
 * @param {number} col
 * @returns {number}
 */
var dfs = function (grid, visited, row, col) {
  const inside = row >= 0 && row < grid.length && col >= 0 && col < grid[0].length
  if (!inside) return 0
  if (grid[row][col] === 0 || visited.has(row + ',' + col)) return 0
  visited.add(row + ',' + col)
  const up = dfs(grid, visited, row - 1, col)
  const down = dfs(grid, visited, row + 1, col)
  const left = dfs(grid, visited, row, col - 1)
  const right = dfs(grid, visited, row, col + 1)
  return 1 + up + down + left + right
}

class Solution {
    public int largestIsland(int[][] grid) {
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        int largest = 0;
        for (int row = 0; row < grid.length; row++) {
            for (int col = 0; col < grid[0].length; col++) {
                largest = Math.max(largest, dfs(grid, visited, row, col));
            }
        }
        return largest;
    }

    private int dfs(int[][] grid, boolean[][] visited, int row, int col) {
        boolean inside = row >= 0 && row < grid.length && col >= 0 && col < grid[0].length;
        if (!inside) return 0;
        if (grid[row][col] == 0 || visited[row][col]) return 0;
        visited[row][col] = true;
        int up = dfs(grid, visited, row - 1, col);
        int down = dfs(grid, visited, row + 1, col);
        int left = dfs(grid, visited, row, col - 1);
        int right = dfs(grid, visited, row, col + 1);
        return 1 + up + down + left + right;
    }
}

Iterative implementation

Code

def largestIsland(grid: list[list[int]]) -> int:
    visited = set()
    largest = 0
    for row in range(len(grid)):
        for col in range(len(grid[0])):
            largest = max(largest, dfs(grid, visited, row, col))
    return largest


def dfs(grid: list[list[int]], visited: set[tuple[int, int]], row: int, col: int) -> int:
    if grid[row][col] == 0 or (row, col) in visited:
        return 0
    visited.add((row, col))
    stack = [(row, col)]
    size = 0
    while stack:
        at_row, at_col = stack.pop()
        size += 1
        up = (at_row - 1, at_col)
        down = (at_row + 1, at_col)
        left = (at_row, at_col - 1)
        right = (at_row, at_col + 1)
        for next_row, next_col in (up, down, left, right):
            if not (0 <= next_row < len(grid) and 0 <= next_col < len(grid[0])):
                continue
            if grid[next_row][next_col] == 1 and (next_row, next_col) not in visited:
                visited.add((next_row, next_col))
                stack.append((next_row, next_col))
    return size

/**
 * @param {number[][]} grid
 * @returns {number}
 */
var largestIsland = function (grid) {
  const visited = new Set()
  let largest = 0
  for (let row = 0; row < grid.length; row++) {
    for (let col = 0; col < grid[0].length; col++) largest = Math.max(largest, dfs(grid, visited, row, col))
  }
  return largest
}

/**
 * @param {number[][]} grid
 * @param {Set<string>} visited
 * @param {number} row
 * @param {number} col
 * @returns {number}
 */
var dfs = function (grid, visited, row, col) {
  if (grid[row][col] === 0 || visited.has(row + ',' + col)) return 0
  visited.add(row + ',' + col)
  const stack = [[row, col]]
  let size = 0
  while (stack.length) {
    const [atRow, atCol] = stack.pop()
    size++
    const up = [atRow - 1, atCol]
    const down = [atRow + 1, atCol]
    const left = [atRow, atCol - 1]
    const right = [atRow, atCol + 1]
    for (const [nextRow, nextCol] of [up, down, left, right]) {
      const inside = nextRow >= 0 && nextRow < grid.length && nextCol >= 0 && nextCol < grid[0].length
      if (!inside) continue
      if (grid[nextRow][nextCol] === 1 && !visited.has(nextRow + ',' + nextCol)) {
        visited.add(nextRow + ',' + nextCol)
        stack.push([nextRow, nextCol])
      }
    }
  }
  return size
}

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int largestIsland(int[][] grid) {
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        int largest = 0;
        for (int row = 0; row < grid.length; row++) {
            for (int col = 0; col < grid[0].length; col++) {
                largest = Math.max(largest, dfs(grid, visited, row, col));
            }
        }
        return largest;
    }

    private int dfs(int[][] grid, boolean[][] visited, int row, int col) {
        if (grid[row][col] == 0 || visited[row][col]) return 0;
        visited[row][col] = true;
        Deque<int[]> stack = new ArrayDeque<>();
        stack.push(new int[] { row, col });
        int size = 0;
        while (!stack.isEmpty()) {
            int[] cell = stack.pop();
            size++;
            int[] up = { cell[0] - 1, cell[1] };
            int[] down = { cell[0] + 1, cell[1] };
            int[] left = { cell[0], cell[1] - 1 };
            int[] right = { cell[0], cell[1] + 1 };
            for (int[] next : new int[][] { up, down, left, right }) {
                boolean inside = next[0] >= 0 && next[0] < grid.length && next[1] >= 0 && next[1] < grid[0].length;
                if (!inside) continue;
                if (grid[next[0]][next[1]] == 1 && !visited[next[0]][next[1]]) {
                    visited[next[0]][next[1]] = true;
                    stack.push(next);
                }
            }
        }
        return size;
    }
}

2. Breadth First Search

O(rows * cols) time | O(rows * cols) space

Intuition

We can iterate through all cells with two nested loops.

If the cell is land, it is a part of an island, so we check this island size, keeping the largest one.

To check the size of the island we use BFS: put the cell in a queue, and every cell we take out of it puts its own land neighbours in, counting every cell we pass until the queue is empty.

We should also keep a set of visited cells to not traverse infinitely.

Algorithm

Create a largest integer and a visited hash set.
Iterate through the outer loop from the first row to the last row with row index.
For each outer loop iteration, iterate through the inner loop from the first column to the last column with col index.
- Count the island the cell at row row and column col belongs to with bfs, and update largest if that count is greater.
Return largest.
In the bfs function:
- If the cell's value is 0 or it was visited before, return 0.
- Otherwise mark the cell as visited and put it in the queue.
- While the queue has cells to take, take the one at the front, and put every cell above, below, to the left and to the right of it that is inside the grid, has value 1 and was not visited before in the queue, marking each as visited.
- Return how many cells went through the queue.

land, size = 1

1 / 40

Code

def largestIsland(grid: list[list[int]]) -> int:
    visited = set()
    largest = 0
    for row in range(len(grid)):
        for col in range(len(grid[0])):
            largest = max(largest, bfs(grid, visited, row, col))
    return largest


def bfs(grid: list[list[int]], visited: set[tuple[int, int]], row: int, col: int) -> int:
    if grid[row][col] == 0 or (row, col) in visited:
        return 0
    visited.add((row, col))
    queue = [(row, col)]
    front = 0
    while front < len(queue):
        at_row, at_col = queue[front]
        front += 1
        up = (at_row - 1, at_col)
        down = (at_row + 1, at_col)
        left = (at_row, at_col - 1)
        right = (at_row, at_col + 1)
        for next_row, next_col in (up, down, left, right):
            if not (0 <= next_row < len(grid) and 0 <= next_col < len(grid[0])):
                continue
            if grid[next_row][next_col] == 1 and (next_row, next_col) not in visited:
                visited.add((next_row, next_col))
                queue.append((next_row, next_col))
    return len(queue)

/**
 * @param {number[][]} grid
 * @returns {number}
 */
var largestIsland = function (grid) {
  const visited = new Set()
  let largest = 0
  for (let row = 0; row < grid.length; row++) {
    for (let col = 0; col < grid[0].length; col++) largest = Math.max(largest, bfs(grid, visited, row, col))
  }
  return largest
}

/**
 * @param {number[][]} grid
 * @param {Set<string>} visited
 * @param {number} row
 * @param {number} col
 * @returns {number}
 */
var bfs = function (grid, visited, row, col) {
  if (grid[row][col] === 0 || visited.has(row + ',' + col)) return 0
  visited.add(row + ',' + col)
  const queue = [[row, col]]
  let front = 0
  while (front < queue.length) {
    const [atRow, atCol] = queue[front++]
    const up = [atRow - 1, atCol]
    const down = [atRow + 1, atCol]
    const left = [atRow, atCol - 1]
    const right = [atRow, atCol + 1]
    for (const [nextRow, nextCol] of [up, down, left, right]) {
      const inside = nextRow >= 0 && nextRow < grid.length && nextCol >= 0 && nextCol < grid[0].length
      if (!inside) continue
      if (grid[nextRow][nextCol] === 1 && !visited.has(nextRow + ',' + nextCol)) {
        visited.add(nextRow + ',' + nextCol)
        queue.push([nextRow, nextCol])
      }
    }
  }
  return queue.length
}

import java.util.ArrayDeque;
import java.util.Queue;

class Solution {
    public int largestIsland(int[][] grid) {
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        int largest = 0;
        for (int row = 0; row < grid.length; row++) {
            for (int col = 0; col < grid[0].length; col++) {
                largest = Math.max(largest, bfs(grid, visited, row, col));
            }
        }
        return largest;
    }

    private int bfs(int[][] grid, boolean[][] visited, int row, int col) {
        if (grid[row][col] == 0 || visited[row][col]) return 0;
        visited[row][col] = true;
        Queue<int[]> queue = new ArrayDeque<>();
        queue.add(new int[] { row, col });
        int size = 0;
        while (!queue.isEmpty()) {
            int[] cell = queue.remove();
            size++;
            int[] up = { cell[0] - 1, cell[1] };
            int[] down = { cell[0] + 1, cell[1] };
            int[] left = { cell[0], cell[1] - 1 };
            int[] right = { cell[0], cell[1] + 1 };
            for (int[] next : new int[][] { up, down, left, right }) {
                boolean inside = next[0] >= 0 && next[0] < grid.length && next[1] >= 0 && next[1] < grid[0].length;
                if (!inside) continue;
                if (grid[next[0]][next[1]] == 1 && !visited[next[0]][next[1]]) {
                    visited[next[0]][next[1]] = true;
                    queue.add(next);
                }
            }
        }
        return size;
    }
}