What is the time complexity of Queens That Can Attack the King?

The optimal solution has a time complexity of O(N).

What data structures are used to solve Queens That Can Attack the King?

This problem uses Array, Matrix, Simulation. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Queens That Can Attack the King?

Insight 1: We need to check all 8 possible directions (horizontal, vertical, and diagonals) from the king's position. Insight 2: A set or hash table is an efficient way to store the queen positions for fast lookup.

Which companies ask LeetCode 1222. Queens That Can Attack the King in interviews?

This problem is frequently asked at Media.net.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Queens That Can Attack the King - LeetCode 1222 Solution

Queens That Can Attack the King - Complete Solution Guide

Queens That Can Attack the King is LeetCode problem 1222, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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: qu

Detailed Explanation

The problem asks us to find all black queens on an 8x8 chessboard that can directly attack a white king. A queen can attack horizontally, vertically, and diagonally. We are given the positions of the queens and the king as integer coordinates. The goal is to return a list of the queen coordinates that can attack the king, ensuring that no other queen or obstacle blocks the line of sight between the queen and the king.

Solution Approach

The provided solution iterates through the 8 possible directions from the king's position. For each direction, it moves one step at a time until it finds a queen or reaches the edge of the board. If a queen is found, its coordinates are added to the result list. Using a set/hash table to store the queen positions allows for quick checking if a given coordinate contains a queen.

Step-by-Step Algorithm

Step 1: Create a set (or hash table) to store the positions of the queens for fast lookup.
Step 2: Initialize an empty list to store the attacking queens.
Step 3: Define the eight possible directions a queen can attack in: up, down, left, right, and the four diagonals.
Step 4: Iterate through each of the eight directions.
Step 5: For each direction, start from the king's position and move one step at a time.
Step 6: Check if the current position is within the bounds of the chessboard (0 to 7).
Step 7: If the current position is within bounds, check if there's a queen at that position using the set.
Step 8: If a queen is found, add its coordinates to the list of attacking queens and stop searching in that direction.
Step 9: If the current position is out of bounds, stop searching in that direction.
Step 10: After iterating through all directions, return the list of attacking queens.

Key Insights

Insight 1: We need to check all 8 possible directions (horizontal, vertical, and diagonals) from the king's position.
Insight 2: A set or hash table is an efficient way to store the queen positions for fast lookup.
Insight 3: We should iterate through each direction until we either encounter a queen or reach the edge of the board.

Complexity Analysis

Time Complexity: O(N)

Space Complexity: O(N)

Topics

This problem involves: Array, Matrix, Simulation.

Companies

Asked at: Media.net.

Queens That Can Attack the King | LeetCode 1222

Medium

Array Matrix Simulation

Time: O(N)Space: O(N)

Solution Code

Available in:

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public List<List<Integer>> queensAttacktheKing(int[][] queens, int[] king) {
        Set<String> queenSet = new HashSet<>();
        for (int[] q : queens) {
            queenSet.add(q[0] + "," + q[1]);
        }

        List<List<Integer>> attackingQueens = new ArrayList<>();

        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, 
                              {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};

        int kr = king[0];
        int kc = king[1];

        for (int[] dir : directions) {
            int dr = dir[0];
            int dc = dir[1];

            int r = kr;
            int c = kc;

            while (true) {
                r += dr;
                c += dc;

                if (!(0 <= r && r < 8 && 0 <= c && c < 8)) {
                    break;
                }

                if (queenSet.contains(r + "," + c)) {
                    List<Integer> queenPos = new ArrayList<>();
                    queenPos.add(r);
                    queenPos.add(c);
                    attackingQueens.add(queenPos);
                    break;
                }
            }
        }

        return attackingQueens;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 1222: Queens That Can Attack the King - Detailed explanation and solution approaches.

Topics

Array Matrix Simulation

Companies

Media.net

Stats

Difficulty:Medium

Languages:4

Companies:1

Problem #:1222

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

10 steps

1
Step 1: Create a set (or hash table) to store the positions of the queens for fast lookup.
2
Step 2: Initialize an empty list to store the attacking queens.
3
Step 3: Define the eight possible directions a queen can attack in: up, down, left, right, and the four diagonals.
4
Step 4: Iterate through each of the eight directions.
5
Step 5: For each direction, start from the king's position and move one step at a time.
6
Step 6: Check if the current position is within the bounds of the chessboard (0 to 7).
7
Step 7: If the current position is within bounds, check if there's a queen at that position using the set.
8
Step 8: If a queen is found, add its coordinates to the list of attacking queens and stop searching in that direction.
9
Step 9: If the current position is out of bounds, stop searching in that direction.
10
Step 10: After iterating through all directions, return the list of attacking queens.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(N)

💾

Space Complexity

O(N)

📝

Why?

The time complexity is O(N) because the dominant operation is inserting the queen positions into a set/hash table. The searching part is O(1) * 8 directions, which is constant time. The space complexity is O(N) because we store the queen positions in a set. The space required for the result list is at most the number of queens, which is bounded by N.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Brute-Force Approach

Iterate through all queens and check if each queen can attack the king. To check if a queen can attack the king, verify if they are in the same row, column, or diagonal. Also, ensure no other queen lies between them.

Time: O(N^2), where N is the number of queens. For each queen, we potentially need to iterate through all other queens to check for obstructions.Space: O(1).

Trade-offs: This approach has a higher time complexity than the set-based approach, especially if the number of queens is large. The primary advantage is the lower space complexity.

✨

Key Insights

1Insight 1: We need to check all 8 possible directions (horizontal, vertical, and diagonals) from the king's position.
2Insight 2: A set or hash table is an efficient way to store the queen positions for fast lookup.
3Insight 3: We should iterate through each direction until we either encounter a queen or reach the edge of the board.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Edge Cases

Edge case 1: The king is surrounded by queens on all sides. The solution will correctly identify all the surrounding queens as attacking queens.
Edge case 2: No queens are present on the board. The solution will return an empty list, which is the expected behavior.
Edge case 3: A queen is located at the king's position. This should not happen based on the problem description (positions are unique), but if it did, the solution would incorrectly identify it as an attacking queen if no additional checks were added. The provided solutions work since they search in each direction *from* the king position, not including it.
Edge case 4: Queens are positioned such that some are blocked by others. The algorithm correctly identifies only the closest attacking queen in each direction, ignoring queens blocked by others.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not checking the boundaries of the chessboard while searching for attacking queens. This can lead to out-of-bounds errors.

✗Common mistake 2: Failing to consider all eight possible directions of attack for a queen.

✗Common mistake 3: Not handling the case where no queen can attack the king, leading to incorrect output.

✗Common mistake 4: Returning blocked queens. It is important to only add the closest queen in each direction.

✗Common mistake 5: Incorrectly calculating the direction vectors, which would affect whether a queen could actually be reached

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: In a game of chess, this algorithm can be used to determine which pieces are attacking the king or other key pieces.

🏦Real-world scenario 2: In a sensor network, if we want to detect threats to a central node, we can use a similar algorithm to identify the closest sensor in each direction that detects a potential threat. The chessboard represents a space, the queens are the sensors and the king is the central node.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

If stuck, try working through a small example by hand. The pattern often reveals itself.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: October 21, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 14

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 7

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Queens That Can Attack the King"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether matrix techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?