CareerCup

Consider Red =0 and blue =1, so the question becomes:
Given an array of 0 and 1, sort them.

1) Start two pointers, p0 starts at 0, p0++ until the first 1, stop.
2) p1 starts at p0 + 1, if *p1 == 0, then swap *p0 and *p1, followed by p0++
if *p1== 1, keep p1++

Make sure check all boundary cases.

Time O(N), Space O(1)

balls can be arranged in-place only by just swapping:
a[] -- array containing balls
n is the length of the array
0 -- blue color ball
1 -- red color ball
int partition(int *a,int n){
j=n-1
for(i=1;i<=j;i++){
if(a[i]!=a[i-1]){
while((a[j]==a[i])&&(j>i)){
j--;
}
if(i<j){
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
else{
break; //break the for loop, reached a point where balls are of same color on both the sides.
}
if(i==n-1)
return 0;
else return i;

Time complexity -- o(n) each ball is check for once only.
Spac complexity o(1) no extra memory is used.

Pankaj, if you have a while loop within a for loop, as you do in your solution, is the time complexity still O(n)?

Considering Red and blue to be 0 and 1... i just wrote the function. So pls comment on the logic

void swap(int *a, int *b);
int arrBalls(int array[], int len)
{
int p0 = 0;
int p1 = len -1;
while(array[p0] == 0)
p0++;
while(array[p1] == 1)
p1--;
if(p0 == len || p1 == -1)
return 0;

while(p0<p1){
swap(&a[p0], &a[p1]);
while(array[p0] == 0)
p0++;
while(array[p1] == 1)
p1--;
};
return p0;
}
void swap(int *a, int *b)
{
if(*a != *b){
*a = *a^*b;
*b = *a^*b;
*a = *a^*b;
}
}

Another approach to this problem could be :
count1= Count the number of red balls
count2= Number of blue balls= Total - number of red balls
From start of the array till count1
Over write the contents with red balls

From count1 till count1+count2
Over write the contents with blue balls

Complexity will be O(n)+ O(n)= O(n)
No extra memory used

@ananymous
consider RED=0, BLUE=1
sequence is
0111100000
then your algo will do 5 swap to bring it to 00000011111

but rather efficient way will be 11111000000 // 1 swap
-----
so, why not do like this
1. do a full scan, count no of red/blue
2. another scan and check, red-first or blue-first, which will take less swap
3. then follow any 0(n) algo of keeping two pointers and swap, when mismatch

still it's O(n) only...

Comments ?

That's the partition part of quick sort.
Add a pivot Yellow to the end, and assume that Red<Yellow<Blue;
Run one pass of partition, it's done.
BTW, you don't really need to move the pivot.

Another approach to this problem. I have made a small assumption instead of red and blue balls we have odd and even numbers. Logic remains the same anyway. Total complexity is O(n)

int findNextEven(int** arr,int size, int even)
{
// Start from the right of the list and return the next even number
int i=0;
for(i=even;i>=0;i--)
{
if(*(*arr+i)%2==0)
return i;
}
return -1;
}

int findNextOdd(int** arr,int size, int odd)
{
// Starts from the left of the list and return the next odd number.
int i=0;
for(i=odd;i<=size;i++)
{
if(*(*arr+i)%2!=0)
return i;
}
return -1;
}

void partition(int* arr, int size)
{
int i=0,odd=0,even=size-1,temp=-1,odd_temp=-1,even_temp=-1;

while(true)
{
// Get the left most odd number and the right most even number
odd= findNextOdd(&arr,size,odd);
even= findNextEven(&arr,size,even);

// If either of the 2 are -1 that means the list is already partitioned
if(odd==-1|| even==-1)
{

return;
}
else
{
temp= arr[odd];
arr[odd]=arr[even];
arr[even]= temp;
odd++;
even--;
}
}

}

Once this list is partitioned scan the list for the first even number and return. this is where the list is partitioned .

I agree with Anon, this is an implementation of the Selection Rank algorithm (variant of quicksort). It is in-place (but unstable - if there is satellite data involved, the order of equal elements are not preserved). Time complexity is O(n)

The problem is simple, dont need to complicate with different loops. The approach and solution the interviewer look for is simplycity.

a = 0, b = n-1;
while(a != b) {
if(arr[a] == bule && arr[b] == b) swap(a, b)
else {if(arr[a] == blue) a++;if(arr[b] == red) b--;}
}
if (a == b == n-1) return 0;
return a;

The problem with nested loops, even though the algorithm is O(n) is we got to check the bounds at the end of ech embedded loops to make sure they are not out of bounds.
And this complicates the solution unnecessarily. so take simple approach as explined by authors like Gries to construct the solution with gaurds and invariance.

unsigned partition(Ball aBalls[],unsigned cBalls)
{
    if(aBalls && cBalls>0)
    {
        int indexRed=0;
        int indexBlue=cBalls-1;
        
        while(true)
        {
            while(aBalls[indexRed]==Red && indexRed<cBalls-1)
            {
                indexRed++;
            }
            
            while(aBalls[indexBlue]==Blue && indexBlue>0)
            {
                indexBlue--;
            }
            
            if(indexRed < indexBlue)
            {
                aBalls[indexRed]=Red;
                aBalls[indexBlue]=Blue;
            }
            else
            {
                break;
            }
        }
        
        if(indexBlue==0)
            return 0;
        else
        if(indexBlue==cBalls-1)
            return 0;
        else
            return indexBlue+1;
    }
    return -1;
}

Let's represent blue balls by 0 and red balls by 1. The you can just use a variation of dutch national flag algorithm as follows:

/// <summary>
        /// Given random array containing values 0 and 1, sort it so all 0s come before 1
        /// </summary>
        [TestMethod]
        public void Sort0And1Array()
        {
            int[] array = new[] {1, 1, 0, 0, 1};

            int start = 0;
            int mid = array.Length/2;
            int end = array.Length - 1;

            while (mid < end)
            {
                if (array[mid] == 0)
                {
                    int temp = array[start];
                    array[start] = array[mid];
                    array[mid] = temp;
                    start++;
                    mid++;
                }
                else
                {
                    int temp = array[end];
                    array[end] = array[mid];
                    array[mid] = temp;
                    mid++;
                    end--;
                }
            }
        }

I don't understand the complex solutions. Do we really need to rearrange the array? Can't we just have a count of Red and Blue balls (which can be found in a linear loop O(n)). Let's say there are 2 Red and 3 Blue balls - when the array is accessed, we can simply return Red for any index less than count(Red) and Blue for any index greater than count(Red) (of course, check for underflow condition with count(Blue)). Or, we can just overwrite the array in another O(n) loop which will still keep the total time complexity in O(n). Any thoughts?