queens ♛ Attacks King ♚
Intuition\n- This code is a Java implementation of a solution to the Queens That Can Attack the King problem on LeetCode. The problem involves finding all the q
# Intuition\n- This code is a Java implementation of a solution to the `Queens That Can Attack the King` problem on `LeetCode`. The problem involves finding all the queens on a chessboard that can attack a given king.\n\n# Complexity\n- **Time complexity:**\nThe time complexity of this code is `O(q)`, where `q` is the number of queens. The for loop that iterates over the queens takes `O(q)` time. The inline and NearMore methods both have constant time complexity, so the total time complexity of the algorithm is dominated by the for loop. The worst-case scenario is when all queens are in line with the king, which requires checking all `q` queens. Therefore, the overall time complexity is `O(q)`.\n\n- **Space complexity:**\nThe space complexity of this code is `O(1)` since it only uses a fixed amount of memory to store the indexes array, `dy`, `dx`, and index variables. The number of queens and the king\'s position are given as inputs, but they are not used to allocate memory dynamically. The lists variable used to store the result has a maximum length of `8`, which is the maximum number of queens that can attack the king.\n\n# Code\n- This line declares the `queensAttacktheKing` method, which takes two inputs: an array of queen positions `queens` and the position of the king `king`. The method returns a list of positions of queens that can attack the king.\n``` java\npublic List<List<Integer>> queensAttacktheKing(int[][] queens, int[] king)\n```\n- This line initializes the indexes array to `-1` for all eight directions (up-left, up, up-right, right, down-right, down, down-left, left).\n``` java\nint[] indexes = new int[]{-1, -1, -1, -1, -1, -1, -1, -1};\n```\n- These lines declare three integer variables to be used in the loop.\n``` java\nint dy, dx, index;\n```\n- This line starts a loop that iterates over all the queens on the board.\n``` java\nfor (int i = 0; i < queens.length; i++)\n```\n- This line checks if the current queen is in the same row, column, or diagonal as the king. The `inline` method is called to check this.\n``` java\nif (inline(queens[i], king))\n```\n- These lines calculate the vertical and horizontal distances between the `queen` and the `king`.\n``` java\ndy = king[1] - queens[i][1];\ndx = king[0] - queens[i][0];\n```\n- These lines calculate the `index` of the `indexes` array for the direction of the `queen` relative to the `king`. If the `queen` is in the same row, the `index` will be `7` or `3`. If the `queen` is in the same column, the `index` will be `1` or `5`. If the `queen` is in a diagonal direction, the `index` will be `0`, `2`, `4`, or `6`.\n``` java\n/* \n    up-left -> 0, \n    up -> 1, \n    up-right -> 2, \n    right -> 3, \n    down-right -> 4, \n    down -> 5, \n    down-left -> 6, \n    left -> 7\n*/\nif (dx == 0) index = dy < 0 ? 1 : 5;\nelse if (dy == 0) index = dx < 0 ? 7 : 3;\nelse if (dy < 0) index = dx < 0 ? 0 : 2;\nelse index = dx < 0 ? 6 : 4;\n```\n- This line updates the `indexes` array if the current `queen` is closer to the `king` in the given direction than the previous `queen` (if any) in that direction. The `NearMore` method is called to check this.\n\n``` java\nif (indexes[index] == -1 || NearMore(queens[i], queens[indexes[index]], king)) indexes[index] = i;\n```\n- Finally, this block of code creates a list of `queen` positions from the `indexes` array and returns it.\n``` java\nList<List<Integer>> lists = new ArrayList<>();\nfor (int i : indexes) if (i != -1) lists.add(Arrays.asList(queens[i][0], queens[i][1]));\nreturn lists;\n```\n- The `inline` method checks whether two pairs of coordinates are in the same row, column, or diagonal, by checking whether their x-coordinates are equal, their y-coordinates are equal, or the absolute difference of their x-coordinates equals the absolute difference of their y-coordinates, respectively.\n``` java\npublic boolean inline(int[] pair1, int[] pair2) {\n    return\n        pair1[0] == pair2[0] || // case row eq\n        pair1[1] == pair2[1] || // case col eq\n        Math.abs(pair1[1] - pair2[1]) == Math.abs(pair1[0] - pair2[0]); // case cross\n}\n```\n- The `NearMore` method checks which of `two pairs` of coordinates is closer to a target pair of coordinates. If the `two pairs` have the same x-coordinate (i.e., they are in the same row), it returns true if the absolute difference of their y-coordinates to the target is less than the corresponding difference of the other pair. Similarly, if the two pairs have the same y-coordinate (i.e., they are in the same column), it returns true if the absolute difference of their x-coordinates to the target is less than the corresponding difference of the other pair. If neither of these conditions hold, it returns `true` if the distance of the first pair from the target is `less than` the distance of the second pair from the target.\n``` java\npublic boolean NearMore(int[] pair1, int[] pair2, int[] target) {\n    // case raw\n    if (pair1[0] == pair2[0]) return Math.abs(target[1] - pair1[1]) < Math.abs(target[1] - pair2[1]);\n    // case column\n    if (pair1[1] == pair2[1]) return Math.abs(target[0] - pair1[0]) < Math.abs(target[0] - pair2[0]);\n    // case cross\n    return  // dy_1^2 + dx_1^2 < dy_2^2 + dx_2^2\n        Math.pow(target[1] - pair1[1], 2) + Math.pow(target[0] - pair1[0], 2) <\n        Math.pow(target[1] - pair2[1], 2) + Math.pow(target[0] - pair2[0], 2);\n}\n```\n# Full Code\n``` java\nclass Solution {\n    public List<List<Integer>> queensAttacktheKing(int[][] queens, int[] king) {\n        // {\n        //      up-left -> 0, \n        //      up -> 1, \n        //      up-right -> 2, \n        //      right -> 3, \n        //      down-right -> 4, \n        //      down -> 5, \n        //      down-left -> 6, \n        //      left -> 7\n        // } \n        int[] indexes = new int[]{-1, -1, -1, -1, -1, -1, -1, -1};\n        int dy, dx, index;\n        for (int i = 0; i < queens.length; i++) {\n            if (inline(queens[i], king)) // in line with king\n            {\n                dy = king[1] - queens[i][1];\n                dx = king[0] - queens[i][0];\n                // in column\n                if (dx == 0) index = dy < 0 ? 1 /* up */ : 5 /* down */;\n                    // in row\n                else if (dy == 0) index = dx < 0 ? 7 /* left */ : 3 /* right */;\n                    // cross-up\n                else if (dy < 0) index = dx < 0 ? 0 /* up-left */ : 2 /* up-right */;\n                    // cross-down\n                else index = dx < 0 ? 6 /* down-left */ : 4 /* down-right */;\n                if (indexes[index] == -1 || NearMore(queens[i], queens[indexes[index]], king)) indexes[index] = i;\n            }\n        }\n        // setup result\n        List<List<Integer>> lists = new ArrayList<>();\n        for (int i : indexes) if (i != -1) lists.add(Arrays.asList(queens[i][0], queens[i][1]));\n        return lists;\n    }\n\n    public boolean inline(int[] pair1, int[] pair2) {\n        return\n            pair1[0] == pair2[0] || // case row eq\n            pair1[1] == pair2[1] || // case col eq\n            Math.abs(pair1[1] - pair2[1]) == Math.abs(pair1[0] - pair2[0]); // case cross\n    }\n\n    public boolean NearMore(int[] pair1, int[] pair2, int[] target) {\n        // case raw\n        if (pair1[0] == pair2[0]) return Math.abs(target[1] - pair1[1]) < Math.abs(target[1] - pair2[1]);\n        // case column\n        if (pair1[1] == pair2[1]) return Math.abs(target[0] - pair1[0]) < Math.abs(target[0] - pair2[0]);\n        // case cross\n        return  // dy_1^2 + dx_1^2 < dy_0^2 + dx_0^2\n            Math.pow(target[1] - pair1[1], 2) + Math.pow(target[0] - pair1[0], 2) <\n            Math.pow(target[1] - pair2[1], 2) + Math.pow(target[0] - pair2[0], 2);\n    }\n}\n```\n\n\n
['Array', 'Math', 'Java']