999. Available Captures for Rook - Solution

The problem

You are given an 8 x 8 matrix representing a chessboard. There is exactly one white rook represented by 'R', some number of white bishops 'B', and some number of black pawns 'p'. Empty squares are represented by '.'.

A rook can move any number of squares horizontally or vertically (up, down, left, right) until it reaches another piece or the edge of the board. A rook is attacking a pawn if it can move to the pawn's square in one move.

Note: A rook cannot move through other pieces, such as bishops or pawns. This means a rook cannot attack a pawn if there is another piece blocking the path.

Return the number of pawns the white rook is attacking.

Example 1:

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

Output: 3

Explanation:

In this example, the rook is attacking all the pawns.

Example 2:

Input: 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",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]

Output: 0

Explanation:

The bishops are blocking the rook from attacking any of the pawns.

Example 3:

Input: board = [[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","p",".",".",".","."],["p","p",".","R",".","p","B","."],[".",".",".",".",".",".",".","."],[".",".",".","B",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."]]

Output: 3

Explanation:

The rook is attacking the pawns at positions b5, d6, and f5.

Constraints:

board.length == 8
board[i].length == 8
board[i][j] is either 'R', '.', 'B', or 'p'
There is exactly one cell with board[i][j] == 'R'

Approach overview

Problem Overview: You’re given an 8x8 chessboard represented as a matrix. A white rook 'R' can move horizontally or vertically until it hits another piece. Pawns 'p' can be captured, while bishops 'B' block the rook’s path. The task is to count how many pawns the rook can capture in the four cardinal directions.

Approach 1: Direction-Based Iteration (O(n) time, O(1) space)

First locate the rook’s position by scanning the board. Once found, simulate the rook’s movement in the four directions: up, down, left, and right. For each direction, iterate step-by-step through the board. If you encounter a bishop 'B', the path is blocked and you stop exploring that direction. If you encounter a pawn 'p', increment the capture count and stop because the rook captures only the first piece in that direction.

This approach relies on simple iteration over a matrix and direct simulation of chess movement rules. The key insight is that the rook only cares about the first non-empty square in each direction. Because there are only four directions and at most 8 cells per direction, the traversal is extremely efficient. Time complexity is O(n) where n represents the board dimension, and space complexity remains O(1) since no extra structures are needed.

Approach 2: Multi-Directional Traversal with Early Exit (O(n) time, O(1) space)

This variation treats each direction as an independent traversal starting from the rook. Instead of scanning the board multiple times, you locate the rook once and then expand outward in four directions using directional vectors like (-1,0), (1,0), (0,-1), and (0,1). Each step checks the current square and exits immediately when a blocking bishop or capturable pawn appears.

The early-exit behavior reduces unnecessary checks and keeps the logic clean. The implementation closely resembles typical array or simulation patterns used in grid problems. Every direction stops as soon as a decision is made, ensuring no redundant traversal. The complexity remains O(n) time and O(1) space, but the structure is easier to generalize to larger boards or similar movement problems.

Recommended for interviews: Direction-based iteration is what interviewers expect. It directly models rook movement and shows you understand grid traversal and early stopping conditions. A brute-force board scan shows basic understanding, but directional traversal demonstrates stronger control over matrix simulation patterns.

Approach 1: Direction-Based Iteration

This approach involves finding the rook on the board first. Once located, traverse from the rook's position in all four possible directions (up, down, left, right) until you either reach the edge of the board or hit a piece (bishop or pawn). If you encounter a pawn ('p') before a blocking piece or the edge, count it as an attack.

Python

def numRookCaptures(board) -> int:
    def capture_in_direction(x, y, dx, dy):
        while 0 <= x < 8 and 0 <= y < 8:
            if board[x][y] == 'B':
                break
            if board[x][y] == 'p':
                return 1
            x, y = x + dx, y + dy
        return 0

    for i in range(8):
        for j in range(8):
            if board[i][j] == 'R':
                return (
                    capture_in_direction(i, j, 1, 0) +  # Down
                    capture_in_direction(i, j, -1, 0) + # Up
                    capture_in_direction(i, j, 0, 1) +  # Right
                    capture_in_direction(i, j, 0, -1)   # Left
                )
    return 0

# Testing the function
board = [
    ['.', '.', '.', '.', '.', '.', '.', '.'],
    ['.', '.', '.', 'p', '.', '.', '.', '.'],
    ['.', '.', '.', 'R', '.', '.', '.', 'p'],
    ['.', '.', '.', '.', '.', '.', '.', '.'],
    ['.', '.', '.', '.', '.', '.', '.', '.'],
    ['.', '.', '.', 'p', '.', '.', '.', '.'],
    ['.', '.', '.', '.', '.', '.', '.', '.'],
    ['.', '.', '.', '.', '.', '.', '.', '.']
]
print(numRookCaptures(board))  # Output: 3

Java

public class RookCapture {
    public int numRookCaptures(char[][] board) {
        int rookRow = -1, rookCol = -1;
        int pawnsCaptured = 0;
        int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; // down, up, right, left

        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                if (board[i][j] == 'R') {
                    rookRow = i;
                    rookCol = j;
                    break;
                }
            }
            if (rookRow != -1) break;
        }

        for (int[] dir : directions) {
            int x = rookRow, y = rookCol;
            while (true) {
                x += dir[0];
                y += dir[1];
                if (x < 0 || x >= 8 || y < 0 || y >= 8 || board[x][y] == 'B')
                    break;
                if (board[x][y] == 'p') {
                    pawnsCaptured++;
                    break;
                }
            }
        }

        return pawnsCaptured;
    }

    public static void main(String[] args) {
        char[][] board = {
            {'.', '.', '.', '.', '.', '.', '.', '.'},
            {'.', '.', '.', 'p', '.', '.', '.', '.'},
            {'.', '.', '.', 'R', '.', '.', '.', 'p'},
            {'.', '.', '.', '.', '.', '.', '.', '.'},
            {'.', '.', '.', '.', '.', '.', '.', '.'},
            {'.', '.', '.', 'p', '.', '.', '.', '.'},
            {'.', '.', '.', '.', '.', '.', '.', '.'},
            {'.', '.', '.', '.', '.', '.', '.', '.'}
        };
        RookCapture rc = new RookCapture();
        System.out.println(rc.numRookCaptures(board)); // Output: 3
    }
}

C++

#include <vector>
#include <iostream>

using namespace std;

int numRookCaptures(vector<vector<char>>& board) {
    int rookRow, rookCol;
    int pawnsCaptured = 0;
    const vector<vector<int>> directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; // down, up, right, left

    for (int i = 0; i < 8; ++i) {
        for (int j = 0; j < 8; ++j) {
            if (board[i][j] == 'R') {
                rookRow = i;
                rookCol = j;
                break;
            }
        }
    }

    for (const auto& dir : directions) {
        int x = rookRow, y = rookCol;
        while (true) {
            x += dir[0];
            y += dir[1];
            if (x < 0 || x >= 8 || y < 0 || y >= 8 || board[x][y] == 'B')
                break;
            if (board[x][y] == 'p') {
                pawnsCaptured++;
                break;
            }
        }
    }

    return pawnsCaptured;
}

int main() {
    vector<vector<char>> board = {
        {'.', '.', '.', '.', '.', '.', '.', '.'},
        {'.', '.', '.', 'p', '.', '.', '.', '.'},
        {'.', '.', '.', 'R', '.', '.', '.', 'p'},
        {'.', '.', '.', '.', '.', '.', '.', '.'},
        {'.', '.', '.', '.', '.', '.', '.', '.'},
        {'.', '.', '.', 'p', '.', '.', '.', '.'},
        {'.', '.', '.', '.', '.', '.', '.', '.'},
        {'.', '.', '.', '.', '.', '.', '.', '.'}
    };
    cout << numRookCaptures(board) << endl; // Output: 3
}

JavaScript

var numRookCaptures = function(board) {
    let pawnsCaptured = 0;
    const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]; // down, up, right, left
    let rookRow = -1, rookCol = -1;

    for (let i = 0; i < 8; i++) {
        for (let j = 0; j < 8; j++) {
            if (board[i][j] === 'R') {
                rookRow = i;
                rookCol = j;
                break;
            }
        }
        if (rookRow !== -1) break;
    }

    for (const [dx, dy] of directions) {
        let x = rookRow;
        let y = rookCol;
        while (true) {
            x += dx;
            y += dy;
            if (x < 0 || x >= 8 || y < 0 || y >= 8 || board[x][y] === 'B')
                break;
            if (board[x][y] === 'p') {
                pawnsCaptured++;
                break;
            }
        }
    }

    return pawnsCaptured;
};

// Example Test
const board = [
    ['.', '.', '.', '.', '.', '.', '.', '.'],
    ['.', '.', '.', 'p', '.', '.', '.', '.'],
    ['.', '.', '.', 'R', '.', '.', '.', 'p'],
    ['.', '.', '.', '.', '.', '.', '.', '.'],
    ['.', '.', '.', '.', '.', '.', '.', '.'],
    ['.', '.', '.', 'p', '.', '.', '.', '.'],
    ['.', '.', '.', '.', '.', '.', '.', '.'],
    ['.', '.', '.', '.', '.', '.', '.', '.']
];

console.log(numRookCaptures(board)); // Output: 3

#include <stdio.h>

int numRookCaptures(char board[8][8]) {
    int rookRow = -1, rookCol = -1;
    int directions[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};  // down, up, right, left
    int pawnsCaptured = 0;

    for (int i = 0; i < 8; ++i) {
        for (int j = 0; j < 8; ++j) {
            if (board[i][j] == 'R') {
                rookRow = i;
                rookCol = j;
                break;
            }
        }
    }

    for (int d = 0; d < 4; ++d) {
        int x = rookRow, y = rookCol;
        while (1) {
            x += directions[d][0];
            y += directions[d][1];
            if (x < 0 || x >= 8 || y < 0 || y >= 8 || board[x][y] == 'B')
                break;
            if (board[x][y] == 'p') {
                pawnsCaptured++;
                break;
            }
        }
    }

    return pawnsCaptured;
}

int main() {
    char board[8][8] = {
        {'.', '.', '.', '.', '.', '.', '.', '.'},
        {'.', '.', '.', 'p', '.', '.', '.', '.'},
        {'.', '.', '.', 'R', '.', '.', '.', 'p'},
        {'.', '.', '.', '.', '.', '.', '.', '.'},
        {'.', '.', '.', '.', '.', '.', '.', '.'},
        {'.', '.', '.', 'p', '.', '.', '.', '.'},
        {'.', '.', '.', '.', '.', '.', '.', '.'},
        {'.', '.', '.', '.', '.', '.', '.', '.'}
    };

    printf("%d\n", numRookCaptures(board)); // Output: 3
    return 0;
}

using System;
public class RookCapture {
    public int NumRookCaptures(char[][] board) {
        int pawnsCaptured = 0;
        int rookRow = 0, rookCol = 0;
        int[][] directions = new int[][] {
            new int[] {1, 0}, new int[] {-1, 0},
            new int[] {0, 1}, new int[] {0, -1}
        };

        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                if (board[i][j] == 'R') {
                    rookRow = i;
                    rookCol = j;
                    break;
                }
            }
        }

        foreach (var dir in directions) {
            int x = rookRow, y = rookCol;
            while (true) {
                x += dir[0];
                y += dir[1];
                if (x < 0 || x >= 8 || y < 0 || y >= 8 || board[x][y] == 'B')
                    break;
                if (board[x][y] == 'p') {
                    pawnsCaptured++;
                    break;
                }
            }
        }

        return pawnsCaptured;
    }

    public static void Main() {
        char[][] board = new char[][] {
            new char[] {'.', '.', '.', '.', '.', '.', '.', '.'},
            new char[] {'.', '.', '.', 'p', '.', '.', '.', '.'},
            new char[] {'.', '.', '.', 'R', '.', '.', '.', 'p'},
            new char[] {'.', '.', '.', '.', '.', '.', '.', '.'},
            new char[] {'.', '.', '.', '.', '.', '.', '.', '.'},
            new char[] {'.', '.', '.', 'p', '.', '.', '.', '.'},
            new char[] {'.', '.', '.', '.', '.', '.', '.', '.'},
            new char[] {'.', '.', '.', '.', '.', '.', '.', '.'}
        };

        RookCapture rc = new RookCapture();
        Console.WriteLine(rc.NumRookCaptures(board)); // Output: 3
    }
}

This Python solution uses a helper function to traverse in each of the four cardinal directions. Once the rook spot is identified, the function checks in each direction to see if an enemy pawn is present before any blocks are encountered.

Complexity

Time Complexity: O(N), since every potential line of the rook must still be verified, approximately 28 to 32 squares.
Space Complexity: O(1), only the function's local storage and computational vectors are used.

Try this approach in the editor

Approach 2: Multi-Directional Traversal with Early Exit

This approach also begins by locating the rook but applies a multi-threaded like traversal where each direction is explored and can theoretically break free once the path is obstructed by a Bishop or edge effectively.

Python

def numRookCaptures(board):
    def capture_in_direction(x, y, dx, dy):
        while 0 <= x < 8 and 0 <= y < 8:
            if board[x][y] == 'B':
                break
            if board[x][y] == 'p':
                return 1
            x, y = x + dx, y + dy
        return 0

    for i in range(8):
        for j in range(8):
            if board[i][j] == 'R':
                return (
                    capture_in_direction(i, j, 1, 0) +  # Down
                    capture_in_direction(i, j, -1, 0) + # Up
                    capture_in_direction(i, j, 0, 1) +  # Right
                    capture_in_direction(i, j, 0, -1)   # Left
                )
    return 0

# Testing the function
board = [
    ['.', '.', '.', '.', '.', '.', '.', '.'],
    ['.', '.', '.', 'p', '.', '.', '.', '.'],
    ['.', '.', '.', 'R', '.', '.', '.', 'p'],
    ['.', '.', '.', '.', '.', '.', '.', '.'],
    ['.', '.', '.', '.', '.', '.', '.', '.'],
    ['.', '.', '.', 'p', '.', '.', '.', '.'],
    ['.', '.', '.', '.', '.', '.', '.', '.'],
    ['.', '.', '.', '.', '.', '.', '.', '.']
]
print(numRookCaptures(board))  # Output: 3

Java

public class RookCapture {
    public int numRookCaptures(char[][] board) {
        int pawnsCaptured = 0;
        int rookRow = -1, rookCol = -1;
        int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        outerLoop: for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                if (board[i][j] == 'R') {
                    rookRow = i;
                    rookCol = j;
                    break outerLoop;
                }
            }
        }

        for (int[] dir : directions) {
            for (int d = 1; ; d++) {
                int x = rookRow + d * dir[0];
                int y = rookCol + d * dir[1];
                if (x < 0 || y < 0 || x >= 8 || y >= 8 || board[x][y] == 'B')
                    break;
                if (board[x][y] == 'p') {
                    pawnsCaptured++;
                    break;
                }
            }
        }

        return pawnsCaptured;
    }

    public static void main(String[] args) {
        char[][] board = {
            {'.', '.', '.', '.', '.', '.', '.', '.'},
            {'.', '.', '.', 'p', '.', '.', '.', '.'},
            {'.', '.', '.', 'R', '.', '.', '.', 'p'},
            {'.', '.', '.', '.', '.', '.', '.', '.'},
            {'.', '.', '.', '.', '.', '.', '.', '.'},
            {'.', '.', '.', 'p', '.', '.', '.', '.'},
            {'.', '.', '.', '.', '.', '.', '.', '.'},
            {'.', '.', '.', '.', '.', '.', '.', '.'}
        };
        RookCapture rc = new RookCapture();
        System.out.println(rc.numRookCaptures(board)); // Output: 3
    }
}

C++

#include <iostream>
#include <vector>

using namespace std;

int numRookCaptures(vector<vector<char>>& board) {
    int rookRow, rookCol;
    int pawnsCaptured = 0;
    vector<vector<int>> directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; // down, up, right, left

    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            if (board[i][j] == 'R') {
                rookRow = i;
                rookCol = j;
                break;
            }
        }
        if (rookRow != 0) break;
    }

    for (auto& dir : directions) {
        for (int d = 1; ; d++) {
            int x = rookRow + d * dir[0];
            int y = rookCol + d * dir[1];
            if (x < 0 || y < 0 || x >= 8 || y >= 8 || board[x][y] == 'B')
                break;
            if (board[x][y] == 'p') {
                pawnsCaptured++;
                break;
            }
        }
    }

    return pawnsCaptured;
}

int main() {
    vector<vector<char>> board = {
        {'.', '.', '.', '.', '.', '.', '.', '.'},
        {'.', '.', '.', 'p', '.', '.', '.', '.'},
        {'.', '.', '.', 'R', '.', '.', '.', 'p'},
        {'.', '.', '.', '.', '.', '.', '.', '.'},
        {'.', '.', '.', '.', '.', '.', '.', '.'},
        {'.', '.', '.', 'p', '.', '.', '.', '.'},
        {'.', '.', '.', '.', '.', '.', '.', '.'},
        {'.', '.', '.', '.', '.', '.', '.', '.'}
    };
    cout << numRookCaptures(board) << endl; // Output: 3
    return 0;
}

JavaScript

var numRookCaptures = function(board) {
    let pawnsCaptured = 0;
    const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]; // down, up, right, left
    let rookRow = -1, rookCol = -1;

    for (let i = 0; i < 8; i++) {
        for (let j = 0; j < 8; j++) {
            if (board[i][j] === 'R') {
                rookRow = i;
                rookCol = j;
                break;
            }
        }
        if (rookRow !== -1) break;
    }

    for (const [dx, dy] of directions) {
        for (let d = 1; ; d++) {
            let x = rookRow + d * dx;
            let y = rookCol + d * dy;
            if (x < 0 || y < 0 || x >= 8 || y >= 8 || board[x][y] === 'B')
                break;
            if (board[x][y] === 'p') {
                pawnsCaptured++;
                break;
            }
        }
    }

    return pawnsCaptured;
};

// Example Test
const board = [
    ['.', '.', '.', '.', '.', '.', '.', '.'],
    ['.', '.', '.', 'p', '.', '.', '.', '.'],
    ['.', '.', '.', 'R', '.', '.', '.', 'p'],
    ['.', '.', '.', '.', '.', '.', '.', '.'],
    ['.', '.', '.', '.', '.', '.', '.', '.'],
    ['.', '.', '.', 'p', '.', '.', '.', '.'],
    ['.', '.', '.', '.', '.', '.', '.', '.'],
    ['.', '.', '.', '.', '.', '.', '.', '.']
];

console.log(numRookCaptures(board)); // Output: 3

#include <stdio.h>

int numRookCaptures(char board[8][8]) {
    int directions[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};  // down, up, right, left
    int rookRow, rookCol;
    int pawnsCaptured = 0;

    // Find rook's position
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            if (board[i][j] == 'R') {
                rookRow = i;
                rookCol = j;
                break;
            }
        }
    }

    // Explore in each direction
    for (int d = 0; d < 4; d++) {
        for (int dist = 1; ; dist++) {
            int x = rookRow + dist * directions[d][0];
            int y = rookCol + dist * directions[d][1];
            if (x < 0 || x >= 8 || y < 0 || y >= 8 || board[x][y] == 'B')
                break;
            if (board[x][y] == 'p') {
                pawnsCaptured++;
                break;
            }
        }
    }

    return pawnsCaptured;
}

int main() {
    char board[8][8] = {
        {'.', '.', '.', '.', '.', '.', '.', '.'},
        {'.', '.', '.', 'p', '.', '.', '.', '.'},
        {'.', '.', '.', 'R', '.', '.', '.', 'p'},
        {'.', '.', '.', '.', '.', '.', '.', '.'},
        {'.', '.', '.', '.', '.', '.', '.', '.'},
        {'.', '.', '.', 'p', '.', '.', '.', '.'},
        {'.', '.', '.', '.', '.', '.', '.', '.'},
        {'.', '.', '.', '.', '.', '.', '.', '.'}
    };

    printf("%d\n", numRookCaptures(board)); // Output: 3
    return 0;
}

using System;
public class RookCapture {
    public int NumRookCaptures(char[][] board) {
        int pawnsCaptured = 0;
        int rookRow = -1, rookCol = -1;
        int[][] directions = new int[][] {
            new int[] {1, 0}, new int[] {-1, 0},
            new int[] {0, 1}, new int[] {0, -1}
        };

        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                if (board[i][j] == 'R') {
                    rookRow = i;
                    rookCol = j;
                    break;
                }
            }
            if (rookRow != -1) break;
        }

        foreach (var dir in directions) {
            for (int d = 1; ; d++) {
                int x = rookRow + d * dir[0], y = rookCol + d * dir[1];
                if (x < 0 || x >= 8 || y < 0 || y >= 8 || board[x][y] == 'B')
                    break;
                if (board[x][y] == 'p') {
                    pawnsCaptured++;
                    break;
                }
            }
        }

        return pawnsCaptured;
    }

    public static void Main() {
        char[][] board = new char[][] {
            new char[] {'.', '.', '.', '.', '.', '.', '.', '.'},
            new char[] {'.', '.', '.', 'p', '.', '.', '.', '.'},
            new char[] {'.', '.', '.', 'R', '.', '.', '.', 'p'},
            new char[] {'.', '.', '.', '.', '.', '.', '.', '.'},
            new char[] {'.', '.', '.', '.', '.', '.', '.', '.'},
            new char[] {'.', '.', '.', 'p', '.', '.', '.', '.'},
            new char[] {'.', '.', '.', '.', '.', '.', '.', '.'},
            new char[] {'.', '.', '.', '.', '.', '.', '.', '.'}
        };

        RookCapture rc = new RookCapture();
        Console.WriteLine(rc.NumRookCaptures(board)); // Output: 3
    }
}

Python implements a modular capture-in-direction function for diagnostic simplicity checking an iterative compass with early avenue abandonment when blockages emerge expediently from board's peripherals.

Complexity

Time Complexity: O(1) constants in logistical pathing computation replica of integration points.
Space Complexity: O(1), employing minimalist path delineation structures.

Try this approach in the editor

Approach 3: Simulation

We first traverse the board to find the position of the rook (i, j). Then, starting from (i, j), we traverse in four directions: up, down, left, and right.

If it is not the boundary and not a bishop, continue moving forward.
If it is a pawn, increment the answer by one and stop traversing in that direction.

After traversing in all four directions, we get the answer.

The time complexity is O(m times n), where m and n are the number of rows and columns of the board, respectively. In this problem, m = n = 8. The space complexity is O(1).

TypeScript

function numRookCaptures(board: string[][]): number {
    const dirs = [-1, 0, 1, 0, -1];
    const n = board.length;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (board[i][j] === 'R') {
                let ans = 0;
                for (let k = 0; k < 4; k++) {
                    let [x, y] = [i + dirs[k], j + dirs[k + 1]];
                    while (x >= 0 && x < n && y >= 0 && y < n && board[x][y] !== 'B') {
                        if (board[x][y] === 'p') {
                            ans++;
                            break;
                        }
                        x += dirs[k];
                        y += dirs[k + 1];
                    }
                }
                return ans;
            }
        }
    }
    return 0;
}

func numRookCaptures(board [][]byte) (ans int) {
    dirs := []int{-1, 0, 1, 0, -1}
    n := len(board)
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            if board[i][j] == 'R' {
                for k := 0; k < 4; k++ {
                    x, y := i + dirs[k], j + dirs[k+1]
                    for x >= 0 && x < n && y >= 0 && y < n && board[x][y] != 'B' {
                        if board[x][y] == 'p' {
                            ans++
                            break
                        }
                        x += dirs[k]
                        y += dirs[k+1]
                    }
                }
                return
            }
        }
    }
    return
}

Rust

impl Solution {
    pub fn num_rook_captures(board: Vec<Vec<char>>) -> i32 {
        let dirs = [-1, 0, 1, 0, -1];
        let n = board.len();
        for i in 0..n {
            for j in 0..n {
                if board[i][j] == 'R' {
                    let mut ans = 0;
                    for k in 0..4 {
                        let mut x = i as i32 + dirs[k];
                        let mut y = j as i32 + dirs[k + 1];
                        while x >= 0
                            && x < n as i32
                            && y >= 0
                            && y < n as i32
                            && board[x as usize][y as usize] != 'B'
                        {
                            if board[x as usize][y as usize] == 'p' {
                                ans += 1;
                                break;
                            }
                            x += dirs[k];
                            y += dirs[k + 1];
                        }
                    }
                    return ans;
                }
            }
        }
        0
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Direction-Based Iteration	Time Complexity: O(N), since every potential line of the rook must still be verified, approximately 28 to 32 squares. Space Complexity: O(1), only the function's local storage and computational vectors are used.
Multi-Directional Traversal with Early Exit	Time Complexity: O(1) constants in logistical pathing computation replica of integration points. Space Complexity: O(1), employing minimalist path delineation structures.
Simulation	–

Complexity analysis

Approach	Time	Space	When to Use
Direction-Based Iteration	O(n)	O(1)	Standard solution for rook movement simulation on a grid
Multi-Directional Traversal with Early Exit	O(n)	O(1)	Cleaner directional logic using vectors and early stopping

Frequently asked questions

Is Available Captures for Rook easy or hard?

Available Captures for Rook is classified as an Easy problem. The challenge mainly involves correctly simulating rook movement and stopping traversal when a blocking piece appears. Basic matrix traversal knowledge is enough to solve it.

Available Captures for Rook Python/Java solution

Python and Java implementations both follow the same pattern: find the rook position, then iterate in four directions until encountering a pawn or bishop. The logic uses simple loops and condition checks, maintaining O(n) time and O(1) extra space.

How to solve Available Captures for Rook in O(n)?

First scan the matrix to find the rook's coordinates. From that position, iterate outward in four directions using loops or directional vectors. Stop traversal when a bishop appears or count a pawn when encountered. Each direction is explored once, giving an overall O(n) runtime.

What is the best approach for Available Captures for Rook?

Direction-based iteration is the most common solution. After locating the rook, scan in four directions (up, down, left, right) until a bishop blocks the path or a pawn is captured. This simulation approach runs in O(n) time and O(1) space and directly models the rook's chess movement.

Is Available Captures for Rook asked at Google/Amazon/Meta?

Grid traversal and simulation problems like Available Captures for Rook appear in interviews at companies such as Amazon and Google. They test understanding of matrix iteration, boundary checks, and directional traversal patterns.

What data structure is used in Available Captures for Rook?

The problem primarily uses a 2D array (matrix) to represent the chessboard. The algorithm performs directional traversal across rows and columns, making it a classic matrix simulation problem.

What is the time complexity of Available Captures for Rook?

The time complexity is O(n) where n is the board dimension. You scan the board once to locate the rook and then traverse at most 8 cells in each of four directions. Space complexity is O(1) since the algorithm uses only a few variables.

Available Captures for Rook solution and explanation

The problem

Approach overview

Approach 1: Direction-Based Iteration

Approach 2: Multi-Directional Traversal with Early Exit

Approach 3: Simulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Available Captures for Rook solution and explanation

The problem

Approach overview

Approach 1: Direction-Based Iteration

Approach 2: Multi-Directional Traversal with Early Exit

Approach 3: Simulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems