Line sweep | Java | Explained
Code\n\nclass Solution {\n    public int minMoves(int[] nums, int limit) {\n        int n = nums.length;\n\n        // since limit>=nums[i], sum of pair lies in
# Code\n```\nclass Solution {\n    public int minMoves(int[] nums, int limit) {\n        int n = nums.length;\n\n        // since limit>=nums[i], sum of pair lies in [2,limit*2]\n        int[] arr = new int[2*limit+2];\n\n        /* Now we will calculate for each pair, number of moves required to get each sum in [2,limit*2]\n            current pair = [x,y]\n            for sum = x+y , 0 moves\n            minimum sum with one move = min(x,y)+1, so for all sum <min(x,y)+1 we need 2 moves\n            maximum sum with one move = max(x,y)+limit, so we need 1 moves for min(x,y)+1<=sum<=max(x,y)+limit\n            and for sum>max(x,y)+limit, we need 2 moves\n\n            for given pair, the number line gets divided as follows\n            2....min(x,y)+1....x+y.....max(x,y)+limit....limit*2\n        */\n\n        // One way, but too many redundant operations\n        // for(int i=0;i<n/2;i++){\n        //     int a = nums[i], b = nums[n-1-i];\n        //     // 2 moves for [2,Math.min(a,b)+1)\n        //     arr[2]+=2;\n        //     arr[Math.min(a,b)+1]-=2;\n        //     // 1 moves for [Math.min(a,b)+1,a+b)\n        //     arr[Math.min(a,b)+1]++;\n        //     arr[a+b]--;\n        //     // 1 moves for [a+b+1,Math.max(a,b)+limit]\n        //     arr[a+b+1]++;\n        //     arr[Math.max(a,b)+limit+1]--;\n        //     //2 moves for [Math.max(a,b)+limit+1,limit*2]\n        //     arr[Math.max(a,b)+limit+1]+=2;\n        //     arr[2*limit+1]-=2;\n        // }\n\n        // line sweep , moves needed goes from 2->1->0->1->2\n        // here the starting value is 0, so minimum value will go to -n in case of 2 moves for all n/2 pairs\n        // so initial sum value need to be kept equal to n\n        for(int i=0;i<n/2;i++){\n            int a = nums[i], b = nums[n-1-i];\n            arr[Math.min(a,b)+1]--;\n            arr[a+b]--;\n            arr[a+b+1]++;\n            arr[Math.max(a,b)+limit+1]++;\n        }\n\n        // if we calculate prefix sum now, then pre[i] tells total number of moves for pair sum i\n        // but we want minimum moves, so take minimum\n\n        int moves = n, ans = Integer.MAX_VALUE;\n        for(int i=2;i<=limit*2;i++){\n            moves+=arr[i];\n            ans = Math.min(ans,moves);\n        }\n\n        return ans;\n    }\n}\n```
['Java']