999. Available Captures for Rook

EasyArrayMatrixSimulation
Leetcode Link

Problem Description

The problem is set on an 8x8 chessboard with one white rook 'R', several white bishops 'B', black pawns 'p', and empty squares '.'. The rook can move in any of the four cardinal directions - north, east, south, or west. The move of the rook is only stopped by either reaching the board's edge, capturing a black pawn, or being blocked by a white bishop. The task is to calculate the number of black pawns that the rook can capture in its next move. A pawn is considered capturable or "under attack" if the rook can reach it without being obstructed by a bishop or the edge of the board. The desired output is the count of such pawns.

Intuition

To approach the problem efficiently, the solution first identifies the rook's position on the board. Once that's done, the solution needs to check each of the four cardinal directions from the rook's position to see if there's a pawn that can be captured.

This involves moving outward from the rook's position in the given direction, step by step, until hitting the edge of the board, a bishop, or a pawn. When encountering a pawn, it's important to increase the capture count and stop checking that direction as the rook would stop after a capture. Upon encountering a bishop, checking that direction should also stop as the bishop blocks the rook's path. By iterating through each direction, the solution checks all possible captures the rook can make.

The code uses a 'dirs' tuple which contains the changes in coordinates corresponding to the four cardinal directions - up, right, down, and left, given in pairs using the pairwise function. By looping through these direction pairs, the code checks each direction sequentially, applying the direction changes to the rook's position to move along the chessboard.

Solution Approach

The solution is straightforward and involves iterating through the chessboard to identify the rook's position and then, from there, examining all four cardinal directions to check for capturable pawns. Here's the breakdown of the implementation steps:

  1. Iteration to Find the Rook's Position:

    • Start by iterating over each cell of the 8x8 chessboard using a nested loop.
    • Identify the rook's position by checking if the character in the current cell is "R".
  2. Directional Checks for Captures:

    • Once the position of the rook is found, use a directional array dirs = (-1, 0, 1, 0, -1) that represents the possible moves in the north, east, south, and west directions sequentially.
    • The pairwise function (not built-in) is implied to create pairs of directions (dx, dy), obtaining the directions for the rook to check. Normally we would need to create these pairs manually or through iteration.
  3. Loop Through Directions:

    • For each direction pair obtained from dirs, initialize coordinates (x, y) to the rook's position.
    • Move in the current direction until a pawn 'p', bishop 'B', or the edge of the board is encountered.
  4. Edge and Piece Encounters:

    • Use a while loop to repeatedly apply the direction to the coordinates (x, y) until one of the following occurs:
      • The new coordinates are out of bounds (beyond the edges of an 8x8 board).
      • A "B" (bishop) is encountered, which blocks the rook's movement on that path.
      • A "p" (pawn) is encountered, in which case increment the capture count ans and stop checking that path since the pawn will be captured.
  5. Terminating Conditions and Incrementing Capture Count:

    • If the cell under the current direction is a pawn, increment the answer (ans) as a pawn is capturable.
    • If the cell is a bishop, it acts as a blocking piece, and the rook cannot move further in that direction, so break out of the while loop and proceed to the next direction.
  6. Returning the Result:

    • After all four directions are checked, the resulting capture count ans is returned, which is the total number of pawns the rook can capture according to the game rules outlined in the problem description.
Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

In a binary min heap, the minimum element can be found in:

Example Walkthrough

Let's consider a small example to illustrate the solution approach described above. Suppose we have the following 8x8 chessboard layout:

1. . . . . . . .
2. . . p . . . .
3. B . . . . . .
4. . . R . . B .
5. . . p . . . .
6. . . . . . . .
7. . . . . . . .
8. . p . . . . .

Here, the rook R is located at coordinates (3,3), using a 0-based index. We want to determine how many black pawns p the rook can capture in its next move without being obstructed by any white bishops B. Now, let's walk through the solution steps:

  1. Iteration to Find the Rook's Position:

    • We iterate through the board and find the rook at coordinates (3,3).
  2. Directional Checks for Captures:

    • We identify the direction array dirs = (-1, 0, 1, 0, -1) and use the implied pairwise technique to get direction pairs. The direction pairs would be (-1, 0), (0, 1), (1, 0), and (0, -1) representing north, east, south, and west respectively.
  3. Loop Through Directions:

    • We start iterating through these direction pairs applying them one by one.
  4. Edge and Piece Encounters:

    • When going north (up), we encounter the edge of the board. No pawns or bishops block the path, but the rook can't move past the boundary; therefore, no pawns are capturable in this direction.
    • Moving east (right), the first piece the rook encounters is a bishop at (3,7). This blocks any further movement in that direction. No pawns are capturable.
    • Heading south (down), the rook encounters a pawn at (4,3). This pawn is capturable, and the movement in this direction stops with an increment in the capture count.
    • Finally, going west (left), the rook reaches the edge of the board without encountering any pawns or bishops, so no captures can be made.
  5. Terminating Conditions and Incrementing Capture Count:

    • From these explorations, only one pawn at (4,3) is capturable. So we increment the answer ans by 1.
  6. Returning the Result:

    • Having checked all four directions, we conclude that there's only one pawn the rook can capture. So the function returns ans which is 1.

Solution Implementation

1class Solution:
2    def numRookCaptures(self, board: List[List[str]]) -> int:
3        # Initialize the number of captures to 0
4        captures = 0
5        # This tuple represents the four directions: up, right, down, left
6        directions = (-1, 0), (0, 1), (1, 0), (0, -1)
7      
8        # Locate the Rook on the board
9        for i in range(8):
10            for j in range(8):
11                if board[i][j] == "R":
12                    # Search for possible captures in all four directions
13                    for d in directions:
14                        x, y = i, j
15                        # Keep moving in the current direction until hitting a boundary or a piece
16                        while 0 <= x + d[0] < 8 and 0 <= y + d[1] < 8:
17                            x += d[0]
18                            y += d[1]
19                            # If a pawn is encountered, capture it and break out of the loop
20                            if board[x][y] == "p":
21                                captures += 1
22                                break
23                            # If there is a bishop or any other piece, the Rook cannot move past it
24                            if board[x][y] != ".":
25                                break
26        # Return the number of pawns the Rook can capture
27        return captures
28
1class Solution {
2    // This method calculates the number of pawns the rook can capture.
3    public int numRookCaptures(char[][] board) {
4        int captures = 0; // Store the number of captures by the rook
5        // Directions array to help move up, right, down, left (clockwise)
6        // It represents the 4 possible directions for the rook to move.
7        int[] directions = {-1, 0, 1, 0, -1};
8      
9        // Loop through the board to find the rook's position
10        for (int i = 0; i < 8; ++i) {
11            for (int j = 0; j < 8; ++j) {
12                // Check if we found the rook
13                if (board[i][j] == 'R') {
14                    // Check all four directions for captures
15                    for (int k = 0; k < 4; ++k) {
16                        // Start position for the rook
17                        int x = i, y = j;
18                        // x and y direction for the current search
19                        int deltaX = directions[k], deltaY = directions[k + 1];
20                      
21                        // Keep moving in the direction unless a boundary or a bishop is hit
22                        while (x + deltaX >= 0 && x + deltaX < 8 && 
23                               y + deltaY >= 0 && y + deltaY < 8 && 
24                               board[x + deltaX][y + deltaY] != 'B') {
25                            x += deltaX;
26                            y += deltaY;
27                          
28                            // Check if a pawn is captured by the rook
29                            if (board[x][y] == 'p') {
30                                captures++; // Increase the number of captures
31                                break; // Move to next direction after capture
32                            }
33                        }
34                    }
35                    // No need to check the rest of the board after finding the rook
36                    break;
37                }
38            }
39        }
40      
41        return captures; // Return the number of pawns captured
42    }
43}
44
1class Solution {
2public:
3    // Function to calculate the number of pawns that a rook can capture
4    int numRookCaptures(vector<vector<char>>& board) {
5        // Initialize the answer to zero.
6        int numCaptures = 0;
7        // Define the direction vectors for the rook to move: up, right, down, left.
8        int directions[5] = {-1, 0, 1, 0, -1};
9      
10        // Traverse the 8x8 board to find the rook's position.
11        for (int row = 0; row < 8; ++row) {
12            for (int col = 0; col < 8; ++col) {
13                // When the rook is found ('R')...
14                if (board[row][col] == 'R') {
15                    // Check all four directions.
16                    for (int k = 0; k < 4; ++k) {
17                        // Start from the rook's position.
18                        int x = row, y = col;
19                        // Get the current direction's deltas.
20                        int deltaX = directions[k], deltaY = directions[k + 1];
21                        // Move in the current direction until hitting a boundary or a 'B' (bishop).
22                        while (x + deltaX >= 0 && x + deltaX < 8 &&
23                               y + deltaY >= 0 && y + deltaY < 8 &&
24                               board[x + deltaX][y + deltaY] != 'B') {
25                            // Advance to the next cell in the current direction.
26                            x += deltaX;
27                            y += deltaY;
28                            // If a pawn ('p') is encountered, increment the capture count.
29                            if (board[x][y] == 'p') {
30                                ++numCaptures;
31                                // Break out of this loop as a pawn has been captured in this direction.
32                                break;
33                            }
34                        }
35                    }
36                    // Since the rook can only be in one position on the board, 
37                    // we can return the number of captures immediately.
38                    return numCaptures;
39                }
40            }
41        }
42        // Return the number of pawns the rook can capture.
43        return numCaptures;
44    }
45};
46
1// Define the board as a 2D array of characters.
2type Board = char[][];
3
4// Function to calculate the number of pawns that a rook can capture.
5function numRookCaptures(board: Board): number {
6    // Initialize the answer to zero.
7    let numCaptures: number = 0;
8    // Define the direction vectors for the rook to move: up, right, down, left.
9    const directions: number[] = [-1, 0, 1, 0, -1];
10  
11    // Traverse the 8x8 board to find the rook's position.
12    for (let row: number = 0; row < 8; ++row) {
13        for (let col: number = 0; col < 8; ++col) {
14            // When the rook is found ('R')...
15            if (board[row][col] === 'R') {
16                // Check all four directions.
17                for (let k: number = 0; k < 4; ++k) {
18                    // Start from the rook's position.
19                    let x: number = row, y: number = col;
20                    // Get the current direction's deltas.
21                    const deltaX: number = directions[k], deltaY: number = directions[k + 1];
22                    // Move in the current direction until hitting a boundary or a 'B' (bishop).
23                    while (x + deltaX >= 0 && x + deltaX < 8 &&
24                           y + deltaY >= 0 && y + deltaY < 8 &&
25                           board[x + deltaX][y + deltaY] !== 'B') {
26                        // Advance to the next cell in the current direction.
27                        x += deltaX;
28                        y += deltaY;
29                        // If a pawn ('p') is encountered, increment the capture count.
30                        if (board[x][y] === 'p') {
31                            numCaptures++;
32                            // Break out of this loop as a pawn has been captured in this direction.
33                            break;
34                        }
35                    }
36                }
37                // Since the rook can only be in one position on the board, 
38                // return the number of captures immediately.
39                return numCaptures;
40            }
41        }
42    }
43    // Return the number of pawns the rook can capture.
44    return numCaptures;
45}
46

Time and Space Complexity

Time Complexity

The time complexity for this code is O(n^2), where n is the dimension of the chessboard; since the board is 8x8, the time complexity can also be considered O(1) as the size of the board is constant and does not scale with input size. The algorithm goes through every cell of the chessboard in the worst case (8*8 iterations), and in each cell where the rook is found, it iterates in four directions until it encounters a bishop, pawn, or the edge of the board. The maximum distance the inner while-loop can cover in any direction is 7 cells meaning O(n). But, since n=8 is a constant, iterating through the entire direction in a fixed-size board doesn't depend on input size and thus contributes a constant factor.

Space Complexity

The space complexity of the code is O(1) because the space used does not scale with the size of the input; the dirs tuple and the few variables used for iteration are all that is needed. The space requirements remain constant regardless of the size of the board or configuration of pieces on the chessboard.

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

Which technique can we use to find the middle of a linked list?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄