algoadvance

Leetcode 999. Available Captures for Rook

Problem Statement

You are given an 8x8 chessboard represented as a 2D character array board.

• The character ‘R’ represents a white rook.
• The character ‘B’ represents a black bishop.
• The character ‘p’ represents a black pawn.
• The character ‘.’ represents an empty square.

The white rook can move along the row or column, and it can attack (capture) the black pawns.

However, it cannot pass through black bishops. The rook’s maximum block distance is thus limited by any bishops along the same row or column.

Return the number of pawns the rook can capture in one move.

Clarifying Questions

1. Can there be multiple rooks on the board?
   • No, there is only one rook (‘R’) on the board.
2. Do we need to check diagonally?
   • No, just horizontally and vertically.
3. Can there be other pieces on the board apart from ‘R’, ‘B’, ‘p’, and ‘.’?
   • No, only ‘R’, ‘B’, ‘p’, and ‘.’ are present on the board.

Strategy

1. Find the Rook: First, locate the position of the rook ‘R’.
2. Scan in Four Directions: Scan in all four directions (up, down, left, right) to find pawns ‘p’ that can be captured:
   • Stop scanning in a direction if you encounter a bishop ‘B’ or the edge of the board.
   • Count the number of pawns encountered before hitting a bishop or the edge of the board.

Code

public class Solution {
    public int numRookCaptures(char[][] board) {
        int rookRow = -1, rookCol = -1;

        // Step 1: Find the position of the Rook
        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;
                }
            }
        }

        int captures = 0;

        // Step 2: Check in all four directions from the Rook's position

        // Check upward
        for (int i = rookRow - 1; i >= 0; i--) {
            if (board[i][rookCol] == 'B') break;
            if (board[i][rookCol] == 'p') {
                captures++;
                break;
            }
        }

        // Check downward
        for (int i = rookRow + 1; i < 8; i++) {
            if (board[i][rookCol] == 'B') break;
            if (board[i][rookCol] == 'p') {
                captures++;
                break;
            }
        }

        // Check leftward
        for (int j = rookCol - 1; j >= 0; j--) {
            if (board[rookRow][j] == 'B') break;
            if (board[rookRow][j] == 'p') {
                captures++;
                break;
            }
        }

        // Check rightward
        for (int j = rookCol + 1; j < 8; j++) {
            if (board[rookRow][j] == 'B') break;
            if (board[rookRow][j] == 'p') {
                captures++;
                break;
            }
        }

        return captures;
    }
}

Time Complexity

• Finding the rook: O(1), as the board size is fixed at 8x8.
• Checking in each of the four directions: O(1), limited to a maximum of 8 checks in each direction.

Overall, the time complexity is O(1), making the solution very efficient due to the constant board size.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?