Python O(n+limit) line sweep with explanation
The idea is to built up the moves table and then scan for the minimum value.\nFirst see an naive O(n.limit) approach:\n\npython\ndef solution(nums, limit):\n\tn
The idea is to built up the `moves` table and then scan for the minimum value.\nFirst see an naive `O(n.limit)` approach:\n\n```python\ndef solution(nums, limit):\n\tn = len(nums)\n\tmoves = [0] * (limit*2+1)\n\tfor i in range(n//2):\n\t\ta, b = nums[i], nums[-i-1]\n\t\tpairs.append(a+b)\n\t\tfor j in range(2, limit*2+1):\n\t\t\tif j <= min(a,b):\n\t\t\t\tmoves[j] += 2\n\t\t\telif j <= max(a,b) + limit:\n\t\t\t\tmoves[j] += 1\n\t\t\telse:\n\t\t\t\tmoves[j] += 2\n\t\t\tif j == pairs[-1]:\n\t\t\t\tmoves[j] -= 1\n\n\treturn min(moves[2:])\n```\n\nThen improve the time complexity with addtional storage.\n```python\ndef solution(nums, limit):\n\tn = len(nums)\n\tsums, maxs, mins = ([0] * (limit*2+1) for _ in range(3))\n\tfor i in range(n//2):\n\t\ta, b = nums[i], nums[-i-1]\n\t\tsums[a+b] += 1\n\t\tmins[min(a,b)] += 1\n\t\tif max(a,b)+limit+1 <= limit*2:\n\t\t\tmaxs[max(a,b)+limit+1] += 1\n\n\tfor v in range(2, limit*2+1):\n\t\tmaxs[v] += maxs[v-1]\n\n\tfor v in range(limit*2, 2, -1):\n\t\tmins[v-1] += mins[v]\n\n\tmoves = [n//2] * (limit*2+1)\n\tfor v in range(2, limit*2+1):\n\t\tmoves[v] -= sums[v]\n\t\tmoves[v] += maxs[v]\n\t\tmoves[v] += mins[v]\n\n\treturn min(moves[2:])\n```\n
['Python']