Available Captures for Rook
Easy
3 views
Topics:
Arrays
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.
For example:
board = [
[".",".",".",".",".",".",".","."],
[".",".",".","p",".",".",".","."],
[".",".",".","R",".",".",".","p"],
[".",".",".",".",".",".",".","."],
[".",".",".",".",".",".",".","."],
[".",".",".","p",".",".",".","."],
[".",".",".",".",".",".",".","."],
[".",".",".",".",".",".",".","."]
]
In this example, the rook is attacking all the pawns, so the correct output is 3.
As another example:
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",".","."],
[".",".",".",".",".",".",".","."],
[".",".",".",".",".",".",".","."]
]
In this case, the correct output is 0 because the bishops are blocking the rook from attacking any of the pawns.
Write a function to solve this problem.
Solution
Clarifying Questions
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
- What are the dimensions of the board (the number of rows and columns)? Is it always an 8x8 board?
- What characters, besides the rook ('R'), can appear on the board? Are they limited to pawns ('p'), empty squares ('.'), and potentially the Bishop ('B') as an obstacle?
- If a pawn is 'captured', does that mean we should count it? Or, is the goal to identify all squares reachable by the rook without encountering an obstacle, even if those squares do not contain pawns?
- Can the rook be located at any position on the board, or is it guaranteed to be placed at a valid position at the beginning of the game?
- If there are multiple pawns that the rook can capture in the same direction before encountering an obstacle, should I only count the first one?
Brute Force Solution
Approach
Imagine the rook is on a chessboard, and we want to see how many pawns it can capture. We'll check every possible direction the rook can move and stop when it hits a friendly piece, an enemy pawn (which it can capture), or the edge of the board.
Here's how the algorithm would work step-by-step:
- Start at the rook's current position.
- Look to the right: Check each square one by one in that direction.
- If you find a pawn, count it as captured and stop looking in that direction.
- If you find another rook, stop looking in that direction (can't capture friendly pieces).
- If you reach the edge of the board, stop looking in that direction.
- Do the same thing to the left: Check each square one by one.
- Again, stop when you find a pawn, another rook, or the edge of the board.
- Now do the same thing upwards: Check each square one by one.
- Again, stop when you find a pawn, another rook, or the edge of the board.
- Finally, do the same thing downwards: Check each square one by one.
- Again, stop when you find a pawn, another rook, or the edge of the board.
- Add up the number of pawns you found in all four directions. That's the total number of captures the rook can make.
Code Implementation
def available_captures(board): rook_row, rook_col = -1, -1
for row in range(8):
for col in range(8):
if board[row][col] == 'R':
rook_row, rook_col = row, col
break
if rook_row != -1:
break
captures = 0
# Check right
for col in range(rook_col + 1, 8):
if board[rook_row][col] == 'p':
captures += 1
# Stop looking once a pawn is found
break
elif board[rook_row][col] != '.':
# Stop if another piece is encountered
break
# Check left
for col in range(rook_col - 1, -1, -1):
if board[rook_row][col] == 'p':
captures += 1
# Stop looking once a pawn is found
break
elif board[rook_row][col] != '.':
# Stop if another piece is encountered
break
# Check up
for row in range(rook_row - 1, -1, -1):
if board[row][rook_col] == 'p':
captures += 1
# Stop looking once a pawn is found
break
elif board[row][rook_col] != '.':
# Stop if another piece is encountered
break
# Check down
for row in range(rook_row + 1, 8):
if board[row][rook_col] == 'p':
captures += 1
# Stop looking once a pawn is found
break
elif board[row][rook_col] != '.':
# Stop if another piece is encountered
break
return capturesBig(O) Analysis
Time Complexity
O(1) – The algorithm examines a maximum of 4 * 8 = 32 cells on the chessboard, as it explores at most 8 cells in each of the four cardinal directions (up, down, left, right) from the rook's position. Since the chessboard size is fixed (8x8), the number of operations is bounded by a constant. Therefore, the time complexity is O(1).
Space Complexity
O(1) – The algorithm described in the plain English explanation only uses a few integer variables to track the rook's current position and count the captured pawns. It doesn't create any auxiliary data structures like arrays, lists, or hashmaps to store intermediate results or visited locations. Therefore, the amount of extra memory used is constant and independent of the chessboard size (N, where N is the number of squares on the board). Consequently, the space complexity is O(1).
Optimal Solution
Approach
The problem asks to find how many pawns a rook can capture on a chessboard. The optimal solution involves checking in all four directions from the rook until you hit an obstacle (another piece) or the edge of the board.
Here's how the algorithm would work step-by-step:
- Find the location of the rook on the board.
- Look to the left of the rook, one square at a time.
- If you see a pawn, count it as a capture and stop looking in that direction.
- If you see another rook or a block, stop looking in that direction.
- Repeat this process, but this time look to the right of the rook.
- Repeat the same process looking above the rook.
- Repeat the same process looking below the rook.
- Add up all the pawns that the rook can capture. This is your final result.
Code Implementation
def numRookCaptures(board): 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
# Check left
for col in range(rook_col - 1, -1, -1):
if board[rook_row][col] == 'p':
# Stop after first pawn
captures += 1
break
elif board[rook_row][col] != '.':
# Stop after other piece
break
# Check right
for col in range(rook_col + 1, 8):
if board[rook_row][col] == 'p':
# Stop after first pawn
captures += 1
break
elif board[rook_row][col] != '.':
# Stop after other piece
break
# Check up
for row in range(rook_row - 1, -1, -1):
if board[row][rook_col] == 'p':
# Stop after first pawn
captures += 1
break
elif board[row][rook_col] != '.':
# Stop after other piece
break
# Check down
for row in range(rook_row + 1, 8):
if board[row][rook_col] == 'p':
# Stop after first pawn
captures += 1
break
elif board[row][rook_col] != '.':
# Stop after other piece
break
return capturesBig(O) Analysis
Time Complexity
O(1) – The chessboard is always 8x8, so the input size is constant. Finding the rook takes constant time. Checking each direction from the rook involves iterating at most 7 times in each of the four directions (left, right, up, down) until an obstacle or the edge of the board is reached. Therefore, the maximum number of operations is bounded by a constant (4 * 7 = 28), regardless of the specific arrangement of pieces. This results in O(1) time complexity.
Space Complexity
O(1) – The algorithm finds the rook's location and then checks in four directions. It uses a fixed number of variables (e.g., row, col, counters for each direction) to track the current position and whether a pawn has been captured in each direction. No auxiliary data structures like lists or hash maps are created. Therefore, the space used is constant regardless of the board size (N), resulting in O(1) space complexity.
Edge Cases
| Case | How to Handle |
|---|---|
| Null or invalid board input | Throw an IllegalArgumentException or return 0 if the board is null or not an 8x8 array, to ensure program stability. |
| Rook is placed on the edge of the board | The solution must handle cases where the rook's movement is constrained by the board edges without causing out-of-bounds errors. |
| The board is completely empty (no pieces other than the rook) | The solution should return 0 because the rook cannot capture anything if there are no pawns. |
| The board is completely full of enemy pawns with no friendly pieces between rook and pawns | The solution should count all pawns visible from the rook as capturable, not exceeding the maximum count of 4. |
| Multiple pawns and blocking pieces exist in the same row/column | The algorithm should only count the first capturable pawn in each direction, stopping when it encounters a friendly piece or the board edge. |
| Rook is surrounded by friendly pieces preventing any captures | The solution should return 0 as no captures are possible when the rook is blocked in all directions. |
| Board contains invalid characters besides 'R', 'p', 'B', and '.' | The code should either ignore invalid characters or throw an exception to indicate malformed board input. |
| Integer overflow on extremely large board sizes (though the problem constrains to 8x8) | Since board size is fixed, integer overflow is not possible; if input size scaled, integer types must be validated or use bigger types. |
Explore Interview QuestionsGoogle Interview QuestionsMeta Interview QuestionsAmazon Interview QuestionsApple Interview QuestionsNetflix Interview Questions
Explore Jobs By LevelEntry-Level Software Engineer JobsMid-Level Software Engineer JobsSenior Software Engineer JobsStaff Software Engineer Jobs
