Coding Interview — Move Zeros (Array)
Given an array of numbers, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.
Input: [0,-1,0,15,7]
Output: [-1,15,7,0,0]Thought process:
In order to check all the elements within the input array, we need to loop through the whole array, and that’s O(n) for Time Complexity, which is inevitable. How about Space? Naturally we would think to create an empty array result=[] and loop through the Input array and do the operations to get the result we want. However that would require additional O(n) space. Is it possible to do it without additional space? Yes! Let’s do it In-Place!
Solution:
moveZeros(numbers) {
// Keep good habit to check corner cases at the beginning.
if (numbers === null || numbers.length < 1) return numbers; // Use a pointer to keep track our 'zero' location
let idx = 0; // Loop through the input to find the non-zero elements and update the input array in place!
for (let num of numbers) {
if (num !== 0) {
numbers[idx++] = num;
}
}
while (idx < numbers.length) {
numbers[idx++] = 0;
}
};
Key Notes:
- Save Space
- How to track & update the input array? Use pointer/Swap technique … etc
What’s the next question?
Stocks 101 — When to buy/sell the stock? Given an array contains the daily price for a stock. Try to find the maximum profit. (thought process and solution)
Before You Go —
There’s no better way to support me than to give me a follow on Medium (Victor Lin). Let me know that I should write more!
Did you know that you can give up to 50 👏’s by pressing down on the 👏 button? Give it a try if you reeeeeeally liked this article!
