How do you solve Available Captures for Rook on LeetCode?

Available Captures for Rook (LeetCode #999) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Rooks attack in straight lines until blocked.

What is the brute force solution for Available Captures for Rook?

The brute force approach for Available Captures for Rook is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves checking each direction from the rook's position until we hit a piece or the edge of the board. We count how many pawns we can attack in total by moving in all four directions. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Available Captures for Rook?

Available Captures for Rook uses the following concepts: Array, Matrix, Simulation. The recommended patterns to study are: Simulation, Grid Traversal.

What are the interview tips for Available Captures for Rook?

Clarify the board's layout and piece positions. Discuss edge cases, like no pawns or all pieces blocking the rook.

What are common mistakes when solving Available Captures for Rook?

Not stopping when hitting a bishop. Confusing rook's movement with other pieces.

#999

Available Captures for Rook

Easy

ArrayMatrixSimulationSimulationGrid Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal solution is similar to the brute force but focuses on stopping immediately when we encounter a piece, making it more efficient. We can also use a single loop to check each direction without needing to iterate through the entire board.

⚙️

Algorithm

3 steps

1Step 1: Locate the rook's position on the board.
2Step 2: For each of the four directions, check until a piece is encountered.
3Step 3: If a pawn is found, increment the counter; if a bishop is found, stop checking in that direction.

solution.py20 lines

1def numRookCaptures(board):
2    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
3    count = 0
4    for i in range(8):
5        for j in range(8):
6            if board[i][j] == 'R':
7                rook_x, rook_y = i, j
8                break
9    for dx, dy in directions:
10        x, y = rook_x, rook_y
11        while 0 <= x < 8 and 0 <= y < 8:
12            x += dx
13            y += dy
14            if 0 <= x < 8 and 0 <= y < 8:
15                if board[x][y] == 'p':
16                    count += 1
17                    break
18                elif board[x][y] == 'B':
19                    break
20    return count

ℹ

Complexity note: The optimal solution runs in O(n) because we only traverse the board in the four directions from the rook's position, stopping early when we hit a piece.

1Rooks attack in straight lines until blocked.
2Only pawns can be captured; bishops block the path.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.