Coding questions · Uber
Move zeros to the front
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.
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.
Move Zeros to the Front
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
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.