Q7: How do you move all zeroes to the end of an array in-place while maintaining relative order?
Maintain a lastNonZeroFoundAt pointer initialized to 0. Iterate through the array; whenever a non-zero element is encountered, swap it with the element at lastNonZeroFoundAt and increment the pointer.
In-Place Move Zeroes Solution
public class MoveZeroes {
public static void moveZeroes(int[] nums) {
int insertPos = 0;
for (int num : nums) {
if (num != 0) {
nums[insertPos++] = num;
}
}
while (insertPos < nums.length) {
nums[insertPos++] = 0;
}
}
}💡 Overwrites non-zero values forward, then pads remaining indices with zeroes.
Key Takeaways
- Two-pointer partitioning scheme.
- Executes in $O(n)$ time with $O(1)$ auxiliary memory.
Knowledge Check
What is the total number of array writes required in the worst-case for the two-pass insertPos approach?