sort binary array with minimum time complexity

Question

Anonymous · Accepted Answer

Maintain two counters, one for 0 and another for 1. Start from array[0] and go on till end and increment counts if zero or one whichever you encounter. Overwrite the array with number of zeros and then number of ones. "counting sort". O(n)

hivehome · Answer

int[] sortBinary(int[] nums) {
        if(nums == null || nums.length ==0)
            return nums;
        int left = 0, right = nums.length -1;
        while(left < right) {
            if(nums[left] == 0)
                left++;
            if(nums[right] == 1)
                right--;
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
        }
        return nums;
    }

Anonymous · Answer

traverse array in one for loop with one index from start and one from end.
move all 0's on one end and 1's on other end using these indexed.
The minimum time complexity is O(n/2)

Anonymous · Answer

void
sort(char A[], int len)
{
   int ones = len - 1;
   int zeroes = 0;

   while (zeros < ones) {
      while (A[zeroes] == 0)
         zeroes++;
      while (A[ones] == 1)
         ones--;
      swap(A+zeroes, A+ones);
      zeroes++;
      ones--;
   }
}

Apple

Apple Interview Question

Interview Answers

Followed companies

Job searches

Bowls

Want the inside scoop on your own company?