sort binary array with minimum time complexity

Question

Sigiloso · 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;
    }

Sigiloso · 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)

Sigiloso · 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

Pergunta de entrevista da empresa Apple

Respostas da entrevista

Empresas seguidas

Buscas de vagas