LeetCode 999: Available Captures for Rook

Problem Restatement

We are given an 8 x 8 chessboard.

Each cell contains one of four characters:

Character	Meaning
`"R"`	White rook
`"B"`	White bishop
`"p"`	Black pawn
`"."`	Empty square

There is exactly one rook.

The rook can move horizontally or vertically. It can capture a pawn if the pawn is the first piece in that direction.

The rook cannot move through another piece. A bishop blocks the rook, and a pawn also stops the rook after being captured.

We need to return the number of pawns the rook can capture in one move. The official statement defines the rook movement in four cardinal directions and notes that pieces block its path.

Input and Output

Item	Meaning
Input	An `8 x 8` board
Output	Number of pawns the rook can capture
Rook	`"R"`
Bishop	`"B"` blocks movement
Pawn	`"p"` can be captured if visible
Empty cell	`"."`

Function shape:

def numRookCaptures(board: list[list[str]]) -> int:
    ...

Examples

Example 1:

board = [
    [".",".",".",".",".",".",".","."],
    [".",".",".","p",".",".",".","."],
    [".",".",".","R",".",".",".","p"],
    [".",".",".",".",".",".",".","."],
    [".",".",".",".",".",".",".","."],
    [".",".",".","p",".",".",".","."],
    [".",".",".",".",".",".",".","."],
    [".",".",".",".",".",".",".","."],
]

The rook is at row 2, column 3.

It can capture:

Direction	First piece seen	Result
Up	Pawn	Capture
Down	Pawn	Capture
Left	No piece	No capture
Right	Pawn	Capture

Answer:

Example 2:

board = [
    [".",".",".",".",".",".",".","."],
    [".","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",".","."],
    [".",".",".",".",".",".",".","."],
    [".",".",".",".",".",".",".","."],
]

The rook is blocked by bishops in all four directions.

Answer:

First Thought: Simulate the Rook

The board is small and fixed at 8 x 8.

So we can directly simulate how a rook moves:

Find the rook.
Look upward until hitting a piece or leaving the board.
Look downward.
Look left.
Look right.
Count the first pawn visible in each direction.

This matches the chess rule exactly.

Key Insight

Only the first non-empty square in each direction matters.

If the first piece is a pawn, the rook can capture it.

If the first piece is a bishop, the rook is blocked.

If there is no piece before the board edge, there is no capture.

So each direction contributes either 0 or 1.

Algorithm

First scan the board to find the rook position:

rook_row, rook_col

Then define four directions:

up, down, left, right

For each direction:

Start one square away from the rook.
Move while inside the board.
If the cell is ".", continue.
If the cell is "p", increment the answer and stop this direction.
If the cell is "B", stop this direction.

Return the answer.

Correctness

The algorithm first finds the unique rook position.

For each of the four legal rook directions, it scans squares in the exact order the rook would encounter them while moving. Empty squares do not affect movement, so the scan continues through them.

When the scan reaches a pawn, that pawn is the first piece in that direction, so the rook can capture it in one move. The algorithm counts it and stops, because the rook cannot move beyond the captured pawn.

When the scan reaches a bishop, the bishop blocks the rook, so no pawn beyond it can be captured in that direction. The algorithm stops without counting.

If the scan reaches the board edge without seeing a pawn, then no capture is possible in that direction.

Since the rook can only move in these four directions, and the algorithm checks each direction exactly once, the returned count is correct.

Complexity

Metric	Value	Why
Time	`O(1)`	The board is always `8 x 8`
Space	`O(1)`	Only a few variables are stored

If generalized to an n x n board, the time would be O(n^2) to find the rook and O(n) to scan directions.

Implementation

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

        for r in range(8):
            for c in range(8):
                if board[r][c] == "R":
                    rook_row = r
                    rook_col = c
                    break

            if rook_row != -1:
                break

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

        for dr, dc in directions:
            r = rook_row + dr
            c = rook_col + dc

            while 0 <= r < 8 and 0 <= c < 8:
                if board[r][c] == "p":
                    captures += 1
                    break

                if board[r][c] == "B":
                    break

                r += dr
                c += dc

        return captures

Code Explanation

We first locate the rook:

for r in range(8):
    for c in range(8):
        if board[r][c] == "R":
            rook_row = r
            rook_col = c
            break

After the rook is found, we scan four directions:

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

Each direction uses a row delta and a column delta.

For example:

(1, 0)

moves downward one row at a time.

The scan continues while the position is inside the board:

while 0 <= r < 8 and 0 <= c < 8:

If the first piece is a pawn, count one capture:

if board[r][c] == "p":
    captures += 1
    break

If the first piece is a bishop, stop without counting:

if board[r][c] == "B":
    break

Otherwise the square is empty, so continue moving:

r += dr
c += dc

Testing

def run_tests():
    s = Solution()

    assert s.numRookCaptures([
        [".",".",".",".",".",".",".","."],
        [".",".",".","p",".",".",".","."],
        [".",".",".","R",".",".",".","p"],
        [".",".",".",".",".",".",".","."],
        [".",".",".",".",".",".",".","."],
        [".",".",".","p",".",".",".","."],
        [".",".",".",".",".",".",".","."],
        [".",".",".",".",".",".",".","."],
    ]) == 3

    assert s.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

    assert s.numRookCaptures([
        [".",".",".",".",".",".",".","."],
        [".",".",".","p",".",".",".","."],
        [".",".",".","p",".",".",".","."],
        ["p","p",".","R",".","p","B","."],
        [".",".",".",".",".",".",".","."],
        [".",".",".","B",".",".",".","."],
        [".",".",".","p",".",".",".","."],
        [".",".",".",".",".",".",".","."],
    ]) == 3

    print("all tests passed")

run_tests()

Test	Expected	Why
First board	`3`	Rook sees three pawns
Bishop-blocked board	`0`	Bishops block all directions
Mixed board	`3`	Captures first visible pawns only