<p>On a <strong>0-indexed</strong> <code>8 x 8</code> chessboard, there can be multiple black queens and one white king.</p>

<p>You are given a 2D integer array <code>queens</code> where <code>queens[i] = [xQueen<sub>i</sub>, yQueen<sub>i</sub>]</code> represents the position of the <code>i<sup>th</sup></code> black queen on the chessboard. You are also given an integer array <code>king</code> of length <code>2</code> where <code>king = [xKing, yKing]</code> represents the position of the white king.</p>

<p>Return <em>the coordinates of the black queens that can directly attack the king</em>. You may return the answer in <strong>any order</strong>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/12/21/chess1.jpg" style="width: 400px; height: 400px;" />
<pre>
<strong>Input:</strong> queens = [[0,1],[1,0],[4,0],[0,4],[3,3],[2,4]], king = [0,0]
<strong>Output:</strong> [[0,1],[1,0],[3,3]]
<strong>Explanation:</strong> The diagram above shows the three queens that can directly attack the king and the three queens that cannot attack the king (i.e., marked with red dashes).
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/12/21/chess2.jpg" style="width: 400px; height: 400px;" />
<pre>
<strong>Input:</strong> queens = [[0,0],[1,1],[2,2],[3,4],[3,5],[4,4],[4,5]], king = [3,3]
<strong>Output:</strong> [[2,2],[3,4],[4,4]]
<strong>Explanation:</strong> The diagram above shows the three queens that can directly attack the king and the three queens that cannot attack the king (i.e., marked with red dashes).
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= queens.length &lt; 64</code></li>
	<li><code>queens[i].length == king.length == 2</code></li>
	<li><code>0 &lt;= xQueen<sub>i</sub>, yQueen<sub>i</sub>, xKing, yKing &lt; 8</code></li>
	<li>All the given positions are <strong>unique</strong>.</li>
</ul>

class Solution:
    def queensAttacktheKing(self, queens: List[List[int]], king: List[int]) -> List[List[int]]:
        # Work outwards from king and see if any queens are on this path.
        # This is fast because we can use math to determine if they're on a row, column, or diag from the king.
        # Check each queen once.
        # There are a maximum of 8 possible queens that can attack directly. It suffices to simply replace each of these in a lookup for the closest queen.
        i, j = king
        spaces = {}  # make 0 equal to vertical
        def get_space(x, y) -> int:  # -1 is not Valid. Ignore on top.
            if j == y:  # vertical attack, 0 or 3
                if x < i:  # above
                    return 0
                else:
                    return 4
            if i == x:  # horizontal attack
                if y > j:  # right
                    return 2
                else:
                    return 6
            elif abs(x - i) == abs(y - j):  # diags
                if x < i and y < j:  # top left
                    return 7
                elif x < i and y > j:  # top right
                    return 1
                elif x > i and y > j:
                    return 3
                elif x > i and y < j:
                    return 5
            else:
                return -1

        def hamming(pos1, pos2):
            return abs(pos1[0] - pos2[0]) + abs(pos1[1] - pos2[1])

        def closer(queen1, queen2) -> tuple[int, int]:  # return list cause easier. This type is better.
            # Closer is defined relative to the king. Since these are in the same line, we can simply do two diffs and return the abs sum. Essentially hamming distance.
            if hamming(queen1, (i, j)) < hamming(queen2, (i, j)):  # ignore collision
                return queen1
            return queen2


        for queen in queens:
            space = get_space(*queen)
            if space != -1:
                existing_queen = spaces.get(space, [])
                if len(existing_queen):
                    spaces[space] = closer(queen, existing_queen)
                else:
                    spaces[space] = queen
        return list(spaces.values())


        
16300