Is Available Captures for Rook easy or hard?

Available Captures for Rook is classified as an Easy problem. The challenge mainly involves correctly simulating rook movement and stopping traversal when a blocking piece appears. Basic matrix traversal knowledge is enough to solve it.

Available Captures for Rook Python/Java solution

Python and Java implementations both follow the same pattern: find the rook position, then iterate in four directions until encountering a pawn or bishop. The logic uses simple loops and condition checks, maintaining O(n) time and O(1) extra space.

How to solve Available Captures for Rook in O(n)?

First scan the matrix to find the rook's coordinates. From that position, iterate outward in four directions using loops or directional vectors. Stop traversal when a bishop appears or count a pawn when encountered. Each direction is explored once, giving an overall O(n) runtime.

What is the best approach for Available Captures for Rook?

Direction-based iteration is the most common solution. After locating the rook, scan in four directions (up, down, left, right) until a bishop blocks the path or a pawn is captured. This simulation approach runs in O(n) time and O(1) space and directly models the rook's chess movement.

Is Available Captures for Rook asked at Google/Amazon/Meta?

Grid traversal and simulation problems like Available Captures for Rook appear in interviews at companies such as Amazon and Google. They test understanding of matrix iteration, boundary checks, and directional traversal patterns.

What data structure is used in Available Captures for Rook?

The problem primarily uses a 2D array (matrix) to represent the chessboard. The algorithm performs directional traversal across rows and columns, making it a classic matrix simulation problem.

What is the time complexity of Available Captures for Rook?

The time complexity is O(n) where n is the board dimension. You scan the board once to locate the rook and then traverse at most 8 cells in each of four directions. Space complexity is O(1) since the algorithm uses only a few variables.

Description Solution Video 5:12

999. Available Captures for Rook

Easy72.2% acceptance2 companies

You are given an 8 x 8 matrix representing a chessboard. There is exactly one white rook represented by 'R', some number of white bishops 'B', and some number of black pawns 'p'. Empty squares are represented by '.'.

A rook can move any number of squares horizontally or vertically (up, down, left, right) until it reaches another piece or the edge of the board. A rook is attacking a pawn if it can move to the pawn's square in one move.

Note: A rook cannot move through other pieces, such as bishops or pawns. This means a rook cannot attack a pawn if there is another piece blocking the path.

Return the number of pawns the white rook is attacking.

Example 1:

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

Output: 3

Explanation:

In this example, the rook is attacking all the pawns.

Example 2:

Input: board = [[".",".",".",".",".",".","."],[".","p","p","p","p","p",".","."],[".","p","p","B","p","p",".","."],[".","p","B","R","B","p",".","."],[".","p","p","B","p","p",".","."],[".","p","p","p","p","p",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]

Output: 0

Explanation:

The bishops are blocking the rook from attacking any of the pawns.

Example 3:

Input: board = [[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","p",".",".",".","."],["p","p",".","R",".","p","B","."],[".",".",".",".",".",".",".","."],[".",".",".","B",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."]]

Output: 3

Explanation:

The rook is attacking the pawns at positions b5, d6, and f5.

Constraints:

board.length == 8
board[i].length == 8
board[i][j] is either 'R', '.', 'B', or 'p'
There is exactly one cell with board[i][j] == 'R'

Asked at 2 companies

Square

Google

Topics

5:12

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

Similar problems

Count Unguarded Cells in the GridMedium Minimum Moves to Capture The QueenMedium Maximum Value Sum by Placing Three Rooks IIHard Maximum Value Sum by Placing Three Rooks IHard

LanguageLoading editor…

1class Solution:
2    def numRookCaptures(self, board: List[List[str]]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","R",".",".",".","p"],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]

Input

[[".",".",".",".",".",".",".","."],[".","p","p","p","p","p",".","."],[".","p","p","B","p","p",".","."],[".","p","B","R","B","p",".","."],[".","p","p","B","p","p",".","."],[".","p","p","p","p","p",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]

Input

[[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","p",".",".",".","."],["p","p",".","R",".","p","B","."],[".",".",".",".",".",".",".","."],[".",".",".","B",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."]]

Your code is saved on this device.Solution