200. Islands num

200_solution1_recursion.c

static const int dirs[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

static void sink(char **grid, int r, int c, int rows, int cols) {
  if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] != '1')
    return;
  grid[r][c] = '0';
  for (int d = 0; d < 4; d++)
    sink(grid, r + dirs[d][0], c + dirs[d][1], rows, cols);
}

int numIslands(char **grid, int gridSize, int *gridColSize) {
  if (gridSize == 0)
    return 0;
  int rows = gridSize, cols = gridColSize[0];
  int count = 0;
  for (int i = 0; i < rows; i++)
    for (int j = 0; j < cols; j++)
      if (grid[i][j] == '1') {
        sink(grid, i, j, rows, cols);
        count++;
      }
  return count;
}

200_solution2_stack.c

#include <stdlib.h>

static const int dirs[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

static void sink(char **grid, int r, int c, int rows, int cols) {
  // each cell is pushed at most once, so rows * cols slots suffice
  int (*st)[2] = malloc(rows * cols * sizeof *st);
  int top = 0;
  st[top][0] = r, st[top][1] = c, top++;
  grid[r][c] = '0';
  while (top > 0) {
    top--;
    int cr = st[top][0], cc = st[top][1];
    for (int d = 0; d < 4; d++) {
      int nr = cr + dirs[d][0], nc = cc + dirs[d][1];
      if (nr >= 0 && nc >= 0 && nr < rows && nc < cols &&
          grid[nr][nc] == '1') {
        grid[nr][nc] = '0';
        st[top][0] = nr, st[top][1] = nc, top++;
      }
    }
  }
  free(st);
}

int numIslands(char **grid, int gridSize, int *gridColSize) {
  if (gridSize == 0)
    return 0;
  int rows = gridSize, cols = gridColSize[0];
  int count = 0;
  for (int i = 0; i < rows; i++)
    for (int j = 0; j < cols; j++)
      if (grid[i][j] == '1') {
        sink(grid, i, j, rows, cols);
        count++;
      }
  return count;
}

200_solution3_queue.c

#include <stdlib.h>

static const int dirs[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

static void sink(char **grid, int r, int c, int rows, int cols) {
  // each cell is enqueued at most once, so rows * cols slots suffice
  int (*q)[2] = malloc(rows * cols * sizeof *q);
  int head = 0, tail = 0;
  q[tail][0] = r, q[tail][1] = c, tail++;
  grid[r][c] = '0';
  while (head < tail) {
    int cr = q[head][0], cc = q[head][1];
    head++;
    for (int d = 0; d < 4; d++) {
      int nr = cr + dirs[d][0], nc = cc + dirs[d][1];
      if (nr >= 0 && nc >= 0 && nr < rows && nc < cols &&
          grid[nr][nc] == '1') {
        grid[nr][nc] = '0';
        q[tail][0] = nr, q[tail][1] = nc, tail++;
      }
    }
  }
  free(q);
}

int numIslands(char **grid, int gridSize, int *gridColSize) {
  if (gridSize == 0)
    return 0;
  int rows = gridSize, cols = gridColSize[0];
  int count = 0;
  for (int i = 0; i < rows; i++)
    for (int j = 0; j < cols; j++)
      if (grid[i][j] == '1') {
        sink(grid, i, j, rows, cols);
        count++;
      }
  return count;
}

200_solution1_recursion.cpp

#include <vector>

using namespace std;

class Solution {
public:
  int numIslands(vector<vector<char>> &grid) {
    if (grid.empty())
      return 0;
    int rows = grid.size(), cols = grid[0].size();
    int count = 0;
    for (int i = 0; i < rows; i++)
      for (int j = 0; j < cols; j++)
        if (grid[i][j] == '1') {
          sink(grid, i, j, rows, cols);
          count++;
        }
    return count;
  }

private:
  static constexpr int dirs[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

  void sink(vector<vector<char>> &grid, int r, int c, int rows, int cols) {
    if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] != '1')
      return;
    grid[r][c] = '0';
    for (auto [dr, dc] : dirs)
      sink(grid, r + dr, c + dc, rows, cols);
  }
};

200_solution2_stack.cpp

#include <stack>
#include <utility>
#include <vector>

using namespace std;

class Solution {
public:
  int numIslands(vector<vector<char>> &grid) {
    if (grid.empty())
      return 0;
    int rows = grid.size(), cols = grid[0].size();
    int count = 0;
    for (int i = 0; i < rows; i++)
      for (int j = 0; j < cols; j++)
        if (grid[i][j] == '1') {
          sink(grid, i, j, rows, cols);
          count++;
        }
    return count;
  }

private:
  static constexpr int dirs[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

  void sink(vector<vector<char>> &grid, int r, int c, int rows, int cols) {
    stack<pair<int, int>> st;
    st.push({r, c});
    grid[r][c] = '0';
    while (!st.empty()) {
      auto [cr, cc] = st.top();
      st.pop();
      for (auto [dr, dc] : dirs) {
        int nr = cr + dr, nc = cc + dc;
        if (nr >= 0 && nc >= 0 && nr < rows && nc < cols &&
            grid[nr][nc] == '1') {
          grid[nr][nc] = '0';
          st.push({nr, nc});
        }
      }
    }
  }
};

200_solution3_queue.cpp

#include <queue>
#include <utility>
#include <vector>

using namespace std;

class Solution {
public:
  int numIslands(vector<vector<char>> &grid) {
    if (grid.empty())
      return 0;
    int rows = grid.size(), cols = grid[0].size();
    int count = 0;
    for (int i = 0; i < rows; i++)
      for (int j = 0; j < cols; j++)
        if (grid[i][j] == '1') {
          sink(grid, i, j, rows, cols);
          count++;
        }
    return count;
  }

private:
  static constexpr int dirs[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

  void sink(vector<vector<char>> &grid, int r, int c, int rows, int cols) {
    queue<pair<int, int>> q;
    q.push({r, c});
    grid[r][c] = '0';
    while (!q.empty()) {
      auto [cr, cc] = q.front();
      q.pop();
      for (auto [dr, dc] : dirs) {
        int nr = cr + dr, nc = cc + dc;
        if (nr >= 0 && nc >= 0 && nr < rows && nc < cols &&
            grid[nr][nc] == '1') {
          grid[nr][nc] = '0';
          q.push({nr, nc});
        }
      }
    }
  }
};

200_solution1_recursion.go

package graphs

var dirs = [4][2]int{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}

func numIslands(grid [][]byte) int {
    if len(grid) == 0 {
        return 0
    }
    rows, cols := len(grid), len(grid[0])
    count := 0
    for i := 0; i < rows; i++ {
        for j := 0; j < cols; j++ {
            if grid[i][j] == '1' {
                sink(grid, i, j, rows, cols)
                count++
            }
        }
    }
    return count
}

func sink(grid [][]byte, r, c, rows, cols int) {
    if r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] != '1' {
        return
    }
    grid[r][c] = '0'
    for _, d := range dirs {
        sink(grid, r+d[0], c+d[1], rows, cols)
    }
}

200_solution2_stack.go

package graphs

var dirs = [4][2]int{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}

func numIslands(grid [][]byte) int {
    if len(grid) == 0 {
        return 0
    }
    rows, cols := len(grid), len(grid[0])
    count := 0
    for i := 0; i < rows; i++ {
        for j := 0; j < cols; j++ {
            if grid[i][j] == '1' {
                sink(grid, i, j, rows, cols)
                count++
            }
        }
    }
    return count
}

func sink(grid [][]byte, r, c, rows, cols int) {
    st := [][2]int{{r, c}}
    grid[r][c] = '0'
    for len(st) > 0 {
        cur := st[len(st)-1]
        st = st[:len(st)-1]
        for _, d := range dirs {
            nr, nc := cur[0]+d[0], cur[1]+d[1]
            if nr >= 0 && nc >= 0 && nr < rows && nc < cols && grid[nr][nc] == '1' {
                grid[nr][nc] = '0'
                st = append(st, [2]int{nr, nc})
            }
        }
    }
}

200_solution3_queue.go

package graphs

var dirs = [4][2]int{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}

func numIslands(grid [][]byte) int {
    if len(grid) == 0 {
        return 0
    }
    rows, cols := len(grid), len(grid[0])
    count := 0
    for i := 0; i < rows; i++ {
        for j := 0; j < cols; j++ {
            if grid[i][j] == '1' {
                sink(grid, i, j, rows, cols)
                count++
            }
        }
    }
    return count
}

func sink(grid [][]byte, r, c, rows, cols int) {
    q := [][2]int{{r, c}}
    grid[r][c] = '0'
    for len(q) > 0 {
        cur := q[0]
        q = q[1:]
        for _, d := range dirs {
            nr, nc := cur[0]+d[0], cur[1]+d[1]
            if nr >= 0 && nc >= 0 && nr < rows && nc < cols && grid[nr][nc] == '1' {
                grid[nr][nc] = '0'
                q = append(q, [2]int{nr, nc})
            }
        }
    }
}

200_solution1_recursion.java

class Solution {
    public int numIslands(char[][] grid) {
        if (grid.length == 0)
            return 0;
        int rows = grid.length, cols = grid[0].length;
        int count = 0;
        for (int i = 0; i < rows; i++)
            for (int j = 0; j < cols; j++)
                if (grid[i][j] == '1') {
                    sink(grid, i, j, rows, cols);
                    count++;
                }
        return count;
    }

    private static final int[][] DIRS = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

    private void sink(char[][] grid, int r, int c, int rows, int cols) {
        if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] != '1')
            return;
        grid[r][c] = '0';
        for (int[] d : DIRS)
            sink(grid, r + d[0], c + d[1], rows, cols);
    }
}

200_solution2_stack.java

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

class Solution {
    public int numIslands(char[][] grid) {
        if (grid.length == 0)
            return 0;
        int rows = grid.length, cols = grid[0].length;
        int count = 0;
        for (int i = 0; i < rows; i++)
            for (int j = 0; j < cols; j++)
                if (grid[i][j] == '1') {
                    sink(grid, i, j, rows, cols);
                    count++;
                }
        return count;
    }

    private static final int[][] DIRS = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

    private void sink(char[][] grid, int r, int c, int rows, int cols) {
        Deque<int[]> st = new ArrayDeque<>();
        st.push(new int[] {r, c});
        grid[r][c] = '0';
        while (!st.isEmpty()) {
            int[] cur = st.pop();
            for (int[] d : DIRS) {
                int nr = cur[0] + d[0], nc = cur[1] + d[1];
                if (nr >= 0 && nc >= 0 && nr < rows && nc < cols && grid[nr][nc] == '1') {
                    grid[nr][nc] = '0';
                    st.push(new int[] {nr, nc});
                }
            }
        }
    }
}

200_solution3_queue.java

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

class Solution {
    public int numIslands(char[][] grid) {
        if (grid.length == 0)
            return 0;
        int rows = grid.length, cols = grid[0].length;
        int count = 0;
        for (int i = 0; i < rows; i++)
            for (int j = 0; j < cols; j++)
                if (grid[i][j] == '1') {
                    sink(grid, i, j, rows, cols);
                    count++;
                }
        return count;
    }

    private static final int[][] DIRS = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

    private void sink(char[][] grid, int r, int c, int rows, int cols) {
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[] {r, c});
        grid[r][c] = '0';
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            for (int[] d : DIRS) {
                int nr = cur[0] + d[0], nc = cur[1] + d[1];
                if (nr >= 0 && nc >= 0 && nr < rows && nc < cols && grid[nr][nc] == '1') {
                    grid[nr][nc] = '0';
                    q.offer(new int[] {nr, nc});
                }
            }
        }
    }
}

200_solution1_recursion.js

const DIRS = [
  [1, 0],
  [0, 1],
  [-1, 0],
  [0, -1],
];

const sink = (grid, r, c, rows, cols) => {
  if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] !== "1") return;
  grid[r][c] = "0";
  for (const [dr, dc] of DIRS) sink(grid, r + dr, c + dc, rows, cols);
};

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function (grid) {
  if (grid.length === 0) return 0;
  const rows = grid.length,
    cols = grid[0].length;
  let count = 0;
  for (let i = 0; i < rows; i++)
    for (let j = 0; j < cols; j++)
      if (grid[i][j] === "1") {
        sink(grid, i, j, rows, cols);
        count++;
      }
  return count;
};

200_solution2_stack.js

const DIRS = [
  [1, 0],
  [0, 1],
  [-1, 0],
  [0, -1],
];

const sink = (grid, r, c, rows, cols) => {
  const st = [[r, c]];
  grid[r][c] = "0";
  while (st.length > 0) {
    const [cr, cc] = st.pop();
    for (const [dr, dc] of DIRS) {
      const nr = cr + dr,
        nc = cc + dc;
      if (nr >= 0 && nc >= 0 && nr < rows && nc < cols && grid[nr][nc] === "1") {
        grid[nr][nc] = "0";
        st.push([nr, nc]);
      }
    }
  }
};

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function (grid) {
  if (grid.length === 0) return 0;
  const rows = grid.length,
    cols = grid[0].length;
  let count = 0;
  for (let i = 0; i < rows; i++)
    for (let j = 0; j < cols; j++)
      if (grid[i][j] === "1") {
        sink(grid, i, j, rows, cols);
        count++;
      }
  return count;
};

200_solution3_queue.js

const DIRS = [
  [1, 0],
  [0, 1],
  [-1, 0],
  [0, -1],
];

const sink = (grid, r, c, rows, cols) => {
  // index-based queue: Array.shift() is O(n)
  const q = [[r, c]];
  grid[r][c] = "0";
  for (let head = 0; head < q.length; head++) {
    const [cr, cc] = q[head];
    for (const [dr, dc] of DIRS) {
      const nr = cr + dr,
        nc = cc + dc;
      if (nr >= 0 && nc >= 0 && nr < rows && nc < cols && grid[nr][nc] === "1") {
        grid[nr][nc] = "0";
        q.push([nr, nc]);
      }
    }
  }
};

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function (grid) {
  if (grid.length === 0) return 0;
  const rows = grid.length,
    cols = grid[0].length;
  let count = 0;
  for (let i = 0; i < rows; i++)
    for (let j = 0; j < cols; j++)
      if (grid[i][j] === "1") {
        sink(grid, i, j, rows, cols);
        count++;
      }
  return count;
};

200_solution1_recursion.py

from typing import List

DIRS = ((1, 0), (0, 1), (-1, 0), (0, -1))


class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0
        rows, cols = len(grid), len(grid[0])
        count = 0
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == "1":
                    self.sink(grid, i, j, rows, cols)
                    count += 1
        return count

    def sink(self, grid: List[List[str]], r: int, c: int, rows: int, cols: int) -> None:
        if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] != "1":
            return
        grid[r][c] = "0"
        for dr, dc in DIRS:
            self.sink(grid, r + dr, c + dc, rows, cols)

200_solution2_stack.py

from typing import List

DIRS = ((1, 0), (0, 1), (-1, 0), (0, -1))


class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0
        rows, cols = len(grid), len(grid[0])
        count = 0
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == "1":
                    self.sink(grid, i, j, rows, cols)
                    count += 1
        return count

    def sink(self, grid: List[List[str]], r: int, c: int, rows: int, cols: int) -> None:
        st = [(r, c)]
        grid[r][c] = "0"
        while st:
            cr, cc = st.pop()
            for dr, dc in DIRS:
                nr, nc = cr + dr, cc + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == "1":
                    grid[nr][nc] = "0"
                    st.append((nr, nc))

200_solution3_queue.py

from collections import deque
from typing import List

DIRS = ((1, 0), (0, 1), (-1, 0), (0, -1))


class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0
        rows, cols = len(grid), len(grid[0])
        count = 0
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == "1":
                    self.sink(grid, i, j, rows, cols)
                    count += 1
        return count

    def sink(self, grid: List[List[str]], r: int, c: int, rows: int, cols: int) -> None:
        q = deque([(r, c)])
        grid[r][c] = "0"
        while q:
            cr, cc = q.popleft()
            for dr, dc in DIRS:
                nr, nc = cr + dr, cc + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == "1":
                    grid[nr][nc] = "0"
                    q.append((nr, nc))

200_solution1_recursion.rs

const DIRS: [(isize, isize); 4] = [(1, 0), (0, 1), (-1, 0), (0, -1)];

impl Solution {
    pub fn num_islands(mut grid: Vec<Vec<char>>) -> i32 {
        if grid.is_empty() {
            return 0;
        }
        let (rows, cols) = (grid.len(), grid[0].len());
        let mut count = 0;
        for i in 0..rows {
            for j in 0..cols {
                if grid[i][j] == '1' {
                    Self::sink(&mut grid, i, j, rows, cols);
                    count += 1;
                }
            }
        }
        count
    }

    fn sink(grid: &mut Vec<Vec<char>>, r: usize, c: usize, rows: usize, cols: usize) {
        if grid[r][c] != '1' {
            return;
        }
        grid[r][c] = '0';
        for (dr, dc) in DIRS {
            // wrapping_add_signed turns -1 at 0 into usize::MAX, caught by the bounds check
            let (nr, nc) = (r.wrapping_add_signed(dr), c.wrapping_add_signed(dc));
            if nr < rows && nc < cols {
                Self::sink(grid, nr, nc, rows, cols);
            }
        }
    }
}

200_solution2_stack.rs

const DIRS: [(isize, isize); 4] = [(1, 0), (0, 1), (-1, 0), (0, -1)];

impl Solution {
    pub fn num_islands(mut grid: Vec<Vec<char>>) -> i32 {
        if grid.is_empty() {
            return 0;
        }
        let (rows, cols) = (grid.len(), grid[0].len());
        let mut count = 0;
        for i in 0..rows {
            for j in 0..cols {
                if grid[i][j] == '1' {
                    Self::sink(&mut grid, i, j, rows, cols);
                    count += 1;
                }
            }
        }
        count
    }

    fn sink(grid: &mut Vec<Vec<char>>, r: usize, c: usize, rows: usize, cols: usize) {
        let mut st = vec![(r, c)];
        grid[r][c] = '0';
        while let Some((cr, cc)) = st.pop() {
            for (dr, dc) in DIRS {
                // wrapping_add_signed turns -1 at 0 into usize::MAX, caught by the bounds check
                let (nr, nc) = (cr.wrapping_add_signed(dr), cc.wrapping_add_signed(dc));
                if nr < rows && nc < cols && grid[nr][nc] == '1' {
                    grid[nr][nc] = '0';
                    st.push((nr, nc));
                }
            }
        }
    }
}

200_solution3_queue.rs

use std::collections::VecDeque;

const DIRS: [(isize, isize); 4] = [(1, 0), (0, 1), (-1, 0), (0, -1)];

impl Solution {
    pub fn num_islands(mut grid: Vec<Vec<char>>) -> i32 {
        if grid.is_empty() {
            return 0;
        }
        let (rows, cols) = (grid.len(), grid[0].len());
        let mut count = 0;
        for i in 0..rows {
            for j in 0..cols {
                if grid[i][j] == '1' {
                    Self::sink(&mut grid, i, j, rows, cols);
                    count += 1;
                }
            }
        }
        count
    }

    fn sink(grid: &mut Vec<Vec<char>>, r: usize, c: usize, rows: usize, cols: usize) {
        let mut q = VecDeque::from([(r, c)]);
        grid[r][c] = '0';
        while let Some((cr, cc)) = q.pop_front() {
            for (dr, dc) in DIRS {
                // wrapping_add_signed turns -1 at 0 into usize::MAX, caught by the bounds check
                let (nr, nc) = (cr.wrapping_add_signed(dr), cc.wrapping_add_signed(dc));
                if nr < rows && nc < cols && grid[nr][nc] == '1' {
                    grid[nr][nc] = '0';
                    q.push_back((nr, nc));
                }
            }
        }
    }
}