If you've been following this series so far, then this problem should be a piece of cake.
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.
Example:
Input: [0,1,0,3,12]
Output: [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.
Approach 1
Algorithm:
- Initialize variable zeroCount to store count of zeroes
- Initialize result to store the final array
- Iterate through all elements of the array
- If the element is zero then increment zeroCount
- Else append to the result array
- Append zeroCount number of zeroes to the result
- Replace elements of original array with result
Code:
def approach1(nums):
zeroCount = 0
result = []
for i in range(len(nums)):
if nums[i] == 0:
zeroCount += 1
else:
result.append(nums[i])
for i in range(zeroCount):
result.append(0)
for i in range(len(nums)):
nums[i] = result[i]
return nums
Complexity analysis:
Time complexity: O(n) Always n operations
Space complexity: O(n)
Approach 2
Algorithm:
- Initialize variable nextIndex to store the next index of non zero element
- Iterate through all elements of the array
- If the current element is not zero then put it at nextIndex and increment it
- Once step 2 ends iterate from nextIndex to the end of the array and assign zero at those indices
Code:
def approach2(nums):
nextIndex = 0
for i in range(len(nums)):
if nums[i] != 0:
nums[nextIndex] = nums[i]
nextIndex += 1
for i in range(nextIndex, len(nums)):
nums[i] = 0
return nums
Complexity analysis:
Time complexity: O(n) with near minimum operations
Space complexity: O(1)
Approach 3
Algorithm:
- Initialize variable nextIndex to store the next index of non zero element
- Iterate through all elements of the array
- If the current element is not zero then swap it with the element at nextIndex and increment it
Code:
def approach3(nums):
nextIndex = 0
for i in range(len(nums)):
if nums[i] != 0:
nums[i], nums[nextIndex] = nums[nextIndex], nums[i]
nextIndex += 1
return nums
Complexity analysis:
Time complexity: O(n) with minimum operations
Space complexity: O(1)
Summary
This problem was more of tricky thinking rather than algorithmic thinking.
Here's the replit
Top comments (0)