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

• Time Complexity: O(n), where n is the length of the array. The array is traversed once.
• Space Complexity: O(1), since we only use a few extra variables regardless of the input size.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?