Thursday, July 12, 2012

Algorithm to move all ones(1's) in an array to end of the array - O(n) Solution

Problem:
Given an array which contains only 0's and 1's. Write an algorithm to move all the 1's in the array to end of the array in one traversal only. Avoid unnecessary swapping and using extra space.

Different version of this problem would be Dutch National Flag Problem, which is very common question in many interviews in initial stages. Above given problem is simplified version of 0, 1, 2 or Dutch Flag problem, where we are concerned only about moving 0's to initial parts of the given array. We keep track of index of zeroes(i.e. nothing but number of zeroes that we have encountered till now), whenever we find zero in the array we swap with this zero index that we have been tracking.

Solution:
Below code in C#, I think code itself is self explanatory. If not drop a comment please.

========================================================================

           int[] arr = { 1, 0, 1, 0, 1, 0, 1, 0, 1};


            int zeroIndex = 0;
            for (int i = 0; i < arr.Length; i++)
            {
                if (arr[i] == 0)
                {
                    if (i!= zeroIndex && arr[i] != arr[zeroIndex])
                    {
                        int temp = arr[i];
                        arr[i] = arr[zeroIndex];
                        arr[zeroIndex] = temp;
                    }
                        zeroIndex++;
                    
                }
            }


            for (int i = 0; i < arr.Length; i++)
            {
                Console.Write(arr[i]);
            }
========================================================================

No comments:

Post a Comment