[JavaScript] Simple solution with prefix sum + sliding window, beat 100%
Approach\nThis solution combines prefix sum and sliding window techniques to efficiently find the optimal way to collect ones.\nThe prefix sum array allows quic
# Approach\nThis solution combines prefix sum and sliding window techniques to efficiently find the optimal way to collect ones.\nThe prefix sum array allows quick calculation of distances for any range of ones, while the sliding window approach systematically evaluates different groupings.\nThe key insight is that the best solution always involves collecting a contiguous group of ones and using maxChanges for the rest. This allows us to focus our search on specific configurations.\nBy considering various group sizes and positions, we balance collecting existing ones with creating new ones via maxChanges. This approach efficiently finds the global optimum without exhaustive searching\n\n# Steps\n1. We start by creating a prefix sum array A of the indices where nums[i] > 0. This allows us to quickly calculate the sum of indices for any range. \n\n2. We calculate n, which is the number of ones in the original array, and m, which is the minimum number of ones we need to collect directly (not using maxChanges).\n\n3. We initialize res to the maximum safe integer value.\n\n4. We then iterate through possible numbers of ones to collect directly (l). We consider values from m up to the minimum of:\n    - The total number of ones available (n)\n    - m + 3 (as collecting more than 3 additional ones directly is never optimal)\n    - The total number of ones we need to collect (k)\n    \n5. For each l, we try all possible starting positions i.\n\n6. For each configuration, we calculate the cost:\n    - We find the midpoints mid1 and mid2 of the range.\n    - We calculate the cost as the difference between the sum of distances to the right of the midpoint and the sum of distances to the left of the midpoint.\n    - We add the cost of creating and collecting the remaining ones using maxChanges.\n\n7. We update res with the minimum cost found.\n\n8. Finally, we return the minimum cost.\n\n# Complexity\n- Time complexity: O(n * k), where n is the length of the input array. In the worst case, we might iterate through all positions for each value of l.\n\n- Space complexity: O(n), for storing the prefix sum array A.\n\n# Code\n```\n/**\n * @param {number[]} nums\n * @param {number} k\n * @param {number} maxChanges\n * @return {number}\n */\nvar minimumMoves = function(nums, k, maxChanges) {\n    // Create a prefix sum array of indices where nums[i] > 0\n    const A = [0];\n    for (let i = 0; i < nums.length; i++) {\n        if (nums[i] > 0) {\n            A.push(A[A.length - 1] + i);\n        }\n    }\n\n    const n = A.length - 1;\n    const m = Math.max(0, k - maxChanges);\n    let res = Number.MAX_SAFE_INTEGER;\n\n    // Iterate through possible numbers of ones to collect directly\n    for (let l = m; l <= Math.min(n, Math.min(m + 3, k)); l++) {\n        // Try all possible starting positions\n        for (let i = 0; i <= n - l; i++) {\n            const mid1 = i + Math.floor(l / 2);\n            const mid2 = i + l - Math.floor(l / 2);\n            // Calculate cost for this configuration\n            const cur = A[i + l] - A[mid2] - (A[mid1] - A[i]);\n            // Update minimum cost\n            res = Math.min(res, cur + (k - l) * 2);\n        }\n    }\n\n    return res;\n};\n```
['JavaScript']