[Java] Guaranteed O(n log n) solution with some explanation
Same idea as the O(max(n, limit)) solutions, but keep track of all the turning points (points where the number of operations change), and only walk through thes
Same idea as the O(max(n, limit)) solutions, but keep track of all the turning points (points where the number of operations change), and only walk through these points when calculating the final answer.\nSince every 2 numbers in the array have at most 5 turning points, the number of turning points is O(n); and keeping them in a sorted map (tree map here) costs O(n log n).\n\nA bit of explanation:\n\n- If an array is complementary, all pairs of numbers add up to the same number, which for convenience we may call the `target number`; but we don\'t know what this target number would be.\n- Therefore, we need to try different possible values of the `target number`, and find the minimal numbers of operations to reach these possible values.\n- For each of the pairs, if we denote the smaller number `less` and the larger number `more`, we will have 5 intervals that require different numbers of operations to reach (ignoring corner cases):\n(1) `target number == less + more`, we need to perform 0 operations.\n(2) notice that if we only perform one operation, the minimal sum we could get is `less + 1`, in other words changing `more` to `1`; thus if `target number` is in interval `[less + 1, less + more - 1]`, we need to perform one operation to bring the sum of `less` and `more` to `target number`.\n(3) symmetrically, if `target number` is in interval `[less + more + 1, more + limit]`, we need to perform one operation, which is to increase `less` to `limit`.\n(4) now a fourth situation is when `target number < less + 1`. In this case, we need to change both `less` and `more` in order to get `target number`. Therefore, if `target number` is in interval `[2, less]`, we need to perform 2 operations.\n(5) symmetrically we need to perform 2 operations if `target number` is in `[more + limit + 1, 2 * limit]`.\n\n- Now that we have these intervals, how do we get the final result? A straightforward answer is that we iterate over all the possible `target number`s, and return the smallest number of operations needed.\n- We achieve this by maintaining a rolling sum of number of operations needed:\n(1) We start from `target number == 2`, in which case each pair will need 2 operations (unless one or more of `less` and `more` is `1`, but that\'s a corner case :3), so we have a rolling sum of number of operations of `2 * (n / 2) == n`.\n(2) A turning point is the number beyond which the number of operations needed to reach `target number` changes. Whenever `target number` reaches a turning point, we update the rolling sum of number of operations.\n(3) Apparently the first 2 turning points (`less + 1`, `less + more`) decrease the number of operations needed by 1; the last 2 (`less + more + 1`, `more + limit + 1`) increase it by 1.\n(4) We return the smallest rolling sum ever seen.\n\n- An "optimisation" is to only consider `target number`s that equal some turning point, which is useful when `limit` is very large (larger than `n log n`, the cost of maintaining a sorted list of turning points). \n\n```\nclass Solution {\n    public int minMoves(int[] nums, int limit) {\n        var turningPoint = new TreeMap<Integer, Integer>();\n\n        for (int i = 0; i < nums.length / 2; i ++) {\n            int less = Math.min(nums[i], nums[nums.length - i - 1]), more = Math.max(nums[i], nums[nums.length - i - 1]);\n\n            if (less == 1) {\n                addToMap(turningPoint, 2, 1);\n            }\n            else {\n                addToMap(turningPoint, 2, 2);\n                addToMap(turningPoint, less + 1, -1);\n            }\n\n            addToMap(turningPoint, less + more, -1);\n\n            if (less + more + 1 <= limit * 2) {\n                addToMap(turningPoint, less + more + 1, 1);\n            }\n            if (more + limit + 1 <= limit * 2) {\n                addToMap(turningPoint, more + limit + 1, 1);\n            }\n        }\n\n        int watermark = 0, minimal = Integer.MAX_VALUE;\n        for (var entry : turningPoint.entrySet()) {\n            watermark += entry.getValue();\n            if (watermark < minimal) {\n                minimal = watermark;\n            }\n        }\n\n        return minimal;\n    }\n\n    private void addToMap(TreeMap<Integer, Integer> map, int key, int change) {\n        if (map.containsKey(key)) {\n            map.put(key, map.get(key) + change);\n        }\n        else {\n            map.put(key, change);\n        }\n    }\n}\n```\n
[]