Come across a task in an Interview or a website that challenges you to this. The thing that intrigues me is a good challenge (and many a times I do struggle with it, I am no Genius) However it is still worth a try.
The challenge I came across was to move the zeroes to the end of an array. Think of it as moving a particular character/number but in this case it is zeroes.
Here’s the original problem
Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.
For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].
Note:
You must do this in-place without making a copy of the array.
Minimize the total number of operations.
The first go
There are a couple of things here, the first criterion is not to create a copy of the array. It would have been so simpler if you could simple do the following
var nums = [0, 1, 0, 3, 12]
func removeZeroes(fromArray:[Int]) -> [Int] {
var results = Array<Int>(repeating: 0, count: fromArray.count)
var index = 0
for i in 0..<fromArray.count {
if fromArray[i] != 0 {
results[index] = fromArray[i]
index += 1
}
}
return results
}
let res = removeZeroes(fromArray: nums)
This would be easy, as we can create a new array that has the same length as the passed array and initialized with zeroes. Next we iterate through the array and if the number is non-zero, we save the number at the index and increase the index. That way, we can transverse through the array and add non-zeros to the new array.
However, the trick is NOT to use an alternate array and it has to be in place. So our function has the parameter as inout.
func removeZeroes2(nums: inout [Int]) {
for i in 0..<nums.count {
if nums[i] == 0 {
nums.append(0)
nums.remove(at: i)
}
}
}
removeZeroes2(nums: &nums)
print(nums)
How it works is even simpler, when we find a zero, we add a zero at the end of the array and remove the item at the current index (which is supposedly a zero and already added a zero at the end).
In Conclusion
The code above is short, readable and works … ALMOST!! There is some issue with the code that I could not fix. If there are more than one 0’s consecutively then that 0 is missed or the code does not process it properly. My feeling is that it could happen because either it is a bug in Swift or the array’s original values are preserved even though it is iterated through and altered.
So an easier way to resolve that could be to use code like
func removeZeroes3(nums: inout [Int]) {
let length = nums.count
nums = nums.filter { $0 != 0 }
let maxCount = length - nums.count
for i in 0..<maxCount {
nums.append(0)
}
}
removeZeroes3(nums: &nums_)
print(nums_)
UPDATE:
Another alternative that is now present, alluding that the problem is with swift’s implementation is that the entire exercise can be written with just one line of code using Swift 3.0. It can be expressed as follows
func zeros(num: inout [Int]) {
num.sort { $1 == 0 }
}
The sort function in Swift 3.0 moves the zeros to the end for us without having to do much really.
The methodology behind this is quite simple, we first get the number of items in the passed array, then we filter the array in place to remove any 0’s. This new array is shorter by the number of zeroes. So we simply add as many 0’s as required to make the array the same length as the array passed.
Views All Time
1529
Views Today
1
