algoadvance

Leetcode 283. Move Zeroes

Problem Statement

Given an integer array nums, move all 0s to the end of it while maintaining the relative order of the non-zero elements.

Example:

Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

Clarifying Questions

  1. Can I modify the input array in place?
    • Yes, you need to modify the input array in place.
  2. Is it acceptable to use extra storage?
    • Ideally, you should aim for a solution that uses O(1) extra space.
  3. What should I do if the array is empty or contains only one element?
    • If the array is empty or contains only one element, you can return it as is since no modifications are needed.

Strategy

The main strategy involves two pointers:

  1. lastNonZeroFoundAt: Tracks the position to place the next non-zero element.
  2. current: Loops through all elements in the array.

Algorithm:

  1. Iterate through the array with current. For every non-zero element nums[current]:
    • Swap it with nums[lastNonZeroFoundAt].
    • Increment lastNonZeroFoundAt.
  2. By the end of the iteration, all non-zero elements are shifted to the front, and lastNonZeroFoundAt is positioned at the first zero.

Code

Here is the Java implementation:

public class Solution {
    public void moveZeroes(int[] nums) {
        if (nums == null || nums.length == 0) return;
        
        int lastNonZeroFoundAt = 0;
        
        // Move all the non-zero elements forward
        for (int current = 0; current < nums.length; current++) {
            if (nums[current] != 0) {
                // Swap the elements
                int temp = nums[lastNonZeroFoundAt];
                nums[lastNonZeroFoundAt] = nums[current];
                nums[current] = temp;
                
                lastNonZeroFoundAt++;
            }
        }
    }
}

Time Complexity

In conclusion, this two-pointer technique efficiently moves all zeroes to the end while maintaining the order of non-zero elements.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI