O(n) | Sliding Window  | 2-ms Beats 100% Java | C++ | Python | Rust | Go | JavaScript
Appraoch 1\n# Intuition\n\nThis problem of finding the minimum number of swaps to group all 1\'s in a circular binary array presents a unique challenge due to i
# Appraoch 1\n# Intuition\n\nThis problem of finding the minimum number of swaps to group all 1\'s in a circular binary array presents a unique challenge due to its circular nature. The key insight is to recognize that we\'re essentially looking for a contiguous subarray of a specific length (equal to the total number of 1\'s) that contains the maximum number of 1\'s.\n\nGiven the circular nature of the array, we can visualize it as a ring. The optimal solution will be a segment of this ring that contains the most 1\'s. The number of swaps needed will be the difference between the total number of 1\'s and the number of 1\'s already in this optimal segment.\n\nThis problem can be efficiently solved using a sliding window technique, adapted for a circular array. The circular property allows us to consider all possible contiguous segments without explicitly handling different starting positions.\n\n# Approach\n\nThe solution employs a two-pointer technique combined with a sliding window, adapted for a circular array.\n1. **Count Total Ones**: \n   - We start by iterating through the array to count the total number of 1\'s.\n   - This count serves two purposes:\n     a) It helps us handle edge cases efficiently.\n     b) It determines the size of our sliding window.\n   - The count is crucial because it represents the size of the group we\'re trying to form.\n\n2. **Handle Edge Cases**:\n   - If there are no 1\'s in the array, or if all elements are 1\'s, no swaps are needed.\n   - We can immediately return 0 in these cases, saving unnecessary computations.\n\n3. **Initialize Window**:\n   - We create an initial window of size `totalOnes`.\n   - We count the number of 1\'s in this initial window.\n   - This window represents our first potential segment where all 1\'s could be grouped.\n\n4. **Slide the Window**:\n   - We use two pointers to slide the window around the circular array.\n   - The sliding process involves:\n     a) Removing the element at the start of the window.\n     b) Adding the next element at the end of the window.\n   - We use the modulo operator to wrap around the array, simulating its circular nature.\n   - This clever use of the modulo operator allows us to handle the circular property without creating a duplicate array or using extra space.\n\n5. **Track Maximum**:\n   - As we slide the window, we keep track of the maximum number of 1\'s seen in any window configuration.\n   - This maximum represents the largest group of 1\'s that already exist contiguously in the array.\n   - Updating this maximum is done in constant time at each step.\n\n6. **Calculate Minimum Swaps**:\n   - After sliding the window through all positions, we know the maximum number of 1\'s that exist contiguously in the array.\n   - The minimum number of swaps is the difference between the total number of 1\'s and this maximum.\n   - This difference represents the number of 1\'s that need to be moved to create a contiguous group of all 1\'s.\n\n\n# Complexity\n\n- **Time complexity: O(n)**\n  - We perform two main passes through the array:\n    1. First pass to count the total number of 1\'s: O(n)\n    2. Second pass to slide the window: O(n)\n  - All operations inside the loops are constant time.\n  - Therefore, the overall time complexity is O(n), where n is the length of the input array.\n  - This linear time complexity is optimal for this problem, as we need to examine each element at least once.\n\n- **Space complexity: O(1)**\n  - We only use a constant amount of extra space:\n    - `totalOnes`: integer\n    - `currentOnes`: integer\n    - `maxOnes`: integer\n    - Loop variables\n  - No additional data structures are used.\n  - The space complexity remains constant regardless of the input size.\n  - This constant space usage is a significant advantage of this approach, making it memory-efficient even for very large inputs.\n\n### Code\n```Java []\nclass Solution {\n    public int minSwaps(int[] nums) {\n        int n = nums.length;\n        int totalOnes = 0;\n\n        // Count total number of 1\'s\n        for (int num : nums) {\n            totalOnes += num;\n        }\n\n        // Edge cases\n        if (totalOnes == 0 || totalOnes == n) return 0;\n\n        int currentOnes = 0;\n\n        // Count 1\'s in the first window of size totalOnes\n        for (int i = 0; i < totalOnes; i++) {\n            currentOnes += nums[i];\n        }\n\n        int maxOnes = currentOnes;\n\n        // Use two pointers to slide the window\n        for (int i = 0; i < n; i++) {\n            currentOnes -= nums[i];\n            currentOnes += nums[(i + totalOnes) % n];\n            maxOnes = Math.max(maxOnes, currentOnes);\n        }\n\n        return totalOnes - maxOnes;\n    }\n}\n\n```\n```C++ []\nclass Solution {\npublic:\n    int minSwaps(vector<int>& nums) {\n        int n = nums.size();\n        int totalOnes = 0;\n        \n        // Count total number of 1\'s\n        for (int num : nums) {\n            totalOnes += num;\n        }\n        \n        // Edge cases\n        if (totalOnes == 0 || totalOnes == n) return 0;\n        \n        int currentOnes = 0;\n        \n        // Count 1\'s in the first window of size totalOnes\n        for (int i = 0; i < totalOnes; i++) {\n            currentOnes += nums[i];\n        }\n        \n        int maxOnes = currentOnes;\n        \n        // Use two pointers to slide the window\n        for (int i = 0; i < n; i++) {\n            currentOnes -= nums[i];\n            currentOnes += nums[(i + totalOnes) % n];\n            maxOnes = max(maxOnes, currentOnes);\n        }\n        \n        return totalOnes - maxOnes;\n    }\n};\n\n```\n```Python []\nclass Solution:\n    def minSwaps(self, nums: List[int]) -> int:\n        n = len(nums)\n        total_ones = sum(nums)\n        \n        # Edge cases\n        if total_ones == 0 or total_ones == n:\n            return 0\n        \n        current_ones = sum(nums[:total_ones])\n        max_ones = current_ones\n        \n        # Use two pointers to slide the window\n        for i in range(n):\n            current_ones -= nums[i]\n            current_ones += nums[(i + total_ones) % n]\n            max_ones = max(max_ones, current_ones)\n        \n        return total_ones - max_ones\n\n```\n```Go []\nfunc minSwaps(nums []int) int {\n    n := len(nums)\n    totalOnes := 0\n    \n    // Count total number of 1\'s\n    for _, num := range nums {\n        totalOnes += num\n    }\n    \n    // Edge cases\n    if totalOnes == 0 || totalOnes == n {\n        return 0\n    }\n    \n    currentOnes := 0\n    \n    // Count 1\'s in the first window of size totalOnes\n    for i := 0; i < totalOnes; i++ {\n        currentOnes += nums[i]\n    }\n    \n    maxOnes := currentOnes\n    \n    // Use two pointers to slide the window\n    for i := 0; i < n; i++ {\n        currentOnes -= nums[i]\n        currentOnes += nums[(i + totalOnes) % n]\n        if currentOnes > maxOnes {\n            maxOnes = currentOnes\n        }\n    }\n    \n    return totalOnes - maxOnes\n}\n\n```\n```Rust []\nimpl Solution {\n    pub fn min_swaps(nums: Vec<i32>) -> i32 {\n        let n = nums.len();\n        let total_ones = nums.iter().sum::<i32>();\n        \n        // Edge cases\n        if total_ones == 0 || total_ones as usize == n {\n            return 0;\n        }\n        \n        let mut current_ones = nums.iter().take(total_ones as usize).sum::<i32>();\n        let mut max_ones = current_ones;\n        \n        // Use two pointers to slide the window\n        for i in 0..n {\n            current_ones -= nums[i];\n            current_ones += nums[(i + total_ones as usize) % n];\n            max_ones = max_ones.max(current_ones);\n        }\n        \n        total_ones - max_ones\n    }\n}\n```\n```JavaScript []\n/**\n * @param {number[]} nums\n * @return {number}\n */\nvar minSwaps = function(nums) {\n    const n = nums.length;\n    const totalOnes = nums.reduce((sum, num) => sum + num, 0);\n    \n    // Edge cases\n    if (totalOnes === 0 || totalOnes === n) return 0;\n    \n    let currentOnes = nums.slice(0, totalOnes).reduce((sum, num) => sum + num, 0);\n    let maxOnes = currentOnes;\n    \n    // Use two pointers to slide the window\n    for (let i = 0; i < n; i++) {\n        currentOnes -= nums[i];\n        currentOnes += nums[(i + totalOnes) % n];\n        maxOnes = Math.max(maxOnes, currentOnes);\n    }\n    \n    return totalOnes - maxOnes;\n};\n\n```\n\n\n\n---\n\n\n\n# Approach 2\n\n# Intuition\n\nThe circular nature of the array suggests that we need to consider all possible contiguous subarrays, including those that wrap around the end of the array.\n\nThe key insight is that if we can efficiently calculate the number of 1\'s in any contiguous subarray of a given length, we can determine the minimum number of swaps needed. This leads us to consider using a cumulative sum approach, which allows for constant-time queries of subarray sums.\n\n# Approach\n\n1. **Handling Circularity**: To address the circular nature of the array, we create a doubled array by concatenating the original array with itself. This allows us to consider all possible contiguous subarrays, including those that wrap around the end of the original array.\n\n2. **Cumulative Sum Array**: We construct a cumulative sum array, where each element represents the sum of all elements up to that point in the doubled array. This allows us to calculate the sum of any subarray in constant time.\n\n3. **Window Size**: The optimal grouping of 1\'s will have a size equal to the total number of 1\'s in the array. We calculate this total as our window size.\n\n4. **Checking All Windows**: We iterate through all possible windows of the calculated size, using the cumulative sum array to efficiently determine the number of 1\'s in each window.\n\n5. **Calculating Swaps**: The number of swaps needed for each window is the difference between the total number of 1\'s and the number of 1\'s already in the window. The minimum of these differences across all windows is our answer.\n\nStep-by-step breakdown of the algorithm:\n\n1. Count the total number of 1\'s in the input array.\n2. Create a doubled array by concatenating the input array with itself.\n3. Construct a cumulative sum array from the doubled array.\n4. Iterate through all possible windows of size equal to the total number of 1\'s.\n5. For each window, calculate the number of 1\'s it contains using the cumulative sum array.\n6. Keep track of the maximum number of 1\'s found in any window.\n7. Return the difference between the total number of 1\'s and the maximum found in any window.\n\n# Complexity\n\n- **Time complexity: O(n)**\n  - Counting the total number of 1\'s: O(n)\n  - Creating the doubled array: O(n)\n  - Constructing the cumulative sum array: O(n)\n  - Iterating through all windows: O(n)\n  - All other operations are constant time.\n  \n  Where n is the length of the input array. Despite the nested loops, we only perform a constant number of operations for each element of the original array.\n\n- **Space complexity: O(n)**\n  - The doubled array: O(n)\n  - The cumulative sum array: O(n)\n  - All other variables use constant space.\n  \n  Where n is the length of the input array. We use linear extra space primarily for the doubled array and the cumulative sum array.\n\n\n### Code \n\n\n```Java []\n\nclass Solution {\n    public int minSwaps(int[] nums) {\n        int n = nums.length;\n        int totalOnes = 0;\n\n        // Count total number of 1\'s and create a doubled array\n        int[] doubledNums = new int[2 * n];\n        for (int i = 0; i < n; i++) {\n            totalOnes += nums[i];\n            doubledNums[i] = doubledNums[i + n] = nums[i];\n        }\n\n        // Edge cases\n        if (totalOnes == 0 || totalOnes == n) return 0;\n\n        // Create cumulative sum array\n        int[] cumulativeSum = new int[2 * n + 1];\n        for (int i = 0; i < 2 * n; i++) {\n            cumulativeSum[i + 1] = cumulativeSum[i] + doubledNums[i];\n        }\n\n        int maxOnesInWindow = 0;\n\n        // Check all possible windows of size totalOnes\n        for (int i = 0; i <= n; i++) {\n            int onesInWindow = cumulativeSum[i + totalOnes] - cumulativeSum[i];\n            maxOnesInWindow = Math.max(maxOnesInWindow, onesInWindow);\n        }\n\n        return totalOnes - maxOnesInWindow;\n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    int minSwaps(vector<int>& nums) {\n        int n = nums.size();\n        int totalOnes = 0;\n        \n        // Count total number of 1\'s and create a doubled array\n        vector<int> doubledNums(2 * n);\n        for (int i = 0; i < n; i++) {\n            totalOnes += nums[i];\n            doubledNums[i] = doubledNums[i + n] = nums[i];\n        }\n        \n        // Edge cases\n        if (totalOnes == 0 || totalOnes == n) return 0;\n        \n        // Create cumulative sum array\n        vector<int> cumulativeSum(2 * n + 1, 0);\n        for (int i = 0; i < 2 * n; i++) {\n            cumulativeSum[i + 1] = cumulativeSum[i] + doubledNums[i];\n        }\n        \n        int maxOnesInWindow = 0;\n        \n        // Check all possible windows of size totalOnes\n        for (int i = 0; i <= n; i++) {\n            int onesInWindow = cumulativeSum[i + totalOnes] - cumulativeSum[i];\n            maxOnesInWindow = max(maxOnesInWindow, onesInWindow);\n        }\n        \n        return totalOnes - maxOnesInWindow;\n    }\n};\n\n```\n```Python []\nclass Solution:\n    def minSwaps(self, nums: List[int]) -> int:\n        n = len(nums)\n        total_ones = sum(nums)\n        \n        # Edge cases\n        if total_ones == 0 or total_ones == n:\n            return 0\n        \n        # Create doubled array and cumulative sum\n        doubled_nums = nums + nums\n        cumulative_sum = [0] + list(accumulate(doubled_nums))\n        \n        max_ones_in_window = 0\n        \n        # Check all possible windows of size total_ones\n        for i in range(n + 1):\n            ones_in_window = cumulative_sum[i + total_ones] - cumulative_sum[i]\n            max_ones_in_window = max(max_ones_in_window, ones_in_window)\n        \n        return total_ones - max_ones_in_window\n\n\n```\n```Go []\nfunc minSwaps(nums []int) int {\n    n := len(nums)\n    totalOnes := 0\n    \n    // Count total number of 1\'s and create a doubled array\n    doubledNums := make([]int, 2*n)\n    for i := 0; i < n; i++ {\n        totalOnes += nums[i]\n        doubledNums[i] = nums[i]\n        doubledNums[i+n] = nums[i]\n    }\n    \n    // Edge cases\n    if totalOnes == 0 || totalOnes == n {\n        return 0\n    }\n    \n    // Create cumulative sum array\n    cumulativeSum := make([]int, 2*n+1)\n    for i := 0; i < 2*n; i++ {\n        cumulativeSum[i+1] = cumulativeSum[i] + doubledNums[i]\n    }\n    \n    maxOnesInWindow := 0\n    \n    // Check all possible windows of size totalOnes\n    for i := 0; i <= n; i++ {\n        onesInWindow := cumulativeSum[i+totalOnes] - cumulativeSum[i]\n        if onesInWindow > maxOnesInWindow {\n            maxOnesInWindow = onesInWindow\n        }\n    }\n    \n    return totalOnes - maxOnesInWindow\n}\n\n```\n```Rust []\nimpl Solution {\n    pub fn min_swaps(nums: Vec<i32>) -> i32 {\n        let n = nums.len();\n        let total_ones = nums.iter().sum::<i32>();\n        \n        // Edge cases\n        if total_ones == 0 || total_ones == n as i32 {\n            return 0;\n        }\n        \n        // Create doubled array and cumulative sum\n        let doubled_nums: Vec<i32> = nums.iter().chain(nums.iter()).cloned().collect();\n        let mut cumulative_sum = vec![0; 2 * n + 1];\n        for i in 0..2*n {\n            cumulative_sum[i + 1] = cumulative_sum[i] + doubled_nums[i];\n        }\n        \n        let mut max_ones_in_window = 0;\n        \n        // Check all possible windows of size total_ones\n        for i in 0..=n {\n            let ones_in_window = cumulative_sum[i + total_ones as usize] - cumulative_sum[i];\n            max_ones_in_window = max_ones_in_window.max(ones_in_window);\n        }\n        \n        total_ones - max_ones_in_window\n    }\n}\n\n```\n```JavaScript []\n/**\n * @param {number[]} nums\n * @return {number}\n */\nvar minSwaps = function(nums) {\n    const n = nums.length;\n    const totalOnes = nums.reduce((sum, num) => sum + num, 0);\n    \n    // Edge cases\n    if (totalOnes === 0 || totalOnes === n) return 0;\n    \n    // Create doubled array and cumulative sum\n    const doubledNums = [...nums, ...nums];\n    const cumulativeSum = [0];\n    for (let i = 0; i < 2 * n; i++) {\n        cumulativeSum[i + 1] = cumulativeSum[i] + doubledNums[i];\n    }\n    \n    let maxOnesInWindow = 0;\n    \n    // Check all possible windows of size totalOnes\n    for (let i = 0; i <= n; i++) {\n        const onesInWindow = cumulativeSum[i + totalOnes] - cumulativeSum[i];\n        maxOnesInWindow = Math.max(maxOnesInWindow, onesInWindow);\n    }\n    \n    return totalOnes - maxOnesInWindow;\n};\n\n```
['Array', 'Sliding Window', 'C++', 'Java', 'Go', 'Python3', 'Rust', 'JavaScript']