LeetCode 999 - Available Captures for Rook

The problem gives us an 8 x 8 chessboard represented as a matrix of characters. Each cell contains one of four possible values: - 'R' represents the white rook - 'p' represents a black pawn - 'B' represents a white bishop - '.

leetcodeeasyarraymatrixsimulation

LeetCode Problem 999

Difficulty: 🟢 Easy
Topics: Array, Matrix, Simulation

Solution

Problem Understanding

The problem gives us an 8 x 8 chessboard represented as a matrix of characters. Each cell contains one of four possible values:

  • 'R' represents the white rook
  • 'p' represents a black pawn
  • 'B' represents a white bishop
  • '.' represents an empty square

There is exactly one rook on the board. The task is to determine how many pawns the rook can capture in one move.

A rook in chess moves horizontally or vertically. It can continue moving in one direction until one of two things happens:

  • It reaches the edge of the board
  • It encounters another piece

The rook cannot move through pieces. This is the most important rule in the problem. If a bishop or pawn appears in a direction, the rook stops there and cannot continue beyond it.

A pawn is considered capturable if:

  • It lies in the same row or column as the rook
  • There are no pieces between the rook and that pawn

The input size is fixed because the board is always 8 x 8. This means performance is not a serious concern, but we still want a clean and efficient solution.

The constraints guarantee that:

  • The board dimensions are always valid
  • There is exactly one rook
  • Every character is valid chess notation for this problem

Several edge cases are important:

  • A bishop may block the rook before a pawn is reached
  • Multiple pawns may exist in one direction, but only the first reachable piece matters
  • The rook may be near the edge of the board
  • There may be no capturable pawns at all
  • Pawns may exist behind bishops and therefore be unreachable

A naive implementation might incorrectly continue scanning after hitting a bishop or count multiple pawns in the same direction. Correct handling of blocking pieces is essential.

Approaches

Brute Force Approach

A brute force strategy would examine every pawn on the board individually. For each pawn, we could check whether it shares the same row or column as the rook and whether any blocking piece exists between them.

The algorithm would proceed as follows:

  1. Locate the rook.
  2. Iterate through every square on the board.
  3. Whenever a pawn is found:
  • Check whether it is aligned horizontally or vertically with the rook.
  • Scan the cells between the rook and the pawn to determine whether a bishop or another pawn blocks the path.
  1. Count all pawns that are reachable.

This approach works correctly because every pawn is explicitly verified. However, it performs unnecessary work. The rook can only attack along four directions, so checking every pawn independently is more complicated than needed.

Optimal Approach

The key observation is that the rook only interacts with pieces in four directions:

  • Up
  • Down
  • Left
  • Right

Once we find the rook, we can simulate its movement in each direction independently.

For each direction:

  • Move one square at a time.

  • Stop immediately if:

  • We leave the board

  • We encounter a bishop

  • If we encounter a pawn before anything else, increment the answer and stop searching in that direction.

This mirrors the real movement rules of a rook in chess and avoids unnecessary checks.

Because the board size is tiny and fixed, this approach is extremely efficient and very easy to reason about.

Approach Time Complexity Space Complexity Notes
Brute Force O(8² × 8) O(1) Check every pawn and scan paths individually
Optimal O(8²) O(1) Scan only four directions from the rook

Algorithm Walkthrough

  1. First, scan the entire board to locate the rook's position. Store its row and column indices because all future movement originates from this square.
  2. Define the four movement directions:
  • Up: (-1, 0)
  • Down: (1, 0)
  • Left: (0, -1)
  • Right: (0, 1)
  1. For each direction, begin from the rook's position and move one step at a time.
  2. At every step:
  • Compute the next row and column.
  • If the new position is outside the board, stop searching in this direction because the rook cannot move further.
  • If the cell contains a bishop 'B', stop searching because bishops block movement.
  • If the cell contains a pawn 'p', increment the capture count and stop searching because the rook captures the first reachable pawn.
  1. Continue this process for all four directions.
  2. Return the total number of capturable pawns.

Why it works

The rook moves independently in each of the four cardinal directions. In chess, the first piece encountered in a direction completely determines what happens next:

  • If it is a bishop, movement stops and no pawn can be captured beyond it.
  • If it is a pawn, that pawn is capturable and movement stops there.

By scanning outward from the rook exactly as the rook would move in a real game, the algorithm guarantees that every capturable pawn is counted exactly once.

Python Solution

from typing import List

class Solution:
    def numRookCaptures(self, board: List[List[str]]) -> int:
        rook_row = -1
        rook_col = -1

        # Locate the rook
        for row in range(8):
            for col in range(8):
                if board[row][col] == 'R':
                    rook_row = row
                    rook_col = col
                    break

            if rook_row != -1:
                break

        captures = 0

        # Four directions: up, down, left, right
        directions = [
            (-1, 0),
            (1, 0),
            (0, -1),
            (0, 1)
        ]

        for dr, dc in directions:
            row = rook_row + dr
            col = rook_col + dc

            while 0 <= row < 8 and 0 <= col < 8:
                if board[row][col] == 'B':
                    break

                if board[row][col] == 'p':
                    captures += 1
                    break

                row += dr
                col += dc

        return captures

The implementation begins by locating the rook. Since the problem guarantees exactly one rook, we stop searching once it is found.

After locating the rook, the code defines the four possible movement directions. Each direction is represented as a row and column offset.

For every direction, the algorithm moves step by step outward from the rook. The while loop ensures that movement stays within the board boundaries.

Inside the loop:

  • A bishop immediately terminates the search in that direction because the rook cannot move through it.
  • A pawn increments the answer and also terminates the search because only the first reachable piece matters.
  • Empty cells allow the scan to continue.

Finally, the total number of captures is returned.

Go Solution

func numRookCaptures(board [][]byte) int {
    rookRow, rookCol := -1, -1

    // Locate the rook
    for r := 0; r < 8; r++ {
        for c := 0; c < 8; c++ {
            if board[r][c] == 'R' {
                rookRow = r
                rookCol = c
                break
            }
        }

        if rookRow != -1 {
            break
        }
    }

    captures := 0

    directions := [][]int{
        {-1, 0},
        {1, 0},
        {0, -1},
        {0, 1},
    }

    for _, dir := range directions {
        dr, dc := dir[0], dir[1]

        row := rookRow + dr
        col := rookCol + dc

        for row >= 0 && row < 8 && col >= 0 && col < 8 {
            if board[row][col] == 'B' {
                break
            }

            if board[row][col] == 'p' {
                captures++
                break
            }

            row += dr
            col += dc
        }
    }

    return captures
}

The Go implementation follows the same logic as the Python version. The primary difference is the use of [][]byte instead of a list of strings. Character comparisons therefore use byte literals such as 'R', 'B', and 'p'.

Go slices are naturally suited for representing the chessboard, and no additional memory allocation is required beyond a few integer variables.

Integer overflow is not a concern because the maximum answer is only 4.

Worked Examples

Example 1

Input:

[
[".",".",".",".",".",".",".","."],
[".",".",".","p",".",".",".","."],
[".",".",".","R",".",".",".","p"],
[".",".",".",".",".",".",".","."],
[".",".",".",".",".",".",".","."],
[".",".",".","p",".",".",".","."],
[".",".",".",".",".",".",".","."],
[".",".",".",".",".",".",".","."]
]

The rook is located at (2, 3).

Up Direction

Position Value Action
(1, 3) p Capture pawn, stop

Captures = 1

Down Direction

Position Value Action
(3, 3) . Continue
(4, 3) . Continue
(5, 3) p Capture pawn, stop

Captures = 2

Left Direction

Position Value Action
(2, 2) . Continue
(2, 1) . Continue
(2, 0) . Continue

No capture.

Right Direction

Position Value Action
(2, 4) . Continue
(2, 5) . Continue
(2, 6) . Continue
(2, 7) p Capture pawn, stop

Final captures = 3

Example 2

The rook is completely surrounded by bishops.

Up Direction

Position Value Action
(2, 3) B Stop immediately

Down Direction

Position Value Action
(4, 3) B Stop immediately

Left Direction

Position Value Action
(3, 2) B Stop immediately

Right Direction

Position Value Action
(3, 4) B Stop immediately

No pawn is reachable.

Final captures = 0

Example 3

The rook is at (3, 3).

Up Direction

Position Value Action
(2, 3) p Capture pawn

Captures = 1

Down Direction

Position Value Action
(4, 3) . Continue
(5, 3) B Stop

No capture downward.

Left Direction

Position Value Action
(3, 2) . Continue
(3, 1) p Capture pawn

Captures = 2

Right Direction

Position Value Action
(3, 4) . Continue
(3, 5) p Capture pawn

Final captures = 3

Complexity Analysis

Measure Complexity Explanation
Time O(8²) Scan the board once and explore four directions
Space O(1) Only a few variables are used

The board size is fixed at 8 x 8, so the algorithm effectively runs in constant time. More generally, for an n x n board, the complexity would be O(n²) because we may scan the board once to find the rook and then traverse at most n cells in each of four directions.

The algorithm uses constant extra space because it stores only coordinates, counters, and direction vectors.

Test Cases

from typing import List

class Solution:
    def numRookCaptures(self, board: List[List[str]]) -> int:
        rook_row = -1
        rook_col = -1

        for row in range(8):
            for col in range(8):
                if board[row][col] == 'R':
                    rook_row = row
                    rook_col = col
                    break

            if rook_row != -1:
                break

        captures = 0

        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        for dr, dc in directions:
            row = rook_row + dr
            col = rook_col + dc

            while 0 <= row < 8 and 0 <= col < 8:
                if board[row][col] == 'B':
                    break

                if board[row][col] == 'p':
                    captures += 1
                    break

                row += dr
                col += dc

        return captures

sol = Solution()

# Example 1, rook captures three pawns
assert sol.numRookCaptures([
    [".",".",".",".",".",".",".","."],
    [".",".",".","p",".",".",".","."],
    [".",".",".","R",".",".",".","p"],
    [".",".",".",".",".",".",".","."],
    [".",".",".",".",".",".",".","."],
    [".",".",".","p",".",".",".","."],
    [".",".",".",".",".",".",".","."],
    [".",".",".",".",".",".",".","."]
]) == 3

# Example 2, bishops block all directions
assert sol.numRookCaptures([
    [".",".",".",".",".",".",".","."],
    [".","p","p","p","p","p",".","."],
    [".","p","p","B","p","p",".","."],
    [".","p","B","R","B","p",".","."],
    [".","p","p","B","p","p",".","."],
    [".","p","p","p","p","p",".","."],
    [".",".",".",".",".",".",".","."],
    [".",".",".",".",".",".",".","."]
]) == 0

# Example 3, mixed blockers and captures
assert sol.numRookCaptures([
    [".",".",".",".",".",".",".","."],
    [".",".",".","p",".",".",".","."],
    [".",".",".","p",".",".",".","."],
    ["p","p",".","R",".","p","B","."],
    [".",".",".",".",".",".",".","."],
    [".",".",".","B",".",".",".","."],
    [".",".",".","p",".",".",".","."],
    [".",".",".",".",".",".",".","."]
]) == 3

# No pawns anywhere on the board
assert sol.numRookCaptures([
    [".",".",".",".",".",".",".","."],
    [".",".",".",".",".",".",".","."],
    [".",".",".",".",".",".",".","."],
    [".",".",".","R",".",".",".","."],
    [".",".",".",".",".",".",".","."],
    [".",".",".",".",".",".",".","."],
    [".",".",".",".",".",".",".","."],
    [".",".",".",".",".",".",".","."]
]) == 0

# Pawns blocked by bishops
assert sol.numRookCaptures([
    [".",".",".","p",".",".",".","."],
    [".",".",".","B",".",".",".","."],
    [".",".",".",".",".",".",".","."],
    ["p","B",".","R",".","B","p","."],
    [".",".",".",".",".",".",".","."],
    [".",".",".","B",".",".",".","."],
    [".",".",".","p",".",".",".","."],
    [".",".",".",".",".",".",".","."]
]) == 0

# Rook near corner with one capture
assert sol.numRookCaptures([
    ["R",".",".","p",".",".",".","."],
    [".",".",".",".",".",".",".","."],
    [".",".",".",".",".",".",".","."],
    [".",".",".",".",".",".",".","."],
    [".",".",".",".",".",".",".","."],
    [".",".",".",".",".",".",".","."],
    [".",".",".",".",".",".",".","."],
    [".",".",".",".",".",".",".","."]
]) == 1

# Multiple pawns in one direction, only first is capturable
assert sol.numRookCaptures([
    [".",".",".",".",".",".",".","."],
    [".",".",".","p",".",".",".","."],
    [".",".",".","p",".",".",".","."],
    [".",".",".","R",".",".",".","."],
    [".",".",".",".",".",".",".","."],
    [".",".",".",".",".",".",".","."],
    [".",".",".",".",".",".",".","."],
    [".",".",".",".",".",".",".","."]
]) == 1
Test Why
Example 1 Standard successful captures in multiple directions
Example 2 Bishops completely block the rook
Example 3 Combination of captures and blockers
No pawns Verifies zero result handling
Pawns behind bishops Ensures blocked pawns are not counted
Rook in corner Validates boundary handling
Multiple pawns in one direction Ensures only first reachable pawn is counted

Edge Cases

Bishops immediately adjacent to the rook

One important edge case occurs when bishops surround the rook directly on adjacent squares. A buggy implementation might continue scanning past the bishops and incorrectly count pawns behind them.

The implementation handles this correctly because encountering a bishop immediately triggers a break, terminating the search in that direction.

Multiple pawns in the same direction

Another subtle case occurs when several pawns appear along one line. In real chess, the rook can only capture the first piece encountered. A naive implementation might count every pawn in the row or column.

The algorithm avoids this by stopping immediately after capturing the first pawn in a direction.

Rook positioned near the edge of the board

When the rook starts close to a border or corner, careless index handling can cause out of bounds access errors.

The implementation prevents this using the condition:

while 0 <= row < 8 and 0 <= col < 8:

This guarantees every board access is valid before reading the cell.

Empty board except for the rook

If no pawns exist anywhere on the board, the correct answer is 0. Some implementations accidentally assume at least one pawn exists.

The current solution naturally handles this situation because all directional scans terminate without incrementing the counter.