Detailed Explain Why We Need Difference Array
This post is a further explaination of yanrucheng.
This post is a further explaination of [yanrucheng](https://leetcode.com/problems/minimum-moves-to-make-array-complementary/discuss/952773/PythonJava-simple-O(max(n-k)-method)\'s nice post. But I think he(she) didn\'t explain the intuition behind using difference array well. I think the intuition is that **when you find that maintaining an array is quite difficult, try to maintain its difference array instead**. \n\n> Idea\n> If we want to make the nums complementary, having all the pairs A = nums[i], B = nums[n - 1 - i] with A + B = T. Considering a pair A = nums[i], B = nums[n - 1 - i], there are 5 different situation for every such pair (A, B), given different target T.\n\n>1. 2 <= T < min(A, B) + 1, we need 2 operations to make both A, B smaller\n>2. min(A, B) + 1 <= T < A + B, we need 1 operation to make the larger one out of A and B smaller\n>3. T = A + B, we need 0 operation\n>4. A + B < T < max(A, B) + limit, we need 1 operation to make the smaller one out of A and B larger\n>5. max(A, B) + limit < T <= 2 * limit, we need 2 operation to make both A, B larger\n\nBased on how a specific pair ``(a, b)``should be modified given the target sum ``T``, the most straight-forward idea must be maintaining an array ``T[i]``, which means  **the total number of modification if we set the target sum as ``i``**. \n\nHowever, to maintain such a array ``T[i]`` we have to update a subarray of ``T[i]`` given each pair ``(a, b)``, which will result in ``O(N^2)``time complexity and thus unacceptable. This is where **difference array** comes in. Instead of directly maintaining ``T[i]``, we maintain the difference array ``dT[i] = T[i] - T[i-1]``, which means **if we change the target sum from ``i-1`` to ``i``, we need ``dT[i]`` more (or less) modifications**.  (we can regard the initial state dT[2] = T[2])\n\nBy maintaining ``dT[i] = T[i] - T[i-1]``, we have the following two merits:\n\n**First**, We can recover ``T[i]``by ``T[i] = dT[i] + dT[i-1] + ... + dT[2] = T[i] - T[i-1] + T[i-1] - T[i-2] + ... + T[3] - T[2] + T[2]``. \n\n**Second**, We can easily maintain ``dT[i]``for each pair ``(a, b)`` based on the 5 situations listed above.\n\nFor situation 1, we have ``dT[2] += 2``, which means we need 2 operations if we set both of ``a`` and ``b`` to 1 so that we achieve target sum 2.\n\nFor situation 2, we have ``dT[min(a, b)] -= 1``, because ``dT[min(a, b) + 1] = T[min(a, b) + 1] - T[min(a, b)]``, which means we need **one less operations** for pair ``(a, b)`` if we change the target sum from ``min(a, b)`` to ``min(a, b) + 1``.\n\nFor situation 3, it is similar to situation 2.\n\nFor situation 4, we have ``dT[a + b + 1] += 1``, because If we set the target sum as ``a+b``, then we need zero operations for pair ``(a, b)``. However if we change the target sum from ``a+b`` to ``a+b+1``, we need **one more operations**. \n\nFor situation 5, it is similar to situation 4.\n\nFinally, we just need to iterate over all the possible target sum in ``[2, 2 x limit]``to find the minimum ``T[i]``by simply accumulating over ``dT[i]``.\n\n**Time Complexity**: O(N + K)\n\n**Space Complexity**: O(K)\n\n```C++\nclass Solution {\npublic:\n    const int N = 100000;\n    int minMoves(vector<int>& nums, int limit) {\n        vector<int> dT(2 * N + 1, 0);   // dT[i] = T[i] - T[i-1]\n        \n        int n = nums.size(), res = INT_MAX;\n        for (int i = 0; i < n / 2; ++i) {\n            int a = nums[i], b = nums[n-1-i];\n            \n            dT[2] += 2;\n            dT[min(a, b) + 1] -= 1; \n            dT[a + b] -= 1;\n            dT[a + b + 1] += 1;\n            dT[max(a, b) + limit + 1] += 1;\n        }\n        \n        int curr = 0;\n        for (int t = 2; t <= limit * 2; ++t) {\n            curr += dT[t];\n            res = min(res, curr);\n        }\n        return res;\n    }\n};\n```\n\nOne more thing, I found many solutions in O(NlogN) are based on an assumptions that **the optimal solution must come from the pair sum in the given array**, which I found it is quite hard to prove and might fail in some subtle cases. I wonder if the assumptions is truly correct.
[]