Efficient and Simple Solution for Queens That Can Attack the King
IntuitionThe problem requires us to find all queens that can attack the king in an 8×8 chessboard. A queen can move horizontally, vertically, and diagonally, me
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The problem requires us to find all queens that can attack the king in an 8×8 chessboard. A queen can move horizontally, vertically, and diagonally, meaning we need to check in 8 possible directions to see if there is a queen in the path of the king.

# Approach
<!-- Describe your approach to solving the problem. -->
1. Store Queen Positions Efficiently:
    - We use a set<vector<int>> to store the queens' positions, allowing for O(1) average-time lookup when checking if a queen exists at a given position.
2. Traverse in 8 Directions:
    - We define 8 possible movement directions (left, right, up, down, and four diagonal directions).
    - We iterate outward from the king's position in each direction.
    - If we find a queen in that direction (i.e., the position exists in the set), we add it to the result and stop checking further in that direction.
3. Return the List of Attacking Queens:
    - The final list contains all the queens that can attack the king.

# Complexity
- Time complexity: O(1)
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
Inserting queens into the set: O(q), where q is the number of queens (at most 64).
Checking 8 directions:
In the worst case, the loop runs up to 8 times per direction (since an 8×8 board has at most 8 cells in any direction).
Since we have 8 directions, the worst-case scenario is O(8 × 8) = O(64) = O(1).
Overall time complexity: O(1) (constant time) because the board size is fixed at 8×8.


- Space complexity: O(1)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
Set to store queens: O(q) in the worst case (at most 64 queens).
Result vector: O(8) (maximum 8 attacking queens).
Overall space complexity: O(1) (since the board size is fixed, space usage does not grow dynamically).

![Screenshot 1946-11-16 at 07.38.14.png](https://assets.leetcode.com/users/images/cf5adcf3-5a87-4b25-9394-c2837a96d108_1738721414.6484265.png)
# Code
```cpp []
/*
    AUTHOR     - Prince Sharma
    DATE       - 6/2/2025 18:37
    PROBLEM    - Queens That Can Attack the King
    NOTATION   - O -> worst case complexcity, S -> for space complexity, T -> for time complexity
    COMPLEXITY - TO(1), SO(1)
*/

class Solution
{
public:
    vector<vector<int>> queensAttacktheKing(vector<vector<int>>& queens, vector<int>& king)
    {
        set<vector<int>> queens_search;
        vector<vector<int>> queens_attacking;
        vector<pair<int, int>> directions = {{0, -1}, {0, 1}, {-1, 0}, {1, 0},  // Horizontal & Vertical
                                            {-1, -1}, {1, -1}, {-1, 1}, {1, 1}}; // Diagonal
        for(auto queen:queens) queens_search.insert(queen);

        for(auto [rinc, linc]:directions)
            for(int row=king[0],column=king[1];row>=0 && row<8 && column>=0 && column<8; row+=rinc, column+=linc)
                if(queens_search.count({row, column}))
                    {queens_attacking.push_back({row, column}); break;}
        return queens_attacking;
    }
};
```
![99ebb786-8c55-43b7-a8c9-67ad8a9e9b02_1720172878.6942368.webp](https://assets.leetcode.com/users/images/0d3c0829-cc0d-4971-9e1a-c146182d1a6a_1738481810.709739.webp)
['Array', 'Matrix', 'Simulation', 'C++']