We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Queens That Can Attack the King

Number: 1342

Difficulty: Medium

Paid? No

Companies: Media.net

Problem Description

Given an 8x8 chessboard with several queens and one king, find all queens that can directly attack the king. A queen can attack along eight directions (vertical, horizontal, or diagonal) if no other queen is blocking the path.

Key Insights

  • Consider the eight directions from the king (vertical, horizontal, and both diagonals).
  • For each direction, move step-by-step until you either reach the board edge or find a queen.
  • Only the first queen encountered in each direction can attack the king; any subsequent ones are blocked.
  • Use a set for quick look-up of queen positions on the board.

Space and Time Complexity

Time Complexity: O(N) where N is the number of queens, since in the worst-case scenario you'll check each queen's presence in at most 8 possible directions. Space Complexity: O(N) due to storing queen positions in a set for constant time look-up.

Solution

The solution involves simulating the movement from the king's position in the eight possible directions. First, store all queen positions in a set for quick look-up. For each of the eight directions (represented as (dx, dy) deltas), start from the king’s location and move step-by-step. If a queen is found at the current position during this traversal, add it to the result list and stop further movement in that direction. Continue until the board boundary is reached for that direction.

Code Solutions

# Define the function to find queens that can attack the king
def queensAttackTheKing(queens, king):
    # Convert list of queens to a set for O(1) lookup time
    queen_positions = {(q[0], q[1]) for q in queens}
    
    result = []
    # Define the eight possible directions (dx, dy)
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)]
    
    # Iterate over each direction
    for dx, dy in directions:
        x, y = king
        # Move from the king's position in the current direction
        while 0 <= x < 8 and 0 <= y < 8:
            x += dx
            y += dy
            # If a queen is found at the position, add it to result and break
            if (x, y) in queen_positions:
                result.append([x, y])
                break
    return result

# Example usage:
queens = [[0,1],[1,0],[4,0],[0,4],[3,3],[2,4]]
king = [0,0]
print(queensAttackTheKing(queens, king))  # Expected output: [[0,1],[1,0],[3,3]]
← Back to All Questions