[Java] O(n) solution with HashMap
\nclass Solution {\n    String horisontalLess = "horisontalLess";\n    String horisontalBigger = "horisontalBigger";\n    \n    String verticalLess = "verticalL
```\nclass Solution {\n    String horisontalLess = "horisontalLess";\n    String horisontalBigger = "horisontalBigger";\n    \n    String verticalLess = "verticalLess";\n    String verticalBigger = "verticalBigger";\n    \n    String diahonal1Less = "diahonal1Less";\n    String diahonal1Bigger = "diahonal1Bigger";\n    \n    String diahonal2Less = "diahonal2Less";\n    String diahonal2Bigger = "diahonal2Bigger";\n    \n    public List<List<Integer>> queensAttacktheKing(int[][] queens, int[] king) {\n         Map<String,List<Integer>>candidates = new HashMap<>();\n        String keyToInsert = null;\n        for (int queen[]:queens){\n            keyToInsert=null;\n            if (queen[0]==king[0]){\n                if (queen[1]>king[1] && (candidates.get(verticalBigger)==null ||  candidates.get(verticalBigger).get(1)>queen[1])) \n                    keyToInsert = verticalBigger;\n                if (queen[1]<king[1] && (candidates.get(verticalLess)==null ||  candidates.get(verticalLess).get(1)<queen[1]))\n                    keyToInsert = verticalLess;\n            }\n            \n            if (queen[1]==king[1]){\n                if (queen[0]>king[0] && (candidates.get(horisontalBigger)==null ||  candidates.get(horisontalBigger).get(0)>queen[0])) \n                    keyToInsert = horisontalBigger;\n                if (queen[0]<king[0] && (candidates.get(horisontalLess)==null ||  candidates.get(horisontalLess).get(0)<queen[0]))\n                    keyToInsert = horisontalLess;\n            }\n            \n            \n            if (queen[1]-queen[0]==king[1]-king[0]){\n                if (queen[0]>king[0] && (candidates.get(diahonal1Bigger)==null ||  candidates.get(diahonal1Bigger).get(0)>queen[0])) \n                    keyToInsert = diahonal1Bigger;\n                if (queen[0]<king[0] && (candidates.get(diahonal1Less)==null ||  candidates.get(diahonal1Less).get(0)<queen[0]))\n                    keyToInsert = diahonal1Less;\n            }\n            \n            if (queen[1]+queen[0]==king[1]+king[0]){\n                if (queen[0]>king[0] && (candidates.get(diahonal2Bigger)==null ||  candidates.get(diahonal2Bigger).get(0)>queen[0])) \n                    keyToInsert = diahonal2Bigger;\n                if (queen[0]<king[0] && (candidates.get(diahonal2Less)==null ||  candidates.get(diahonal2Less).get(0)<queen[0]))\n                    keyToInsert = diahonal2Less;\n            }\n            \n            if (keyToInsert!=null) {\n                List<Integer>candidate = new ArrayList<>();\n                    candidate.add(queen[0]); \n                    candidate.add(queen[1]);\n                candidates.put(keyToInsert, candidate);\n            }\n        }\n        \n        return new ArrayList<>(candidates.values());\n    }\n}\n```
[]