Java/Python/Typescript Sliding window technique Time complexity: O(n)/Space complexity: O(1)
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\nThe approach to solving this problem involves using a sliding window tech
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nThe approach to solving this problem involves using a sliding window technique to find the minimum number of swaps required to group all the ones together in a circular binary array.\n\n1. First, count the total number of ones in the given array, which will help us determine the size of the window required to group all the ones together.\n\n2. Initialize variables:\n   - `totalOnes`: The total number of ones in the array.\n   - `n`: The length of the input array.\n   - `startIndex` and `endIndex`: Pointers to define the current window.\n   - `currentWindowOnes`: Count of ones in the current window.\n   - `swaps`: Initialize it with the maximum possible swaps (`n`).\n\n3. Start a while loop with `endIndex` initially at 0. The loop will run until `endIndex` reaches `2 * n`, considering the circular property of the array.\n\n4. Inside the loop:\n   - If `endIndex` is less than `totalOnes`, we are in the first window of size `totalOnes`. Check if the element at `nums[endIndex]` is 1. If it is, increment `currentWindowOnes`.\n   - Increment `endIndex` to expand the current window.\n   - Calculate the number of swaps required to move ones outside of the current window (`swaps = totalOnes - currentWindowOnes`).\n\n5. Once `endIndex` is greater than or equal to `totalOnes`, we start moving the window. In this part:\n   - Check if the element at `nums[startIndex % n]` is 1. If it is, decrement `currentWindowOnes` as we are moving the window away from a 1.\n   - Check if the element at `nums[endIndex % n]` is 1. If it is, increment `currentWindowOnes` as we are moving the window towards a 1.\n   - Increment both `startIndex` and `endIndex` to move the window.\n   - Update `swaps` with the minimum swaps required to group the ones within the current window using `Math.min(swaps, totalOnes - currentWindowOnes)`.\n\n6. The loop continues until `endIndex` reaches `2 * n`, evaluating swaps for each window along the way.\n\n7. Finally, return the minimum value of `swaps`, which represents the minimum number of swaps required to group all the ones together in the circular array.\n\n\n# Complexity\n- Time complexity:\nThe time complexity of the provided solution is O(n), where n is the length of the input array `nums`. Here\'s a breakdown of the time complexity:\n\n1. **Counting Ones:** In the initial loop where we count the total number of ones in the array, we iterate through the entire `nums` array once. This takes O(n) time.\n\n2. **Sliding Window:** The main part of the algorithm uses a sliding window approach to find the minimum swaps. This part iterates through the entire circular array once. The while loop runs until `endIndex` reaches `2 * n`. Since each iteration of the while loop processes one element, it runs in O(n) time as well.\n\nTherefore, the overall time complexity of the algorithm is dominated by the O(n) loop, making it O(n) in total.\n\n- Space complexity:\nThe space complexity of the provided solution is O(1), meaning it uses a constant amount of additional space regardless of the size of the input array. Here\'s why:\n\n1. **Constant Variables:** The algorithm uses a fixed number of variables to store information (e.g., `totalOnes`, `n`, `startIndex`, `endIndex`, `currentWindowOnes`, `swaps`). These variables do not depend on the size of the input array, so they contribute only a constant amount of space.\n\n2. **No Additional Data Structures:** The algorithm does not use any additional data structures like arrays, lists, or sets to store data. It only uses simple variables for calculations.\n\nSince the space used by the algorithm remains constant (it doesn\'t grow with the input size), the space complexity is O(1).\n\n# Code\n```java []\nclass Solution {\n    public int minSwaps(int[] nums) {\n        int totalOnes = 0;\n        for (int one : nums) {\n            if (one == 1) totalOnes++;\n        }\n\n        int n = nums.length,\n                startIndex = 0,\n                endIndex = 0,\n                currentWindowOnes = 0,\n                swaps = n;\n\n        while (endIndex < 2 * n) {\n\n            if (endIndex < totalOnes) {\n                if (nums[endIndex] == 1) currentWindowOnes++;\n\n                endIndex++;\n                swaps = totalOnes - currentWindowOnes;\n\n            } else {\n                if (nums[startIndex % n] == 1) currentWindowOnes--;\n\n                if (nums[endIndex % n] == 1) currentWindowOnes++;\n\n                startIndex++;\n                endIndex++;\n\n                swaps = Math.min(swaps, totalOnes - currentWindowOnes);\n            }\n\n        }\n\n        return swaps;\n    }\n}\n```\n```python []\nclass Solution(object):\n    def minSwaps(self, nums):\n        """\n        :type nums: List[int]\n        :rtype: int\n        """\n        total_ones = 0\n        for one in nums:\n            if one == 1:\n                total_ones += 1\n\n        n = len(nums)\n        start_index = 0\n        end_index = 0\n        current_window_ones = 0\n        swaps = n\n\n        while end_index < 2 * n:\n\n            if end_index < total_ones:\n                if nums[end_index] == 1:\n                    current_window_ones += 1\n\n                end_index += 1\n                swaps = total_ones - current_window_ones\n            else:\n                if nums[start_index % n] == 1:\n                    current_window_ones -= 1\n\n                if nums[end_index % n] == 1:\n                    current_window_ones += 1\n\n                start_index += 1\n                end_index += 1\n\n                swaps = min(swaps, total_ones - current_window_ones)\n\n        return swaps\n```\n```typescript []\nfunction minSwaps(nums: number[]): number {\n    let totalOnes: number = 0;\n    for (const one of nums) {\n        if (one == 1) totalOnes++;\n    }\n\n    let n = nums.length,\n        startIndex = 0,\n        endIndex = 0,\n        currentWindowOnes = 0,\n        swaps = n;\n\n    while (endIndex < 2 * n) {\n\n        if (endIndex < totalOnes) {\n            if (nums[endIndex] == 1) currentWindowOnes++;\n\n            endIndex++;\n            swaps = totalOnes - currentWindowOnes;\n\n        } else {\n            if (nums[startIndex % n] == 1) currentWindowOnes--;\n\n            if (nums[endIndex % n] == 1) currentWindowOnes++;\n\n            startIndex++;\n            endIndex++;\n\n            swaps = Math.min(swaps, totalOnes - currentWindowOnes);\n        }\n\n    }\n\n    return swaps;\n}\n```\n\n
['Python', 'Java', 'TypeScript']