Java | 3 Cases | Explained
IMO, this question is difficult. The hardest HashMap-tagged medium question. \n\nIntuition\n\nHere is how to break it down:\n- If the optimal pair sum OPT excee
IMO, this question is difficult. The hardest HashMap-tagged medium question. \n\n**Intuition**\n\nHere is how to break it down:\n- If the optimal pair sum `OPT` exceeds `MAX(a, b) + limit`, then we will need 2 moves to make this pair sum `OPT`\n\n- If the optimal pair sum `OPT` is below `MIN(a, b) + 1`, then we will need 2 moves to make this par sum `OPT`.\n- If the optimal pair sum `OPT` is between (inclusive) the above two ends, then we need 1 move to make it `OPT`.\n- If the optimal pair sum `OPT` happens to be `a + b`, then we don\'t need any move.\n\n**Strategy**\n\nMark the 1-move range for all the pairs with an array, where `oneMove[j]` means the number of pairs with min `j` requiring 1 move to form a sum of `j`.\nThat is to say, for each pair, we increment `oneMove[MIN(a, b) + 1]` and decrement `oneMove[MAX(a, b) + limit + 1]`.\n\nAnything outside of it `(nums of pairs - oneMove prefix sum)` will take 2 moves to form the sum `j`. \nHowever, we may have counted a pair as 1 move when in fact it should be 0 move, thus we need a HashMap to store pairs of perfect matches.\n\n**Solution**\n\n```Java\nclass Solution {\n    public int minMoves(int[] nums, int limit) {\n        int[] oneMove = new int[2 * limit + 2];\n        Map<Integer, Integer> noMove = new HashMap<>();\n\n        for (int i = 0; i < nums.length / 2; i++){\n            int j = nums.length - 1 - i;\n            noMove.merge(nums[i] + nums[j], 1, Integer::sum);\n            oneMove[Math.min(nums[i], nums[j]) + 1]++;\n            oneMove[Math.max(nums[i], nums[j]) + limit + 1]--;\n        }\n\n        int ans = nums.length, one = 0;\n        for (int i = 2; i <= 2 * limit; i++){\n            one += oneMove[i];\n            ans = Math.min(ans, one + 2 * (nums.length / 2 - one) - noMove.getOrDefault(i, 0));\n        }\n\n        return ans;\n    }\n}\n```\n\n
['Java']