Line Sweep for the win!! | Beats 93 %
Intuition\n Describe your first thoughts on how to solve this problem. \nA very good post on line sweep : link\n\n# Complexity\n- Time complexity:\n Add your ti
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nA very good post on line sweep : [link](https://leetcode.com/discuss/study-guide/2166045/line-sweep-algorithms)\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(limit+max(A_i))$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(limit+max(A_i))$$\n# Code\n```cpp []\nclass Solution {\npublic:\n    int minMoves(vector<int>& A, int limit) {\n        int MAX = 2 + limit + *max_element(begin(A), end(A));\n\n        vector<int> line(MAX, 0), cnt(MAX, 0);\n        int n=A.size();\n        for (int i=0 ; i<n/2 ; i++) {\n            cnt[A[i] + A[n-1-i]] += 1;\n            int mn = 1+min(A[i], A[n-1-i]);\n            int mx = limit+max(A[i], A[n-1-i]);\n            line[mn] += 1;\n            line[mx+1] -= 1;\n        }\n\n        for (int i=1 ; i<MAX ; i++)\n            line[i] += line[i-1];\n        int ans=n;\n        for (int poss=2 ; poss<MAX ; poss++)\n            ans = min(ans, n-line[poss]-cnt[poss]);\n        return ans;\n    }\n};\n\nstatic int io_opt = []() {\n  std::ios::sync_with_stdio(false);\n  return 0;\n}();\n```
['C++']