algoadvance

Leetcode 999. Available Captures for Rook

Problem Statement

Given a chessboard represented as an 8×8 matrix called board where:

The White Rook (‘R’) is the only Rook on the board. It can move horizontally or vertically through any number of empty squares until it finds a pawn (‘p’) or is blocked by a bishop (‘B’). It captures the pawn if possible. The task is to count the number of pawns the Rook can capture in one move.

Example:

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

Clarifying Questions

  1. Are there any other pieces on the board apart from the ones mentioned in the problem statement?
    • No, only empty squares, one white rook, black pawns, and black bishops are present.
  2. Can we assume there’s exactly one Rook on the board?
    • Yes, there is exactly one White Rook.

Strategy

  1. Locate the position of the Rook R in the given board.
  2. Once the Rook’s location is found, we check in the four possible directions (left, right, up, and down):
    • For each direction, move step by step until a pawn p or a bishop B is encountered or the edge of the board is reached.
    • If a pawn p is encountered, increment the capture count.
  3. Sum up the captures from all four directions to get the final result.

Code

#include <vector>

using namespace std;

class Solution {
public:
    int numRookCaptures(vector<vector<char>>& board) {
        int n = 8;
        int rookRow = -1, rookCol = -1;

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

        int captures = 0;

        // Check all four directions
        // Move Up
        for (int row = rookRow - 1; row >= 0; --row) {
            if (board[row][rookCol] == 'B') break;
            if (board[row][rookCol] == 'p') {
                captures++;
                break;
            }
        }

        // Move Down
        for (int row = rookRow + 1; row < n; ++row) {
            if (board[row][rookCol] == 'B') break;
            if (board[row][rookCol] == 'p') {
                captures++;
                break;
            }
        }
        
        // Move Left
        for (int col = rookCol - 1; col >= 0; --col) {
            if (board[rookRow][col] == 'B') break;
            if (board[rookRow][col] == 'p') {
                captures++;
                break;
            }
        }

        // Move Right
        for (int col = rookCol + 1; col < n; ++col) {
            if (board[rookRow][col] == 'B') break;
            if (board[rookRow][col] == 'p') {
                captures++;
                break;
            }
        }

        return captures;
    }
};

Time Complexity

The time complexity for this solution is O(n), where n is the size of the board (which is 8x8). We are first scanning the board to identify the position of the Rook, which is an O(n^2) operation, but since n is constant (8), this can be considered O(1). For each direction, the checking involves at most 7 steps, which is also constant. Therefore, the time complexity is dominated by O(n), here equivalent to a fixed maximal number of operations.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI