Queens That Can Attack the King

Medium

Asked by:

24 views

Topics:

Arrays

On a 0-indexed 8 x 8 chessboard, there can be multiple black queens and one white king.

You are given a 2D integer array queens where queens[i] = [xQueen_i, yQueen_i] represents the position of the i^th black queen on the chessboard. You are also given an integer array king of length 2 where king = [xKing, yKing] represents the position of the white king.

Return the coordinates of the black queens that can directly attack the king. You may return the answer in any order.

Example 1:

Input: queens = [[0,1],[1,0],[4,0],[0,4],[3,3],[2,4]], king = [0,0]
Output: [[0,1],[1,0],[3,3]]
Explanation: The diagram above shows the three queens that can directly attack the king and the three queens that cannot attack the king (i.e., marked with red dashes).

Example 2:

Input: queens = [[0,0],[1,1],[2,2],[3,4],[3,5],[4,4],[4,5]], king = [3,3]
Output: [[2,2],[3,4],[4,4]]
Explanation: The diagram above shows the three queens that can directly attack the king and the three queens that cannot attack the king (i.e., marked with red dashes).

Constraints:

1 <= queens.length < 64
queens[i].length == king.length == 2
0 <= xQueen_i, yQueen_i, xKing, yKing < 8
All the given positions are unique.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the data types and ranges for the coordinates of the queens and the king? Are they always integers within the bounds of the 8x8 chessboard (0-7)?
If no queens can attack the king, should I return an empty list or null?
If multiple queens can attack the king along the same line of sight (row, column, or diagonal), should I return all of them, or only the closest one to the king?
Are the positions of the queens guaranteed to be unique? Can the king and a queen occupy the same position?
Is the order of the queens in the output list significant? If so, is there a specific order I should follow (e.g., by distance to the king)?

Brute Force Solution

Approach

We need to find all the queens that can attack the king on a chessboard. The brute force approach simply checks every queen to see if it can attack the king, without any shortcuts.

Here's how the algorithm would work step-by-step:

Look at the location of the king on the chessboard.
For each queen on the board, consider it individually.
Check if that queen is in the same row as the king. If it is, check if there are any other pieces between the queen and the king in that row. If not, this queen can attack.
Check if that queen is in the same column as the king. If it is, check if there are any other pieces between the queen and the king in that column. If not, this queen can attack.
Check if that queen is on the same diagonal as the king. There are two diagonals to check: one going top-left to bottom-right and another going top-right to bottom-left. For each diagonal, check if there are any other pieces between the queen and the king. If not, this queen can attack.
If the queen can attack the king based on the checks above, we mark that queen as an attacker.
Repeat steps 2-6 for every queen on the board.
After checking all queens, list all the queens that we marked as attackers.

Code Implementation

def queens_that_can_attack_the_king(queens, king):
    attacking_queens = []
    king_row = king[0]
    king_column = king[1]

    for queen in queens:
        queen_row = queen[0]
        queen_column = queen[1]

        # Check if the queen is in the same row as the king
        if queen_row == king_row:
            attacking_queens.append(queen)
            continue

        # Check if the queen is in the same column as the king
        if queen_column == king_column:
            attacking_queens.append(queen)
            continue

        # Check if the queen is on the same diagonal as the king
        if abs(queen_row - king_row) == abs(queen_column - king_column):
            attacking_queens.append(queen)

    return attacking_queens

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through each queen in the 'queens' list. For each queen, it performs a constant amount of work to check if it can attack the king in each direction (row, column, two diagonals). The number of queens 'n' directly impacts the runtime. Therefore, the time complexity is O(n), where n is the number of queens.

Space Complexity

O(1) – The algorithm iterates through the queens and checks each one individually. It uses a few boolean variables (or similar) to track whether a queen can attack and potentially a list to store the attacking queens. However, the number of boolean variables and the size of the attacking queens list are bounded by the number of queens, which is determined by the chessboard size (maximum 64 in a standard chessboard, typically much smaller in interview problems). Therefore, the auxiliary space used does not grow with the input size (N where N is the number of queens or the chessboard size) and remains constant.

Optimal Solution

Approach

The most efficient way to solve this puzzle is to check along the eight possible directions from the king until we find a queen. We stop searching in a direction once a queen is found because any further pieces in that direction are irrelevant.

Here's how the algorithm would work step-by-step:

Imagine the king is at the center of a compass rose with eight directions: North, Northeast, East, Southeast, South, Southwest, West, and Northwest.
For each of these eight directions, look at the locations immediately next to the king. If there's a queen, remember it and move on to the next direction.
If a location isn't a queen, keep moving further along in that direction, checking each location one at a time until one of the following things happen:
If you find a queen, remember that queen.
If you reach the edge of the board without finding a queen, then there's no queen attacking in that direction.
Once you've checked all eight directions, report the queens that you remembered.
This method avoids checking every possible location on the board and only looks in the lines of sight from the king, making it much faster.

Code Implementation

def queens_that_can_attack_the_king(queens, king):
    attacking_queens = []
    king_row, king_col = king

    # Define the 8 directions to check
    directions = [
        (-1, 0),  # Up
        (1, 0),   # Down
        (0, -1),  # Left
        (0, 1),   # Right
        (-1, -1), # Top-Left
        (-1, 1),  # Top-Right
        (1, -1),  # Bottom-Left
        (1, 1)    # Bottom-Right
    ]

    for row_direction, col_direction in directions:
        closest_queen = None
        min_distance = float('inf')

        # Iterate through each queen to find the closest one in current direction
        for queen_row, queen_col in queens:
            if row_direction == 0 and queen_row != king_row:
                continue
            if col_direction == 0 and queen_col != king_col:
                continue
            if row_direction != 0 and col_direction != 0 and (queen_row - king_row) * col_direction != (queen_col - king_col) * row_direction:
                continue

            row_distance = queen_row - king_row
            col_distance = queen_col - king_col

            # Ensure the queen is in the correct direction
            if row_direction != 0 and row_distance * row_direction <= 0:
                continue
            if col_direction != 0 and col_distance * col_direction <= 0:
                continue

            distance = abs(row_distance) + abs(col_distance)

            # Check if this queen is closer than the current closest
            if distance < min_distance:
                min_distance = distance
                closest_queen = (queen_row, queen_col)

        # If a closest queen was found, add it to the result
        if closest_queen:
            attacking_queens.append(closest_queen)

    return attacking_queens

# Finds the queens closest to the king in each of the 8 directions.

Big(O) Analysis

Time Complexity

O(1) – The algorithm iterates at most 8 times, one for each direction (North, Northeast, East, Southeast, South, Southwest, West, and Northwest). In each direction, the maximum number of cells checked is bounded by the size of the board (8x8), so the number of checks is constant. Because the number of operations is constant regardless of the number of queens, the Big O time complexity is O(1).

Space Complexity

O(1) – The algorithm primarily uses a constant amount of extra space. It stores a fixed number of variables, such as the current position being checked in each direction and potentially a variable to remember a queen. No auxiliary data structures, like lists or hash maps that scale with the input size N (where N represents the number of queens), are used to store intermediate results or track visited locations. The space used does not depend on the number of queens or the board size, so the auxiliary space complexity is constant.

Edge Cases

Case	How to Handle
Null or empty queens list	Return an empty list immediately, as no queens can attack.
Null king position	Throw an IllegalArgumentException or return an empty list, as a valid king position is required.
King and queen at the same position	The queen can attack, so it should be included in the result.
Multiple queens on the same line of sight to the king	Only the closest queen to the king on each line of sight should be considered as attacking.
Queen positions outside the chessboard boundaries (0-7)	Ignore any queen with invalid coordinates (outside the 0-7 range) or throw an IllegalArgumentException.
King position outside the chessboard boundaries (0-7)	Throw an IllegalArgumentException as the king must be within the board.
Large number of queens; assess time complexity.	The solution should have a time complexity of O(N) where N is the number of queens to avoid timeouts with large input.
No queens can attack the king	The algorithm should correctly return an empty list in this scenario.

Null or empty queens list

How to Handle:

Return an empty list immediately, as no queens can attack.

Null king position

How to Handle:

Throw an IllegalArgumentException or return an empty list, as a valid king position is required.

King and queen at the same position

How to Handle:

The queen can attack, so it should be included in the result.

Multiple queens on the same line of sight to the king

How to Handle:

Only the closest queen to the king on each line of sight should be considered as attacking.

Queen positions outside the chessboard boundaries (0-7)

How to Handle:

Ignore any queen with invalid coordinates (outside the 0-7 range) or throw an IllegalArgumentException.

King position outside the chessboard boundaries (0-7)

How to Handle:

Throw an IllegalArgumentException as the king must be within the board.

Large number of queens; assess time complexity.

How to Handle:

The solution should have a time complexity of O(N) where N is the number of queens to avoid timeouts with large input.

No queens can attack the king

How to Handle:

The algorithm should correctly return an empty list in this scenario.