[Python3] O(n) Solution with Explanation
Optimized Solution Explanation\nThe idea is to search all possible paths starting at the king location. There can be at most 8 queens in the return array becaus
**Optimized Solution Explanation**\nThe idea is to search all possible paths starting at the king location. There can be at most 8 queens in the return array because the queen can only move in 8 directions.\nSteps:\n1. Create a queens set so you can do on O(1) operation check to see if the queen is in the path.\n2. Starting from the king location, check all 8 directions to find the first queen in that path.\n3. Exit early if you\'ve found 8 queens.\n\n**Time Complexity**\nO(n) (n=number of queens) to store the queens into a set\nAll other operations are constant as the board is fixed at 8 rows x 8 cols\nRuntime: 48 ms, faster than 100.00% of Python3 online submissions\n\n**Space Complexity**\nO(n) (n=number of queens) to store the queens into a set\nMemory Usage: 13.8 MB, less than 100.00% of Python3 online submissions\n\n**Code**\n```\nBOARD_ROWS = 8\nBOARD_COLS = 8\nclass Solution:\n    def queensAttacktheKing(self, queens: "List[List[int]]", king: "List[int]") -> "List[List[int]]":\n        def check(r,c,ro,co):\n            while (r >= 0 and r < BOARD_ROWS and\n                   c >= 0 and c < BOARD_COLS):\n                if (r,c) in queens:\n                    return (r,c)\n                r += ro\n                c += co\n            return None\n\n        # 1. Create a queens set so you can do on O(1) operation check\n\t\t# to see if the queen is in the path.\n        queens = set([(r,c) for r,c in queens]) # O(q) time, and space\n\n        res = []\n\t\t# 2. Starting from the king location, check all 8 directions to find the\n\t\t# first queen in that path.\n        for ro,co in [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]: # O(8) time\n            check_res = check(king[0],king[1],ro,co) # O(8) time\n            if check_res != None:\n                res.append([check_res[0],check_res[1]])\n\t\t\t\t# 3. Exit early if you\'ve found 8 queens.\n                if len(check_res) == 8:\n                    return res\n\n        return res\n```\n\n**Unoptimized O(nlogn) Solution Explanation**\nThe idea is to:\n1. Build a board to determine if a queen can reach the king\n2. Sort the queens based on closest proximity to the king. This is important because it will mark queen locations that block other further out queens.\n3. Use this sorted queens list as a stack to use DFS.\n4. Check all movement directions for all queens, and if it is able to get to the king, then mark it on the board, and add it to the results.\n\n**Time Complexity**\nO(qlogq + 2q) (q=number of queens) -> O(nlogn)\n\n**Space Complexity**\nO(1) because the board always has a constant/static limit of 8 rows and 8 columns\n\n**Code**\n```\nclass Solution:\n    def queensAttacktheKing(self, queens: "List[List[int]]", king: "List[int]") -> "List[List[int]]":\n        def check(r,c,ro,co):\n            while (r >= 0 and r < len(b) and\n                   c >= 0 and c < len(b[0]) and\n                   b[r][c] != 0):\n                   if b[r][c] == 0:\n                       return False\n                   if r == king[0] and c == king[1]:\n                       return True\n                   r += ro\n                   c += co\n            return False\n\n        def generate_board(mr,mc):\n            for r in range(mr+1):\n                b.append([])\n                for c in range(mc+1):\n                    b[r].append(1)\n\n        mr = mc = 0\n        for qr,qc in queens: # O(q) time\n            mr = max(mr, qr)\n            mc = max(mc, qc)\n        mr = max(mr, king[0])\n        mc = max(mc, king[1])\n\n        b = [] # O(1) space bc board has constant size of 8x8\n        generate_board(mr,mc) # O(1) time bc board has constant size of 8x8\n\n        queens.sort(key=lambda q: abs(q[0] - king[0]) + abs(q[1] - king[1]), reverse=True) # O(qlogq) time\n\n        res = []\n        while queens: # O(q) time\n            qr, qc = queens.pop()\n\n            for ro,co in [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]:\n                if check(qr,qc,ro,co) == True: # O(1) time bc the board has a constant size of 8x8\n                    b[qr][qc] = 0\n                    res.append([qr,qc])\n                    break\n\n        return res\n```
[]