Number Of Valid Move Combinations On Chessboard - Leetcode Solution

Problem Statement:

On an 8 x 8 chessboard, there is one white rook. There also may be empty squares, white bishops, and black pawns. These are given as characters 'R', '.', 'B', and 'p' respectively. Uppercase characters represent white pieces, and lowercase characters represent black pieces.

The rook moves as in the rules of Chess: it chooses one of four cardinal directions (north, east, west, and south), then moves in that direction until it chooses to stop, reaches the edge of the board, or captures an opposite colored pawn by moving to the same square it occupies. Also, rooks cannot move through pieces.

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

Solution:

To solve this problem, we can iterate over the chessboard matrix and find the position of the rook. Once we have found the position of the rook, we can iterate over the row and column of the rook's position to check if there are any pawns that can be captured by the rook.

We can iterate over the row and column of the rook's position separately and check for the presence of any black pawns. The idea is to find the first pawn in the row and column of the rook's position and count it as a valid move. If we find any other pawns after the first one, we can ignore them as they cannot be captured by the rook.

We can implement this solution using the following algorithm:

1. Initialize a variable count to store the number of valid move combinations.
2. Iterate over the rows and columns of the chessboard matrix to find the position of the rook.
3. Once the position of the rook is found, iterate over the row and column of the rook's position separately.
4. For each iteration, find the first black pawn in the row or column and count it as a valid move combination.
5. If no black pawn is found in a row or column, move to the next row or column.
6. Return the final count as the number of valid move combinations.

Let's implement this algorithm in Python:

class Solution: def numRookCaptures(self, board: List[List[str]]) -> int: # initialize variables count = 0 rook_row = rook_col = 0

    # iterate over rows and columns to find rook position
    for i in range(len(board)):
        for j in range(len(board[0])):
            if board[i][j] == 'R':
                rook_row, rook_col = i, j
    
    # iterate over row and column of rook's position
    for i in range(rook_col, len(board[0])):
        if board[rook_row][i] == 'B':
            break
        if board[rook_row][i] == 'p':
            count += 1
            break
    
    for i in range(rook_col, -1, -1):
        if board[rook_row][i] == 'B':
            break
        if board[rook_row][i] == 'p':
            count += 1
            break
    
    for i in range(rook_row, len(board)):
        if board[i][rook_col] == 'B':
            break
        if board[i][rook_col] == 'p':
            count += 1
            break
    
    for i in range(rook_row, -1, -1):
        if board[i][rook_col] == 'B':
            break
        if board[i][rook_col] == 'p':
            count += 1
            break
    
    return count

Time Complexity:

The time complexity of this solution is O(n^2), where n is the size of the chessboard matrix. This is because we need to iterate over the entire matrix to find the position of the rook, and then iterate over the row and column of the rook's position separately to find the number of valid move combinations.

Space Complexity:

The space complexity of this solution is O(1), as we are not using any additional data structures to store the information.

1