Given an array, without using extra space, move all zeros to the end and no-zeros to the beginning. The function should return the number of non-zeros.

Question

Yoni Vizel · Accepted Answer

-(int)sortZerosAndReturnCountOfThem:(NSMutableArray *)arr {
    NSLog(@"before: %@", arr);
    
    int cursorFromStart = 0;
    int cursorFromEnd = (int)arr.count - 1;
   
    while (cursorFromStart < cursorFromEnd) {
        while (arr[cursorFromStart].intValue != 0) {
            cursorFromStart++;
        }
        while (arr[cursorFromEnd].intValue == 0) {
            cursorFromEnd--;
        }
        if (cursorFromStart < cursorFromEnd) {
            arr[cursorFromStart] = arr[cursorFromEnd];
            arr[cursorFromEnd] = @(0);
        }
    }
    
    NSLog(@"after: %@", arr);
    
    int counter = 0;
    for (NSNumber *num in arr) {
        if (num.intValue == 0) {
            counter++;
        }
    }
    NSLog(@"counter: %d", counter);
    return counter;
}

Quicksort.. · Answer

Quick sort the count the zeros ...

Anonymous · Answer

func moveZeros(input: inout [Int]) -> Int {
   //reverse sort 
    input = input.sorted { $0 > $1 }
    let countNonZero = input.filter { $0 != 0 }.count
    return countNonZero
}

Davy · Answer

No need to sort. Can do in O(n) time.

Swift:

func moveAllZerosToFront(list: inout [Int]) -> Int {
  var numOfZeros = 0
  for i in 0..

Davy · Answer

Don't know why my post got cut off.

No need to sort. Can do in O(n) time.

Swift:

func moveAllZerosToFront(list: inout [Int]) -> Int {
  var numOfZeros = 0
  for i in 0..

Hari Krishna Bista · Answer

var input = [1,0,0,1,2,3]

var counter = 0
var zerosCounter = 0

while(counter  0){
    input.append(0)
    zerosCounter = zerosCounter - 1
}

print(input)

Anonymous · Answer

func moveAllZeros(_ array : inout [Int]) {
    var left  = 0
    var right  = array.count - 1
    while left < right {
        while array[left] != 0 { left += 1 }
        while array[right] == 0 { right -= 1 }
        if left < right {
            array[left] = array[right]
            array[right] = 0
            left += 1
            right -= 1
        }
    }
}

Nick · Answer

I use Swift, but not sure it ok or not....

func moveAllZeros(_ arr :  [Int]){
   arr.sorted()
}

func ReturnNumberOfnonzeros(_ arr:[Int]) -> Int {
   return arr.filter{$0>0}.count
}

Naga Murala · Answer

We can use the stride function to iterate input array in reverse order then swap the zero values towards the end..

func moveZerosToEnd(inputArray: inout [Int]) -> [Int] {
    var zeroIndex = inputArray.count - 1
    for index in stride(from: inputArray.count-1, through: 0, by: -1) {
        if inputArray[index] == 0 {
            inputArray.swapAt(index, zeroIndex)
            zeroIndex -= 1
        }
    }
    return inputArray
}

var inputArray1 = [1,2,3,4,0,0,4,5,0]
print(moveZerosToEnd(inputArray: &inputArray1))

swift · Answer

func zerosToTheEnd(a: [Int]) -> [Int]{
    guard a.count > 1 else {return a}
    var array = a
    
    var l = 0, h = array.count-1
    
    while h >= 0, array[h] == 0 {
        h -= 1
    }
    
    while l < h {
        if array[l] == 0{
            array[l] = array[h]
            array[h] = 0
            h -= 1
        }
        l += 1
    }
    return array
}

Using JavaScript · Answer

functionPushZeros(arr) {
    let zeros = [], noneZeros = [];

}

Johnpaul · Answer

//using Javascript

function pushZeros(arr) {
    let zeros = [], noneZeros = [];
    for(let val of arr) {
        if(val === 0) zeros.push(val);
             else noneZeros.push(val);
    }
    return [...noneZeros, ...zeros];
}

JK · Answer

swapping 2 numbers if one is zero, can be done without any space.
assuming array[a] is zero, and array [b] is non zero, array[a] = array[b], array[b] = 0 would simply work.

so, have 2 pointers, one from beginning and one from the end, do a while loop

Terry G · Answer

All of the solutions above require addition storage for counters, variables, etc.  This is a solution that does not use any additional in-memory storage, by using an external hash table stored in a relational database.  It also has the added benefit of being  O(n)

getBitwiseShiftedValues( startValue )
        setupSQLValueHashTable();   // generate SQL table with key 'valueKey' and value 'sortedBits'.  Only done once.
        result = SELECT sortedBits FROM valueHashTable where valuekey = startValue ;
        return result;

Meta

Meta interview question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches