Move zeros to the front
Company: Uber
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given an integer array nums, move all elements equal to 0 to the beginning of the array while preserving the relative order of all non-zero elements. The transformation must be done in-place using O(1) extra space.
Example:
- Input: [1, 0, 2, 0, 3]
- Output: [0, 0, 1, 2, 3]
Discuss the time complexity you would target.
Overview: This question evaluates array manipulation skills, in-place algorithm design, and reasoning about time and space complexity while preserving element order under an O(1) extra space constraint.
Read the full Uber Data Scientist interview experience this question came from
Given an integer array nums, move all elements equal to 0 to the beginning of the array while preserving the relative order of all non-zero elements. The transformation must be done in-place using O(1) extra space.
For example, if nums = [1, 0, 2, 0, 3], the result should be [0, 0, 1, 2, 3].
Aim for O(n) time complexity. For evaluation, return the modified array after performing the in-place transformation.
Constraints
- 0 <= len(nums) <= 100000
- -1000000000 <= nums[i] <= 1000000000
- The operation must use O(1) extra space
Examples
Input: [1, 0, 2, 0, 3]
Expected Output: [0, 0, 1, 2, 3]
Explanation: The two zeros move to the front, and the non-zero values 1, 2, 3 keep their original order.
Input: [0, 0, 1, 2]
Expected Output: [0, 0, 1, 2]
Explanation: Zeros are already at the front, so the array stays the same.
Hints
- Try processing the array from right to left and placing non-zero values at the end.
- Once all non-zero values are in their final relative order, fill the remaining positions at the front with 0.
Community answers
Answer by daow
def move_zero(arr):
n = len(arr)
ind = n - 1
for i in range(n - 1, -1, -1):
if arr[i] != 0:
arr[ind] = arr[i]
ind -= 1
arr[:ind + 1] = (ind + 1) * [0]
return arr