Minimum Swaps to Group All 1's Together II Interview Question for Amazon

A swap is defined as taking two distinct positions in an array and swapping the values in them. A circular array is defined as an array where we consider the first element and the last element to be adjacent. Given a binary circular array <code>nums</code>, return the minimum number of swaps required to group all <code>1</code>'s present in the array together at any location.   Example 1: <pre> Input: nums = [0,1,0,1,1,0,0] Output: 1 Explanation: Here are a few of the ways to group all the 1's together: [0,0,1,1,1,0,0] using 1 swap. [0,1,1,1,0,0,0] using 1 swap. [1,1,0,0,0,0,1] using 2 swaps (using the circular property of the array). There is no way to group all 1's together with 0 swaps. Thus, the minimum number of swaps required is 1. </pre> Example 2: <pre> Input: nums = [0,1,1,1,0,0,1,1,0] Output: 2 Explanation: Here are a few of the ways to group all the 1's together: [1,1,1,0,0,0,0,1,1] using 2 swaps (using the circular property of the array). [1,1,1,1,1,0,0,0,0] using 2 swaps. There is no way to group all 1's together with 0 or 1 swaps. Thus, the minimum number of swaps required is 2. </pre> Example 3: <pre> Input: nums = [1,1,0,0,1] Output: 0 Explanation: All the 1's are already grouped together due to the circular property of the array. Thus, the minimum number of swaps required is 0. </pre>   Constraints: <ul> <li><code>1 <= nums.length <= 105</code></li> <li><code>nums[i]</code> is either <code>0</code> or <code>1</code>.</li> </ul>

Naive Solution

The naive solution would involve iterating through all possible subarrays of length ones (the number of 1s in the array) and counting the number of 0s in each subarray. The minimum number of 0s would then be the answer, as each 0 would need to be swapped out. This approach would have a time complexity of O(n^2), where n is the length of the array, due to the nested loops required to iterate through all possible subarrays.

Optimal Solution

A more efficient solution can be achieved using a sliding window approach. First, count the total number of 1s in the array. This represents the size of our window. Then, iterate through the array using a sliding window of that size, counting the number of 0s within each window. The minimum number of 0s encountered is the answer.

Code (Python)

def min_swaps(nums):
    ones = sum(nums)
    n = len(nums)
    if ones == 0 or ones == n:
        return 0
    
    min_zeros = float('inf')
    
    for i in range(n):
        zeros = 0
        for j in range(ones):
            if nums[(i + j) % n] == 0:
                zeros += 1
        min_zeros = min(min_zeros, zeros)
        
    return min_zeros

# Example Usage
nums1 = [0,1,0,1,1,0,0]
print(f"Input: {nums1}, Output: {min_swaps(nums1)}") # Output: 1

nums2 = [0,1,1,1,0,0,1,1,0]
print(f"Input: {nums2}, Output: {min_swaps(nums2)}") # Output: 2

nums3 = [1,1,0,0,1]
print(f"Input: {nums3}, Output: {min_swaps(nums3)}") # Output: 0

Code (Java)

class Solution {
    public int minSwaps(int[] nums) {
        int ones = 0;
        int n = nums.length;
        for (int num : nums) {
            ones += num;
        }

        if (ones == 0 || ones == n) {
            return 0;
        }

        int minZeros = Integer.MAX_VALUE;

        for (int i = 0; i < n; i++) {
            int zeros = 0;
            for (int j = 0; j < ones; j++) {
                if (nums[(i + j) % n] == 0) {
                    zeros++;
                }
            }
            minZeros = Math.min(minZeros, zeros);
        }

        return minZeros;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();

        int[] nums1 = {0, 1, 0, 1, 1, 0, 0};
        System.out.println("Input: [0,1,0,1,1,0,0], Output: " + sol.minSwaps(nums1)); // Output: 1

        int[] nums2 = {0, 1, 1, 1, 0, 0, 1, 1, 0};
        System.out.println("Input: [0,1,1,1,0,0,1,1,0], Output: " + sol.minSwaps(nums2)); // Output: 2

        int[] nums3 = {1, 1, 0, 0, 1};
        System.out.println("Input: [1,1,0,0,1], Output: " + sol.minSwaps(nums3)); // Output: 0
    }
}

Big(O) Run-time Analysis

The optimal solution has a time complexity of O(n), where n is the length of the array. The outer loop iterates through the array once, and the inner loop iterates ones times (where ones is the number of 1s in the array). In the worst case, ones could be equal to n, making the inner loop also O(n). Thus the dominant factor is the outer loop, making the overall time complexity O(n).

Big(O) Space Usage Analysis

The space complexity of the optimal solution is O(1), constant space. We only use a few extra variables to store the count of ones and the minimum number of zeros, regardless of the input array size.

Edge Cases

Empty array: If the input array is empty, the code should handle this gracefully. In the provided code, this case is implicitly handled because the loop will not execute, and the initial value of min_zeros (infinity) will be returned. However, it's good practice to explicitly check for this and return 0.
Array with all 0s or all 1s: If the array contains only 0s or only 1s, no swaps are needed. The provided code handles this efficiently with the check if ones == 0 or ones == n: return 0.
Large array: The code should handle very large arrays efficiently without causing memory issues or exceeding time limits. The O(n) time complexity and O(1) space complexity of the optimal solution make it suitable for large arrays.
Negative numbers: The problem statement specifies that the array contains only 0s and 1s. If the array could potentially contain negative numbers, input validation would be needed to ensure that only binary values are processed.
Circular array: The circular property is handled by using the modulo operator % when accessing array elements within the sliding window, ensuring that the window wraps around the array.