Home > Software design >  Moving zeros to the beginning of an array
Moving zeros to the beginning of an array

Time:10-08

I need help with my solution the algorithm question below. My code works but the elements to right side of the array are not supposed to be sorted.

You are given an array of integers. Rearrange the array so that all zeroes are at the beginning of the array.For example,a = [4,2,0,1,0,3,0] -> [0,0,0,4,1,2,3]

 func moveZerosTotheFront(arrays:[Int] )->[Int] {
    var result = arrays
    var boundary = 0
    for index in 0...arrays.count-1{
        if result[index] == 0{
            print(index )
            result.swapAt(index, boundary)
            boundary =1
        }
    }
    return result
}

[0, 0, 0, 1, 2, 3, 4]

CodePudding user response:

It's because of your use of swapAt. Think about what happens the very first time you encounter a zero. At that time, boundary is 0 and so the value there is 4; you are swapping that 4 to replace the first 0 you encountered, which is after the 2, thus violating the terms of the problem.

The truth is that you don't need to swap anything. You're way overthinking this! You know perfectly well that the only things to be "moved" are 0 values. So just eliminate all the 0 values and stick that same number of 0 values on the front. You know what "that same number" is because that's how much shorter the array got when you eliminated the 0 values.

func moveZerosTotheFront(_ array:[Int])->[Int] {
    let result = array.filter {$0 != 0}
    return Array(repeating: 0, count: array.count - result.count)   result
}

CodePudding user response:

Matt's solution works, but if you're like me and prefer not to use variables, here is an alternative:

func moveZerosTotheFront(arrays: [Int]) -> [Int] {
    arrays
        .enumerated()
        .sorted(by: { lhs, rhs in
            lhs.element == 0 || lhs.offset < rhs.offset
        })
        .map(\.element)
}

Give priority to zero values, else give priority to smallest index.

CodePudding user response:

I've not worked on swift, but just thought of sharing an approach which has O(n) time complexity and O(n) space complexity.

1.You can create an extra array(named as sortingZeros) of same size.

2.givenArr = [4,2,0,1,0,3,0] --> Iterate the gvien array from the last index and add the non zero values from the last position of the extra array. For Ex :

var i = givenArr.length-1;
var j = givenArr.length-1;
for (iterate in the reverse direction) {
  if (givenArr[i] != 0) {
     sortingZeros[j] = givenArr[i];
     j--; 
  }
  i--;
}
  1. Once all the non-zero values are added to the new array the zeros would automatically be at the front of the array.
  • Related