Queens That Can Attack the King

Problem Statement:

There is an 8x8 chessboard, there can be multiple Black Queens and one White King. We are given with the coordinates of all the black queens and and one white king, we have to return all the queens (in any order) that can attack the King.

Let’s understand this with an example:

Image source: Leetcode (online coding platform)

Let’s take top left corner as coordinate [0,0]; top right corner will be [0,7]; bottom left corner will be [7,0]; and bottom right corner will be [7,7].

The white king is at [3,3].

Queen at [2,2] can attack the king as it is on the same diagonal.

Please note that, the queen at [1,1] can’t attack the king because there is a queen in between this queen at [1,1] and the king at [3,3]. The queen at [2,2] is blocking all the other queens from attacking the king that on the same diagonal on left side of the king.

Now, the queen at [3,4] is on same horizontal axis as the king, therefore it will attack the king, but the queen at [3,5] can’t attack the king as there is blocking queen between this queen and the king.

So, let’s begin.

Problem constraints:

• 1 <= queens.length <= 63
• queens[0].length == 2
• 0 <= queens[i][j] < 8
• king.length == 2
• 0 <= king[0], king[1] < 8
• At most one piece is allowed in a cell.

In chess, queen can attack in all the directions, i.e. horizontally, vertically and diagonally. Therefore, if there is a king at some coordinate, it can be attacked from all the possible directions around it i.e. all the 8 directions if a queen is present in all those directions.

Possible directions around the king, considering the king coordinate as [0,0]

So, we can think about finding the first queen in all the directions. Only that queen will be able to attack the king as all the remaining queens will be blocked by the first queen of that direction.

The problem breaks down into finding the first queen in all directions, if present.

Possible directions as shown in the above diagram are:

topLeft = [-1,1]
top = [-1,0]
topRight = [-1,-1]
left = [0,-1]
right = [0,1]
bottomLeft = [1,-1]
bottom = [1,0]
bottomRight = [1,1]

If we want to check the left side of the king, we can keep on adding [0,-1] to the coordinate of king until we are not crossing the leftmost border of the chessboard. Similarly we can do for other directions.

Let’s jump to the code to understand further.

Code Analysis:

int positions[][] = new int[8][8]; //this will store the positions of queens on the chessboard 
//all the possible directions around the king
int xDir[] = new int[]{-1,-1,-1,0,0,1,1,1};
int yDir[] = new int[]{-1,0,1,-1,1,-1,0,1};
public List<List<Integer>> queensAttacktheKing(int[][] queens, int[] king) {
        List<List<Integer>> attackingQueens = new ArrayList<>();
        
        /** put all the queens on the chessboard **/
        for(int i=0; i<queens.length; i++){
            positions[queens[i][0]][queens[i][1]] = 1;
        }
        
        /** iterate for all the directions around the king and if a queen is found in that direction add it in the attacking queens list **/
        for(int i=0; i<8; i++){
            List<Integer> temp = getFirstQueen(king[0], king[1], xDir[i], yDir[i]);
            if(temp.size()==2) {
                attackingQueens.add(temp);
            }
        }
        
        return attackingQueens;
    }

Defining the getFirstQueen function. This function will return the coordinate of the first queen in that direction in an array list.

private List<Integer> getFirstQueen(int kx, int ky, int x, int y){
        List<Integer> temp = new ArrayList<>(2);
        
        //checking if the position at which we will checking the queen is valid or not
        //i.e. the position is not out of the chessboard
        while(kx+x>=0 && kx+x<8 && ky+y>=0 && ky+y<8){
            kx = kx+x;
            ky = ky+y;
            
            //queen is present at that coordinate
            if(positions[kx][ky]==1){
                temp.add(kx);
                temp.add(ky);
                break; //moment we found a queen we break out of the loop
            }
        }
        
        return temp;
    }

Complexity Analysis:

Space complexity = O(8*8) — to store the positions of the queens
Time complexity = O(no. of queens) — while storing all the queens on chessboard + 8*O(3) (i.e. constant time in the worst case when all the queens are present on the borders and king is on the center of the chessboard) — while checking all the possible directions around the king => O(63) equivalent to constant time as there can be at most 63 queens on 8*8 chessboard.

Thanks for devoting your time to this article. I hope you find it helpful and it gives you a clear insight.

If you still have any query, feel free to respond. If you find it helpful, then please share it among your colleagues. Your claps motivate me to write more such blogs! :)