Binary Array Minimum Adjacent Swaps Required To Sort Binary Array




public class BinaryArrayMinimumSwap {
    public static int minswaps(int arr[], int n)
    {
        int count = 0;
        int numUnplacedZeros = 0;

        for (int index = n - 1; index >= 0; index--)
        {
            if (arr[index] == 0)
                numUnplacedZeros += 1;
            else
                count += numUnplacedZeros;
        }
        return count;
    }

    // Driver Code
    public static void main(String[] args)
    {
        int[] arr = { 0, 0, 1, 0, 1, 0, 1, 1 };
        System.out.println(minswaps(arr, 8));

        //Space Optimized Solution: An auxiliary space is not needed.
        // We just need to start reading the list from the back and keep track of number
        // of zeros we encounter.
        // If we encounter a 1 the number of zeros is the number of swaps needed
        // to put the 1 in correct place.
        //Time Complexity: O(n)
        //Auxiliary Space: O(1)
    }
}


No comments:

Post a Comment