Queens That Can Attack the King - Practice Coding Problems

Queens That Can Attack the King - Problem

On a 0-indexed 8 × 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.

A queen can attack the king if they are on the same row, column, or diagonal with no other pieces blocking the path.

Input & Output

Example 1 — Multiple Queens

$ Input: queens = [[0,1],[1,0],[4,0],[0,4],[3,3],[2,4]], king = [0,0]

› Output: [[0,1],[1,0],[3,3]]

💡 Note: Queen at [0,1] attacks king vertically upward. Queen at [1,0] attacks king horizontally. Queen at [3,3] attacks king diagonally. Other queens are either not aligned or blocked by these closer queens.

Example 2 — Some Blocked

$ Input: queens = [[0,0],[1,1],[2,2],[3,4],[3,5],[4,4],[5,6]], king = [3,3]

› Output: [[2,2],[3,4],[4,4]]

💡 Note: Queen at [2,2] can attack diagonally. Queen at [3,4] attacks horizontally. Queen at [4,4] attacks diagonally. Queen at [0,0] is blocked by [2,2], and [3,5] is blocked by [3,4].

Example 3 — Edge Position

$ Input: queens = [[5,6],[7,7],[2,1],[0,7],[1,6],[5,1],[3,7],[0,3],[4,0],[1,2],[6,3],[5,0]], king = [0,4]

› Output: [[0,3],[0,7],[1,2]]

💡 Note: From king at [0,4]: Queen at [0,3] attacks vertically down, [0,7] attacks vertically up, and [1,2] attacks diagonally. Other queens are either not aligned with king or blocked.

Constraints

1 ≤ queens.length ≤ 63
queens[i].length == 2
0 ≤ queens[i][j] < 8
king.length == 2
0 ≤ king[0], king[1] < 8
All the given positions are unique

Visualization

Tap to expand

Understanding the Visualization

Input

8×8 chessboard with queens and king positions

Process

Find queens that can attack king directly (no blocking)

Output

Coordinates of attacking queens

Key Takeaway

🎯 Key Insight: Search from king outward in 8 directions - first queen found in each direction can attack

Asked in

a Amazon 15 M Microsoft 8

The key insight is to search outward from the king's position in all 8 directions rather than checking each queen individually. Best approach is the optimized direction-based search with Time: O(1), Space: O(1) since we're limited to an 8×8 board.

Common Approaches

Approach	Time	Space	Notes
✓ Optimized - Search from King	O(8 × 8) = O(1)	O(1)	Start from king and search outward in 8 directions until finding first queen
Brute Force - Check All Queens	O(n²)	O(1)	Check each queen to see if it can attack the king directly

Optimized - Search from King — Algorithm Steps

Start from king's position
Search in each of 8 directions (horizontal, vertical, diagonal)
For each direction, move step by step until hitting a queen or board boundary
First queen found in each direction can attack the king

Visualization

Tap to expand

Step-by-Step Walkthrough

Start from King

Begin at king's position

Search 8 Directions

Move outward in each direction until finding queen

Collect Results

First queen in each direction can attack

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int solution(int queens[][2], int queensSize, int king[2], int result[][2]) {
    int count = 0;
    
    // 8 directions: up, down, left, right, and 4 diagonals
    int directions[8][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, 
                            {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
    
    for (int d = 0; d < 8; d++) {
        int dx = directions[d][0];
        int dy = directions[d][1];
        
        // Start from king and move in this direction
        int x = king[0] + dx;
        int y = king[1] + dy;
        
        // Keep moving until we hit a queen or go out of bounds
        while (x >= 0 && x < 8 && y >= 0 && y < 8) {
            // Check if there's a queen at this position
            bool foundQueen = false;
            for (int i = 0; i < queensSize; i++) {
                if (queens[i][0] == x && queens[i][1] == y) {
                    result[count][0] = x;
                    result[count][1] = y;
                    count++;
                    foundQueen = true;
                    break;
                }
            }
            if (foundQueen) {
                break; // First queen in this direction can attack
            }
            x += dx;
            y += dy;
        }
    }
    
    return count;
}

int main() {
    char line[1000];
    int queens[64][2];
    int queensSize = 0;
    int king[2];
    
    // Read queens (simplified parsing)
    fgets(line, sizeof(line), stdin);
    char *ptr = line;
    while (*ptr) {
        if (*ptr == '[' && *(ptr+1) != '[') {
            sscanf(ptr+1, "%d,%d", &queens[queensSize][0], &queens[queensSize][1]);
            queensSize++;
        }
        ptr++;
    }
    
    // Read king
    fgets(line, sizeof(line), stdin);
    sscanf(line, "[%d,%d]", &king[0], &king[1]);
    
    int result[8][2];
    int count = solution(queens, queensSize, king, result);
    
    printf("[");
    for (int i = 0; i < count; i++) {
        printf("[%d,%d]", result[i][0], result[i][1]);
        if (i < count - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(8 × 8) = O(1)

At most 8 directions × 8 steps per direction on an 8×8 board, which is constant

✓ Linear Growth

Space Complexity

O(1)

Only using variables to track current position and direction vectors

✓ Linear Space

28.4K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized - Search from King — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler