Available Captures for Rook
EasyPrompt
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 == 8board[i].length == 8board[i][j]is either'R','.','B', or'p'- There is exactly one cell with
board[i][j] == 'R'
Approaches
2 approaches with complexity analysis and trade-offs.
This approach first identifies the locations of the rook and all pawns. It then iterates through each pawn, checking if it's on the same row or column as the rook and if the path between them is unobstructed. This method is less efficient due to redundant checks and higher memory usage.
Algorithm
- Iterate through the
8x8board to find the coordinates of the rook(rookRow, rookCol)and to build a list of all pawn coordinates. - Initialize a
capturescount to 0. - Iterate through the list of pawn coordinates.
- For each pawn at
(pRow, pCol):- If
pRow == rookRow, check the horizontal path between the pawn and the rook. If no other pieces are found, incrementcaptures. - If
pCol == rookCol, check the vertical path between the pawn and the rook. If no other pieces are found, incrementcaptures.
- If
- Return the final
capturescount.
Walkthrough
The core idea is to check, for every pawn, whether it is vulnerable to capture by the rook. The algorithm proceeds in two main phases:
-
Piece Location: The entire 8x8 board is scanned to find the coordinates of the white rook ('R') and to build a list containing the coordinates of every black pawn ('p').
-
Capture Verification: The algorithm then iterates through the list of pawns. For each pawn, it checks two conditions:
- Is the pawn on the same row or column as the rook?
- If so, is the path between the rook and the pawn clear of any other pieces (bishops or other pawns)?
To check the path, a loop iterates over the squares between the rook and the pawn. If any of these squares is not empty ('.'), the path is blocked, and the pawn cannot be captured. If the path is clear, a capture counter is incremented. This process is repeated for all pawns.
import java.util.ArrayList;import java.util.List; class Solution { public int numRookCaptures(char[][] board) { int rookRow = -1, rookCol = -1; List<int[]> pawnPositions = new ArrayList<>(); // Phase 1: Find Rook and all Pawns for (int i = 0; i < 8; i++) { for (int j = 0; j < 8; j++) { if (board[i][j] == 'R') { rookRow = i; rookCol = j; } else if (board[i][j] == 'p') { pawnPositions.add(new int[]{i, j}); } } } int captures = 0; // Phase 2: For each pawn, check if it's capturable for (int[] pawnPos : pawnPositions) { int pRow = pawnPos[0]; int pCol = pawnPos[1]; if (pRow == rookRow) { // Same row boolean pathClear = true; int startCol = Math.min(pCol, rookCol) + 1; int endCol = Math.max(pCol, rookCol); for (int c = startCol; c < endCol; c++) { if (board[rookRow][c] != '.') { pathClear = false; break; } } if (pathClear) { captures++; } } else if (pCol == rookCol) { // Same column boolean pathClear = true; int startRow = Math.min(pRow, rookRow) + 1; int endRow = Math.max(pRow, rookRow); for (int r = startRow; r < endRow; r++) { if (board[r][rookCol] != '.') { pathClear = false; break; } } if (pathClear) { captures++; } } } return captures; }}Complexity
Time
O(N^2 + k*N), where N is the board dimension (8) and k is the number of pawns. The initial scan is O(N^2). Then, for each of the `k` pawns, we might scan up to N cells to check the path. For a fixed 8x8 board, this is constant time, but it's computationally heavier than the optimal approach.
Space
O(k), where `k` is the number of pawns. We need to store the coordinates of all pawns. In the worst case, this could be O(N^2) if most of the board is filled with pawns.
Trade-offs
Pros
Separates the logic of finding pieces from checking captures, which can be clear for some developers.
Cons
Inefficient due to repeated scanning of rows/columns.
Requires extra space to store pawn locations.
More complex logic for checking paths between two points.
This optimal approach first locates the rook and then simulates its movement in the four cardinal directions (up, down, left, right). It scans outwards from the rook's position, stopping in a given direction as soon as any piece is encountered. If the piece is a pawn, it's counted as a capture. This avoids redundant checks and uses minimal memory.
Algorithm
- Iterate through the
8x8board to find the coordinates of the rook(rookRow, rookCol). - Initialize a
capturescount to 0. - Define the four cardinal directions (e.g., using an array of coordinate changes like
{{-1,0}, {1,0}, {0,-1}, {0,1}}). - For each of the four directions:
- Start from the square adjacent to the rook and move one step at a time in the current direction.
- Continue moving until you go off the board or encounter another piece.
- If the first piece encountered is a pawn 'p', increment
captures. - After finding any piece (pawn or bishop), stop searching in that direction and move to the next one.
- Return the final
capturescount.
Walkthrough
This algorithm directly simulates the rook's behavior on a chessboard, making it highly intuitive and efficient.
-
Find the Rook: The first step is a single pass over the board to find the
(row, col)coordinates of the rook, 'R'. The loops can be terminated as soon as the rook is found. -
Scan in Four Directions: Once the rook is located, the algorithm checks for captures along the four cardinal directions. This can be elegantly handled using a directions array (e.g.,
{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}for up, down, left, right). For each direction:- A loop starts from the rook's position and moves one step at a time in the current direction.
- The loop continues as long as it stays within the board's boundaries.
- At each square, the piece is checked. If it's a pawn 'p', the capture count is incremented, and the loop for this direction terminates (since the path is now blocked).
- If it's a bishop 'B', the loop for this direction also terminates, but no capture is counted.
- If the square is empty '.', the loop continues to the next square in the same direction.
This method ensures that each of the four paths from the rook is traversed only once, making it the most efficient solution.
class Solution { public int numRookCaptures(char[][] board) { int rookRow = 0, rookCol = 0; // 1. Find the Rook for (int i = 0; i < 8; ++i) { for (int j = 0; j < 8; ++j) { if (board[i][j] == 'R') { rookRow = i; rookCol = j; break; } } } int captures = 0; int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // Up, Down, Left, Right // 2. Scan in four directions for (int[] d : directions) { int r = rookRow + d[0]; int c = rookCol + d[1]; while (r >= 0 && r < 8 && c >= 0 && c < 8) { if (board[r][c] == 'p') { captures++; break; // Stop searching in this direction } if (board[r][c] == 'B') { break; // Stop searching in this direction } r += d[0]; c += d[1]; } } return captures; }}Complexity
Time
O(N^2), where N is the board dimension (8). The search for the rook takes O(N^2) in the worst case. The subsequent search in four directions takes at most O(4*N) steps. The total complexity is dominated by the initial search. For a fixed 8x8 board, this is constant time, O(1).
Space
O(1). The algorithm uses only a few variables to store the rook's position, the capture count, and loop counters, regardless of the board's content.
Trade-offs
Pros
Optimal time complexity as it avoids redundant checks.
Minimal space usage (O(1)).
The logic is clean and directly simulates the rook's movement.
Cons
No significant disadvantages for this problem; it is the standard and most efficient solution.
Solutions
Solution
class Solution {public int numRookCaptures(char[][] board) { int ans = 0; int[] dirs = {-1, 0, 1, 0, -1}; for (int i = 0; i < 8; ++i) { for (int j = 0; j < 8; ++j) { if (board[i][j] == 'R') { for (int k = 0; k < 4; ++k) { int x = i, y = j; int a = dirs[k], b = dirs[k + 1]; while (x + a >= 0 && x + a < 8 && y + b >= 0 && y + b < 8 && board[x + a][y + b] != 'B') { x += a; y += b; if (board[x][y] == 'p') { ++ans; break; } } } } } } return ans; }}class Solution {public: int numRookCaptures(vector<vector<char>> &board) { int ans = 0; int dirs[5] = {-1, 0, 1, 0, -1}; for (int i = 0; i < 8; ++i) { for (int j = 0; j < 8; ++j) { if (board[i][j] == 'R') { for (int k = 0; k < 4; ++k) { int x = i, y = j; int a = dirs[k], b = dirs[k + 1]; while (x + a >= 0 && x + a < 8 && y + b >= 0 && y + b < 8 && board[x + a][y + b] != 'B') { x += a; y += b; if (board[x][y] == 'p') { ++ans; break; } } } } } } return ans; }};class Solution: def numRookCaptures(self, board: List[List[str]]) -> int: ans = 0 dirs = (- 1, 0, 1, 0, - 1) for i in range(8): for j in range(8): if board[i][j] == "R": for a, b in pairwise(dirs): x, y = i, j while 0 <= x + a < 8 and 0 <= y + b < 8: x, y = x + a, y + b if board[x][y] == "p": ans += 1 break if board[x][y] == "B": break return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.