Katkat
Back

Move zeros to front

UberData Scientist · Technical Screen
MediumData ScientistTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to manipulate array indices in-place to reorder elements according to a specific condition while maintaining relative stability.

Problem Statement

Given an integer array nums, move all zeros to the front of the array while maintaining the relative order of the non-zero elements. You must perform this operation in-place, without making a copy of the array, and minimize the number of operations performed.

Function Signature

def move_zeros_to_front(nums: List[int]) -> None:

Constraints

  • 1 <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4

Examples

Example 1: Input: nums = [0, 1, 0, 3, 12] Output: [0, 0, 1, 3, 12] Explanation: The zeros are moved to the front, and the non-zero elements [1, 3, 12] retain their original order.

Example 2: Input: nums = [1, 7, 0, 0, 8, 0, 9] Output: [0, 0, 0, 1, 7, 8, 9]

Edge Cases

  • The array contains no zeros.
  • The array contains only zeros.
  • The array is already sorted with zeros at the front.
  • The array contains negative numbers.

Hints

Hint 1

Consider iterating through the array from right to left instead of left to right to track the position where the next non-zero element should go.

Hint 2

Using two pointers can help you keep track of where the last non-zero element was moved.

Hint 3

If you start from the end of the array, you can effectively 'shift' non-zero elements towards the back and fill the remaining front slots with zeros.

Follow-up questions

  • What is the time and space complexity of your solution, and can it be optimized further?
  • How would your approach change if you were required to maintain the relative order of the zeros as well?
  • If the input was a very large stream of integers rather than a fixed-size array, how would you handle this problem?