Problems

Master the matrix pattern by solving these carefully selected problems. Each problem demonstrates a different variation of 2D array manipulation and builds your problem-solving skills progressively.

For a theoretical overview, check out the Matrix Algorithms Guide or the Code Templates.

Easy Problems

1. Reshape the Matrix

LeetCode 566 |

Easy

Brief: Transform an m x n matrix into an r x c matrix while maintaining row-major order.
Why this pattern?: Teaches how to flatten 2D coordinates into 1D and re-map them to different 2D coordinates.
Key Insight: Element at matrix[i][j] (where k = i*n + j) maps to result[k/c][k%c].

Visual:

  graph TD
    Input["Input: 2x2"] --> |Flatten| Flat["1, 2, 3, 4"]
    Flat --> |Reshape| Output["Output: 1x4"]
    style Input fill:#e1f5fe
    style Output fill:#e1f5fe

JavaScript:

function matrixReshape(mat, r, c) {
    const m = mat.length, n = mat[0].length;
    if (m * n !== r * c) return mat;

    const result = Array.from({length: r}, () => new Array(c));
    let row = 0, col = 0;

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            result[row][col] = mat[i][j];
            col++;
            if (col === c) {
                col = 0;
                row++;
            }
        }
    }
    return result;
}

Python:

def matrix_reshape(mat: List[List[int]], r: int, c: int) -> List[List[int]]:
    m, n = len(mat), len(mat[0])
    if m * n != r * c:
        return mat

    flat = [x for row in mat for x in row]
    return [flat[i * c : (i + 1) * c] for i in range(r)]

Java:

public int[][] matrixReshape(int[][] mat, int r, int c) {
    int m = mat.length, n = mat[0].length;
    if (m * n != r * c) return mat;

    int[][] res = new int[r][c];
    int row = 0, col = 0;

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            res[row][col] = mat[i][j];
            col++;
            if (col == c) {
                row++;
                col = 0;
            }
        }
    }
    return res;
}

C++:

vector<vector<int>> matrixReshape(vector<vector<int>>& mat, int r, int c) {
    int m = mat.size(), n = mat[0].size();
    if (m * n != r * c) return mat;

    vector<vector<int>> res(r, vector<int>(c));
    int row = 0, col = 0;

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            res[row][col] = mat[i][j];
            col++;
            if (col == c) {
                row++;
                col = 0;
            }
        }
    }
    return res;
}

Go:

func matrixReshape(mat [][]int, r int, c int) [][]int {
    m, n := len(mat), len(mat[0])
    if m*n != r*c {
        return mat
    }

    res := make([][]int, r)
    for i := range res {
        res[i] = make([]int, c)
    }

    row, col := 0, 0
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            res[row][col] = mat[i][j]
            col++
            if col == c {
                row++
                col = 0
            }
        }
    }
    return res
}

Ruby:

def matrix_reshape(mat, r, c)
  m, n = mat.length, mat[0].length
  return mat if m * n != r * c

  mat.flatten.each_slice(c).to_a
end

2. Transpose Matrix

LeetCode 867 |

Easy

Brief: Flip a matrix over its main diagonal, switching row and column indices.
Why this pattern?: Foundational operation for linear algebra and image rotation.
Key Insight: result[j][i] = matrix[i][j].

Visual:

  graph LR
    A["Row i, Col j"] --> |Swap| B["Row j, Col i"]

JavaScript:

function transpose(matrix) {
    const m = matrix.length, n = matrix[0].length;
    const res = Array.from({length: n}, () => new Array(m));

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            res[j][i] = matrix[i][j];
        }
    }
    return res;
}

Python:

def transpose(matrix: List[List[int]]) -> List[List[int]]:
    return list(map(list, zip(*matrix)))

Java:

public int[][] transpose(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    int[][] res = new int[n][m];

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            res[j][i] = matrix[i][j];
        }
    }
    return res;
}

C++:

vector<vector<int>> transpose(vector<vector<int>>& matrix) {
    int m = matrix.size(), n = matrix[0].size();
    vector<vector<int>> res(n, vector<int>(m));

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            res[j][i] = matrix[i][j];
        }
    }
    return res;
}

Go:

func transpose(matrix [][]int) [][]int {
    m, n := len(matrix), len(matrix[0])
    res := make([][]int, n)
    for i := range res {
        res[i] = make([]int, m)
    }

    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            res[j][i] = matrix[i][j]
        }
    }
    return res
}

Ruby:

def transpose(matrix)
  matrix.transpose
end

3. Toeplitz Matrix

LeetCode 766 |

Easy

Brief: Return true if every diagonal from top-left to bottom-right has the same elements.
Why this pattern?: Teaches diagonal comparison logic.
Key Insight: Compare matrix[i][j] with matrix[i-1][j-1].

Visual:

  graph TD
    A["Cells in same diagonal"] --> |Check| B{"Equal?"}
    B -- Yes --> C["Continue"]
    B -- No --> D["Return False"]

JavaScript:

function isToeplitzMatrix(matrix) {
    for (let i = 1; i < matrix.length; i++) {
        for (let j = 1; j < matrix[0].length; j++) {
            if (matrix[i][j] !== matrix[i-1][j-1]) return false;
        }
    }
    return true;
}

Python:

def is_toeplitz_matrix(matrix: List[List[int]]) -> bool:
    return all(matrix[i][j] == matrix[i-1][j-1]
               for i in range(1, len(matrix))
               for j in range(1, len(matrix[0])))

Java:

public boolean isToeplitzMatrix(int[][] matrix) {
    for (int i = 1; i < matrix.length; i++) {
        for (int j = 1; j < matrix[0].length; j++) {
            if (matrix[i][j] != matrix[i-1][j-1]) return false;
        }
    }
    return true;
}

C++:

bool isToeplitzMatrix(vector<vector<int>>& matrix) {
    for (int i = 1; i < matrix.size(); ++i) {
        for (int j = 1; j < matrix[0].size(); ++j) {
            if (matrix[i][j] != matrix[i-1][j-1]) return false;
        }
    }
    return true;
}

Go:

func isToeplitzMatrix(matrix [][]int) bool {
    for i := 1; i < len(matrix); i++ {
        for j := 1; j < len(matrix[0]); j++ {
            if matrix[i][j] != matrix[i-1][j-1] {
                return false
            }
        }
    }
    return true;
}

Ruby:

def is_toeplitz_matrix(matrix)
  (1...matrix.length).each do |i|
    (1...matrix[0].length).each do |j|
      return false if matrix[i][j] != matrix[i-1][j-1]
    end
  end
  return true
end

4. Count Negative Numbers in a Sorted Matrix

LeetCode 1351 |

Easy

Brief: Count negatives in a matrix sorted row-wise and column-wise.
Why this pattern?: Efficient traversal (Staircase search).
Key Insight: Start Top-Right. If negative, entire column below is negative.

Visual:

  graph TD
    Start["Top-Right"] --> Check{"Is Negative?"}
    Check -- Yes --> Count["Add Remaining Rows"] --> MoveLeft
    Check -- No --> MoveDown

JavaScript:

function countNegatives(grid) {
    let count = 0;
    let m = grid.length, n = grid[0].length;
    let r = 0, c = n - 1;

    while (r < m && c >= 0) {
        if (grid[r][c] < 0) {
            count += (m - r); // All below are also negative
            c--;
        } else {
            r++;
        }
    }
    return count;
}

Python:

def count_negatives(grid: List[List[int]]) -> int:
    m, n = len(grid), len(grid[0])
    r, c = 0, n - 1
    count = 0

    while r < m and c >= 0:
        if grid[r][c] < 0:
            count += (m - r)
            c -= 1
        else:
            r += 1
    return count

Java:

public int countNegatives(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int r = 0, c = n - 1;
    int count = 0;

    while (r < m && c >= 0) {
        if (grid[r][c] < 0) {
            count += (m - r);
            c--;
        } else {
            r++;
        }
    }
    return count;
}

C++:

int countNegatives(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    int r = 0, c = n - 1;
    int count = 0;

    while (r < m && c >= 0) {
        if (grid[r][c] < 0) {
            count += (m - r);
            c--;
        } else {
            r++;
        }
    }
    return count;
}

Go:

func countNegatives(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    r, c := 0, n - 1
    count := 0

    while r < m && c >= 0 { // Go has for, but pseudocode:
        for r < m && c >= 0 {
            if grid[r][c] < 0 {
                count += (m - r)
                c--
            } else {
                r++
            }
        }
        break
    }
    return count
}

Ruby:

def count_negatives(grid)
  m, n = grid.length, grid[0].length
  r, c = 0, n - 1
  count = 0

  while r < m && c >= 0
    if grid[r][c] < 0
      count += (m - r)
      c -= 1
    else
      r += 1
    end
  end
  count
end

5. Island Perimeter

LeetCode 463 |

Easy

Brief: Calc perimeter of an island (1s) in a grid of 0s.
Why this pattern?: Neighbor counting logic.
Key Insight: Perimeter = 4 * LandCells - 2 * ConnectedNeighbors (or just check 4 sides for water).

JavaScript:

function islandPerimeter(grid) {
    let p = 0;
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[0].length; j++) {
            if (grid[i][j] === 1) {
                p += 4;
                if (i > 0 && grid[i-1][j] === 1) p -= 2;
                if (j > 0 && grid[i][j-1] === 1) p -= 2;
            }
        }
    }
    return p;
}

Python:

def island_perimeter(grid: List[List[int]]) -> int:
    m, n = len(grid), len(grid[0])
    p = 0
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                p += 4
                if i > 0 and grid[i-1][j] == 1: p -= 2
                if j > 0 and grid[i][j-1] == 1: p -= 2
    return p

Java:

public int islandPerimeter(int[][] grid) {
    int p = 0;
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == 1) {
                p += 4;
                if (i > 0 && grid[i-1][j] == 1) p -= 2;
                if (j > 0 && grid[i][j-1] == 1) p -= 2;
            }
        }
    }
    return p;
}

C++:

int islandPerimeter(vector<vector<int>>& grid) {
    int p = 0;
    int m = grid.size(), n = grid[0].size();
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (grid[i][j] == 1) {
                p += 4;
                if (i > 0 && grid[i-1][j] == 1) p -= 2;
                if (j > 0 && grid[i][j-1] == 1) p -= 2;
            }
        }
    }
    return p;
}

Go:

func islandPerimeter(grid [][]int) int {
    p := 0
    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[0]); j++ {
            if grid[i][j] == 1 {
                p += 4
                if i > 0 && grid[i-1][j] == 1 { p -= 2 }
                if j > 0 && grid[i][j-1] == 1 { p -= 2 }
            }
        }
    }
    return p
}

Ruby:

def island_perimeter(grid)
  p = 0
  (0...grid.length).each do |i|
    (0...grid[0].length).each do |j|
      if grid[i][j] == 1
        p += 4
        p -= 2 if i > 0 && grid[i-1][j] == 1
        p -= 2 if j > 0 && grid[i][j-1] == 1
      end
    end
  end
  p
end

Medium Problems

6. Rotate Image

LeetCode 48 |

Medium

Brief: Rotate an nxn matrix 90 degrees clockwise in-place.
Why this pattern?: Standard interview problem for matrix manipulation.
Key Insight: Transpose then Reverse Rows.

JavaScript:

function rotate(matrix) {
    // 1. Transpose
    for (let i = 0; i < matrix.length; i++) {
        for (let j = i; j < matrix.length; j++) {
            [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
        }
    }
    // 2. Reverse rows
    matrix.forEach(row => row.reverse());
}

Python:

def rotate(matrix: List[List[int]]) -> None:
    n = len(matrix)
    for i in range(n):
        for j in range(i, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    for row in matrix:
        row.reverse()

Java:

public void rotate(int[][] matrix) {
    int n = matrix.length;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int tmp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = tmp;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n/2; j++) {
            int tmp = matrix[i][j];
            matrix[i][j] = matrix[i][n-1-j];
            matrix[i][n-1-j] = tmp;
        }
    }
}

C++:

void rotate(vector<vector<int>>& matrix) {
    int n = matrix.size();
    for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; ++j) {
            swap(matrix[i][j], matrix[j][i]);
        }
    }
    for (int i = 0; i < n; ++i) {
        reverse(matrix[i].begin(), matrix[i].end());
    }
}

Go:

func rotate(matrix [][]int) {
    n := len(matrix)
    for i := 0; i < n; i++ {
        for j := i; j < n; j++ {
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        }
    }
    for i := 0; i < n; i++ {
        for j, k := 0, n-1; j < k; j, k = j+1, k-1 {
            matrix[i][j], matrix[i][k] = matrix[i][k], matrix[i][j]
        }
    }
}

Ruby:

def rotate(matrix)
  n = matrix.length
  (0...n).each do |i|
    (i...n).each do |j|
      matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    end
  end
  matrix.each(&:reverse!)
end

7. Set Matrix Zeroes

LeetCode 73 |

Medium

Brief: If an element is 0, set its entire row and column to 0. In-place.
Why this pattern?: Space optimization (O(1) space).
Key Insight: Use the first row and first column as markers.

JavaScript:

function setZeroes(matrix) {
    const m = matrix.length, n = matrix[0].length;
    let col0 = 1;

    for (let i = 0; i < m; i++) {
        if (matrix[i][0] === 0) col0 = 0;
        for (let j = 1; j < n; j++) {
            if (matrix[i][j] === 0) {
                matrix[i][0] = matrix[0][j] = 0;
            }
        }
    }

    for (let i = m - 1; i >= 0; i--) {
        for (let j = n - 1; j >= 1; j--) {
            if (matrix[i][0] === 0 || matrix[0][j] === 0) {
                matrix[i][j] = 0;
            }
        }
        if (col0 === 0) matrix[i][0] = 0;
    }
}

Python:

def set_zeroes(matrix: List[List[int]]) -> None:
    m, n = len(matrix), len(matrix[0])
    col0 = 1

    for i in range(m):
        if matrix[i][0] == 0: col0 = 0
        for j in range(1, n):
            if matrix[i][j] == 0:
                matrix[i][0] = matrix[0][j] = 0

    for i in range(m - 1, -1, -1):
        for j in range(n - 1, 0, -1):
            if matrix[i][0] == 0 or matrix[0][j] == 0:
                matrix[i][j] = 0
        if col0 == 0: matrix[i][0] = 0

Java:

public void setZeroes(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    int col0 = 1;

    for (int i = 0; i < m; i++) {
        if (matrix[i][0] == 0) col0 = 0;
        for (int j = 1; j < n; j++) {
            if (matrix[i][j] == 0)
                matrix[i][0] = matrix[0][j] = 0;
        }
    }

    for (int i = m - 1; i >= 0; i--) {
        for (int j = n - 1; j >= 1; j--) {
            if (matrix[i][0] == 0 || matrix[0][j] == 0)
                matrix[i][j] = 0;
        }
        if (col0 == 0) matrix[i][0] = 0;
    }
}

C++:

void setZeroes(vector<vector<int>>& matrix) {
    int m = matrix.size(), n = matrix[0].size();
    int col0 = 1;

    for (int i = 0; i < m; ++i) {
        if (matrix[i][0] == 0) col0 = 0;
        for (int j = 1; j < n; ++j) {
            if (matrix[i][j] == 0)
                matrix[i][0] = matrix[0][j] = 0;
        }
    }

    for (int i = m - 1; i >= 0; --i) {
        for (int j = n - 1; j >= 1; --j) {
            if (matrix[i][0] == 0 || matrix[0][j] == 0)
                matrix[i][j] = 0;
        }
        if (col0 == 0) matrix[i][0] = 0;
    }
}

Go:

func setZeroes(matrix [][]int) {
    m, n := len(matrix), len(matrix[0])
    col0 := 1

    for i := 0; i < m; i++ {
        if matrix[i][0] == 0 { col0 = 0 }
        for j := 1; j < n; j++ {
            if matrix[i][j] == 0 {
                matrix[i][0] = 0
                matrix[0][j] = 0
            }
        }
    }

    for i := m - 1; i >= 0; i-- {
        for j := n - 1; j >= 1; j-- {
            if matrix[i][0] == 0 || matrix[0][j] == 0 {
                matrix[i][j] = 0
            }
        }
        if col0 == 0 { matrix[i][0] = 0 }
    }
}

Ruby:

def set_zeroes(matrix)
  m, n = matrix.length, matrix[0].length
  col0 = 1

  (0...m).each do |i|
    col0 = 0 if matrix[i][0] == 0
    (1...n).each do |j|
      if matrix[i][j] == 0
        matrix[i][0] = matrix[0][j] = 0
      end
    end
  end

  (m-1).downto(0) do |i|
    (n-1).downto(1) do |j|
      if matrix[i][0] == 0 || matrix[0][j] == 0
        matrix[i][j] = 0
      end
    end
    matrix[i][0] = 0 if col0 == 0
  end
end

8. Spiral Matrix

LeetCode 54 |

Medium

Brief: Return all elements of the matrix in spiral order.
Why this pattern?: Classic simulation problem with boundary management.
Key Insight: Maintain top, bottom, left, right pointers and shrink them after each pass.

Visual:

  graph TD
    Start --> Right --> Down --> Left --> Up --> Start
    Right --> |Top++| Check1{"Done?"}
    Down --> |Right--| Check2{"Done?"}
    Left --> |Bottom--| Check3{"Done?"}
    Up --> |Left++| Check4{"Done?"}

JavaScript:

function spiralOrder(matrix) {
    const res = [];
    if (!matrix.length) return res;
    let top = 0, bottom = matrix.length - 1;
    let left = 0, right = matrix[0].length - 1;

    while (top <= bottom && left <= right) {
        for (let j = left; j <= right; j++) res.push(matrix[top][j]);
        top++;
        for (let i = top; i <= bottom; i++) res.push(matrix[i][right]);
        right--;
        if (top <= bottom) {
            for (let j = right; j >= left; j--) res.push(matrix[bottom][j]);
            bottom--;
        }
        if (left <= right) {
            for (let i = bottom; i >= top; i--) res.push(matrix[i][left]);
            left++;
        }
    }
    return res;
}

Python:

def spiral_order(matrix: List[List[int]]) -> List[int]:
    res = []
    if not matrix: return res
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1

    while (top <= bottom and left <= right):
        for j in range(left, right + 1):
            res.append(matrix[top][j])
        top += 1
        for i in range(top, bottom + 1):
            res.append(matrix[i][right])
        right -= 1

        if top <= bottom:
            for j in range(right, left - 1, -1):
                res.append(matrix[bottom][j])
            bottom -= 1
        if left <= right:
            for i in range(bottom, top - 1, -1):
                res.append(matrix[i][left])
            left += 1
    return res

Java:

public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> res = new ArrayList<>();
    if (matrix.length == 0) return res;
    int top = 0, bottom = matrix.length - 1;
    int left = 0, right = matrix[0].length - 1;

    while (top <= bottom && left <= right) {
        for (int j = left; j <= right; j++) res.add(matrix[top][j]);
        top++;
        for (int i = top; i <= bottom; i++) res.add(matrix[i][right]);
        right--;

        if (top <= bottom) {
            for (int j = right; j >= left; j--) res.add(matrix[bottom][j]);
            bottom--;
        }
        if (left <= right) {
            for (int i = bottom; i >= top; i--) res.add(matrix[i][left]);
            left++;
        }
    }
    return res;
}

C++:

vector<int> spiralOrder(vector<vector<int>>& matrix) {
    vector<int> res;
    if (matrix.empty()) return res;
    int top = 0, bottom = matrix.size() - 1;
    int left = 0, right = matrix[0].size() - 1;

    while (top <= bottom && left <= right) {
        for (int j = left; j <= right; ++j) res.push_back(matrix[top][j]);
        top++;
        for (int i = top; i <= bottom; ++i) res.push_back(matrix[i][right]);
        right--;

        if (top <= bottom) {
            for (int j = right; j >= left; --j) res.push_back(matrix[bottom][j]);
            bottom--;
        }
        if (left <= right) {
            for (int i = bottom; i >= top; --i) res.push_back(matrix[i][left]);
            left++;
        }
    }
    return res;
}

Go:

func spiralOrder(matrix [][]int) []int {
    var res []int
    if len(matrix) == 0 { return res }
    top, bottom := 0, len(matrix)-1
    left, right := 0, len(matrix[0])-1

    for top <= bottom && left <= right {
        for j := left; j <= right; j++ { res = append(res, matrix[top][j]) }
        top++
        for i := top; i <= bottom; i++ { res = append(res, matrix[i][right]) }
        right--

        if top <= bottom {
            for j := right; j >= left; j-- { res = append(res, matrix[bottom][j]) }
            bottom--
        }
        if left <= right {
            for i := bottom; i >= top; i-- { res = append(res, matrix[i][left]) }
            left++
        }
    }
    return res
}

Ruby:

def spiral_order(matrix)
  res = []
  return res if matrix.empty?
  top, bottom = 0, matrix.length - 1
  left, right = 0, matrix[0].length - 1

  while top <= bottom && left <= right
    (left..right).each { |j| res << matrix[top][j] }
    top += 1
    (top..bottom).each { |i| res << matrix[i][right] }
    right -= 1

    if top <= bottom
      (left..right).to_a.reverse.each { |j| res << matrix[bottom][j] }
      bottom -= 1
    end
    if left <= right
      (top..bottom).to_a.reverse.each { |i| res << matrix[i][left] }
      left += 1
    end
  end
  res
end

9. Number of Islands

LeetCode 200 |

Medium

Brief: Count the number of islands (connected ‘1’s) in a grid.
Why this pattern?: Foundational graph/grid traversal problem.
Key Insight: Iterate through grid. When ‘1’ found, increment count and DFS/BFS to sink the island (mark as ‘0’).

Visual:

  graph TD
    Find["Find '1'"] -->|DFS| Visit["Mark neighbors as '0'"]
    Visit --> Check["Check adjacent cells"]
    Check -->|Found '1'| Visit
    Check -->|No more '1's| Done["Island Counted"]

JavaScript:

function numIslands(grid) {
    if (!grid.length) return 0;
    let count = 0;

    const dfs = (i, j) => {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] === '0') return;
        grid[i][j] = '0'; // Sink
        dfs(i+1, j); dfs(i-1, j); dfs(i, j+1); dfs(i, j-1);
    };

    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[0].length; j++) {
            if (grid[i][j] === '1') {
                count++;
                dfs(i, j);
            }
        }
    }
    return count;
}

Python:

def num_islands(grid: List[List[str]]) -> int:
    if not grid: return 0
    m, n = len(grid), len(grid[0])
    count = 0

    def dfs(i, j):
        if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] == '0':
            return
        grid[i][j] = '0' # Sink
        dfs(i+1, j); dfs(i-1, j); dfs(i, j+1); dfs(i, j-1)

    for i in range(m):
        for j in range(n):
            if grid[i][j] == '1':
                count += 1
                dfs(i, j)
    return count

Java:

public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) return 0;
    int count = 0;
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == '1') {
                count++;
                dfs(grid, i, j);
            }
        }
    }
    return count;
}
private void dfs(char[][] grid, int i, int j) {
    if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0') return;
    grid[i][j] = '0';
    dfs(grid, i+1, j); dfs(grid, i-1, j); dfs(grid, i, j+1); dfs(grid, i, j-1);
}

C++:

void dfs(vector<vector<char>>& grid, int i, int j) {
    if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] == '0') return;
    grid[i][j] = '0';
    dfs(grid, i+1, j); dfs(grid, i-1, j); dfs(grid, i, j+1); dfs(grid, i, j-1);
}
int numIslands(vector<vector<char>>& grid) {
    int count = 0;
    for (int i = 0; i < grid.size(); ++i) {
        for (int j = 0; j < grid[0].size(); ++j) {
            if (grid[i][j] == '1') {
                count++;
                dfs(grid, i, j);
            }
        }
    }
    return count;
}

Go:

func numIslands(grid [][]byte) int {
    if len(grid) == 0 { return 0 }
    count := 0
    var dfs func(int, int)
    dfs = func(i, j int) {
        if i < 0 || i >= len(grid) || j < 0 || j >= len(grid[0]) || grid[i][j] == '0' { return }
        grid[i][j] = '0'
        dfs(i+1, j); dfs(i-1, j); dfs(i, j+1); dfs(i, j-1)
    }
    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[0]); j++ {
            if grid[i][j] == '1' {
                count++
                dfs(i, j)
            }
        }
    }
    return count
}

Ruby:

def num_islands(grid)
  return 0 if grid.empty?
  count = 0

  (0...grid.length).each do |i|
    (0...grid[0].length).each do |j|
      if grid[i][j] == '1'
        count += 1
        dfs_sink(grid, i, j)
      end
    end
  end
  count
end
def dfs_sink(grid, i, j)
  return if i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0'
  grid[i][j] = '0'
  dfs_sink(grid, i+1, j); dfs_sink(grid, i-1, j); dfs_sink(grid, i, j+1); dfs_sink(grid, i, j-1)
end

Hard Problems

10. Sudoku Solver

LeetCode 37 |

Hard

Brief: Fill empty cells in a 9x9 grid to satisfy Sudoku rules.
Why this pattern?: Complex backtracking on a matrix.
Key Insight: Try 1-9. Check validity (Row, Col, 3x3 Box). Recurse. Backtrack if dead end.

Visual:

  graph TD
    Start["Empty Cell"] --> Try["Try Number k=1..9"]
    Try --> Valid{"Valid?"}
    Valid -- Yes --> Place["Place k"]
    Place --> Recurse["Solve Next Cell"]
    Recurse -- Success --> Done["Return True"]
    Recurse -- Fail --> Backtrack["Reset Cell"]
    Backtrack --> Try

JavaScript:

function solveSudoku(board) {
    const solve = () => {
        for (let i = 0; i < 9; i++) {
            for (let j = 0; j < 9; j++) {
                if (board[i][j] === '.') {
                    for (let c = 1; c <= 9; c++) {
                        const char = c.toString();
                        if (isValid(board, i, j, char)) {
                            board[i][j] = char;
                            if (solve()) return true;
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    };
    solve();
}

function isValid(board, row, col, c) {
    for (let i = 0; i < 9; i++) {
        if (board[i][col] === c) return false;
        if (board[row][i] === c) return false;
        if (board[3 * Math.floor(row / 3) + Math.floor(i / 3)][3 * Math.floor(col / 3) + i % 3] === c) return false;
    }
    return true;
}

Python:

def solveSudoku(board: List[List[str]]) -> None:
    def isValid(row, col, ch):
        for i in range(9):
            if board[i][col] == ch: return False
            if board[row][i] == ch: return False
            if board[3 * (row // 3) + i // 3][3 * (col // 3) + i % 3] == ch: return False
        return True

    def solve():
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    for c in "123456789":
                        if isValid(i, j, c):
                            board[i][j] = c
                            if solve(): return True
                            board[i][j] = '.'
                    return False
        return True
    solve()

Java:

public void solveSudoku(char[][] board) {
    solve(board);
}
private boolean solve(char[][] board) {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (board[i][j] == '.') {
                for (char c = '1'; c <= '9'; c++) {
                    if (isValid(board, i, j, c)) {
                        board[i][j] = c;
                        if (solve(board)) return true;
                        board[i][j] = '.';
                    }
                }
                return false;
            }
        }
    }
    return true;
}
private boolean isValid(char[][] board, int row, int col, char c) {
    for (int i = 0; i < 9; i++) {
        if (board[i][col] == c) return false;
        if (board[row][i] == c) return false;
        if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false;
    }
    return true;
}

C++:

bool isValid(vector<vector<char>>& board, int row, int col, char c) {
    for (int i = 0; i < 9; i++) {
        if (board[i][col] == c) return false;
        if (board[row][i] == c) return false;
        if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false;
    }
    return true;
}
bool solve(vector<vector<char>>& board) {
    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {
            if (board[i][j] == '.') {
                for (char c = '1'; c <= '9'; ++c) {
                    if (isValid(board, i, j, c)) {
                        board[i][j] = c;
                        if (solve(board)) return true;
                        board[i][j] = '.';
                    }
                }
                return false;
            }
        }
    }
    return true;
}
void solveSudoku(vector<vector<char>>& board) {
    solve(board);
}

Go:

func solveSudoku(board [][]byte) {
    solve(board)
}
func solve(board [][]byte) bool {
    for i := 0; i < 9; i++ {
        for j := 0; j < 9; j++ {
            if board[i][j] == '.' {
                for c := byte('1'); c <= '9'; c++ {
                    if isValid(board, i, j, c) {
                        board[i][j] = c
                        if solve(board) { return true }
                        board[i][j] = '.'
                    }
                }
                return false
            }
        }
    }
    return true
}
func isValid(board [][]byte, row, col int, c byte) bool {
    for i := 0; i < 9; i++ {
        if board[i][col] == c { return false }
        if board[row][i] == c { return false }
        if board[3*(row/3) + i/3][3*(col/3) + i%3] == c { return false }
    }
    return true
}

Ruby:

def solve_sudoku(board)
  solve(board)
end
def solve(board)
  (0...9).each do |i|
    (0...9).each do |j|
      if board[i][j] == '.'
        ('1'..'9').each do |c|
          if is_valid(board, i, j, c)
            board[i][j] = c
            return true if solve(board)
            board[i][j] = '.'
          end
        end
        return false
      end
    end
  end
  true
end
def is_valid(board, row, col, c)
  (0...9).each do |i|
    return false if board[i][col] == c
    return false if board[row][i] == c
    return false if board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c
  end
  true
end

Recommended Study Order

Basics: Start with Transpose Matrix (LC 867) to get comfortable with index swapping.
Core Application: Solve Set Matrix Zeroes (LC 73) to practice in-place updates and using markers.
The “Aha” Moment: Tackle Spiral Matrix (LC 54). This tests your ability to handle complex boundary conditions.
Graph Traversal: Move to Number of Islands (LC 200) to understand how to treat matrices as graphs.
Advanced: Attempt Sudoku Solver (LC 37) to master backtracking on grids.

Pro Tip: In interview matrix problems, always clarify if the matrix can be empty, if rows have different lengths (jagged), and if you can modify the input in-place. O(1) space solutions often require using the matrix itself for state storage!