Beats 100% ✅ || Sliding Window 🔥 || Very Easy to understand for beginners 💯
Intuition\nTo summarize the question, we need to find the minimum number of moves for Dylan to pick exactly k ones from a binary array nums, with certain constr
## Intuition\nTo summarize the question, we need to find the minimum number of moves for Dylan to pick exactly k ones from a binary array nums, with certain constraints on allowed moves. Dylan can either convert zeros to ones or swap adjacent ones and zeros, subject to a maximum number of allowed changes.\n\n---\n\n## Approach\n1. First, determine the maximum number of consecutive ones in the array `(max_cons)`. This is crucial as it helps in optimizing Dylan\'s selection of ones.\n\n2. Check if Dylan can achieve the target number of ones (k) with the maximum allowed changes `(max_changes)`. If yes, return the minimum number of moves accordingly.\n\n3. If Dylan needs more ones than allowed by `max_changes`, implement a dynamic programming approach.\n\n4. Iterate through the indices of ones to find the optimal solution.\n\n5. Calculate the **cumulative difference between indices** to assess potential moves.\n\n6. Update the **minimum difference** based on the current configuration.\nFinally, return the **total minimum moves** required.\n\n---\n\n## Detailed Explanation\n- The function `minimumMoves` takes `three` arguments: \n    - `nums` (a list of binary numbers)\n    - `k` (the target number of ones Dylan needs to pick)\n    - `max_changes` (the maximum number of allowed changes)\n\n- We then convert the binary array `nums` is into a string `s` for easier manipulation.\n\n- Then we check if there are any **consecutive sequences** of ones in the array `nums` and identify  the maximum consecutive ones `(max_cons)` by checking if `"111"`, `"11"`, or `"1"` exists in the string representation. This is done to optimize the selection of ones by Dylan.\n\n- It\'s ensured that `max_cons` is not greater than `k`. **This is because Dylan can\'t pick more ones than there are in the array.**\n\n- If `max_changes` is enough to make up for the **difference between `k` and `max_cons`,** Dylan can achieve the target with the fewest moves. In this case, the function returns `(k - max_cons) * 2 + max(0, max_cons - 1)`. \n    - `(k - max_cons) * 2` represents the moves needed to convert zeros to ones\n    - `max(0, max_cons - 1)` represents the moves needed to swap ones and zeros within max_cons consecutive ones.\n\n- If `max_changes` is not enough, we calculate the minimum number of moves required.\n\n- Initialize `res` to `max_changes * 2`, representing the moves needed to convert zeros to ones.\n\n- Subtract `max_changes` from `k` to determine how many additional ones Dylan needs to pick `(k -= max_changes)`.\n\n- Creates a list of indices `idxes` where ones are present.\n\n- Calculate the middle point `(pmid)` considering the remaining required ones (k) and divide it by 2.\n\n- Iterate through the indices to find the optimal solution.\n\n    - Calculate the **cumulative difference** `(cdiff)` by summing the absolute differences between the indices of the ones.\n\n    - Update the **minimum difference** `(mdiff)` by comparing it with the cumulative difference.\n\n- Finally, add `mdiff` to `res` and returns the result.\n\n\n---\n\n![image.png](https://assets.leetcode.com/users/images/31a77eac-44e0-4f0f-a7ee-db193f1d157a_1710648200.406048.png)\n\n---\n\n### Time Complexity: `O(N)`\n### Space Complexity: `O(N)`\n\n---\n\n\n\n##### If you want the code in other languages, let me know in the comments below.\n###### I will update the post within one hour! Thanks :)\n\n---\n\n# Code\n``` python []\nclass Solution:\n    def minimumMoves(self, nums: List[int], k: int, max_changes: int) -> int:\n        s = "".join(map(str, nums))\n        if "111" in s:\n            max_cons = 3\n        elif "11" in s:\n            max_cons = 2\n        elif "1" in s:\n            max_cons = 1\n        else:\n            max_cons = 0\n\n        if max_cons > k:\n            max_cons = k\n        if max_changes >= k - max_cons:\n            return (k - max_cons) * 2 + max(0, max_cons - 1)\n        \n        res = max_changes * 2\n        k -= max_changes\n        idxes = [i for i in range(len(nums)) if nums[i]]\n        pmid = k // 2\n        left = 0\n        cdiff = mdiff = sum(abs(i - idxes[pmid]) for i in idxes[:k])\n        for right in range(k, len(idxes)):\n            cdiff -= idxes[pmid] - idxes[left]\n            left += 1\n            cdiff += idxes[right] - idxes[pmid + 1]\n            move_d = idxes[pmid + 1] - idxes[pmid]\n            cdiff += ((pmid + 1 - left) - (right - 1 - pmid)) * move_d\n            mdiff = min(mdiff, cdiff)\n            pmid += 1\n        res += mdiff\n        return res\n```\n\n\n### Also please  $${\\color{purple}upvote}$$, that motivates me! \n\n![66dabafc-1e25-4e05-b54d-4157c3ebe2af_1708833865.8845494.jpeg](https://assets.leetcode.com/users/images/b90c781a-c78a-4d5d-81e8-52c5f606e381_1710648260.6889465.jpeg)\n
['Math', 'Dynamic Programming', 'C', 'Sliding Window', 'Python', 'C++', 'Java', 'Python3']