This post is completed by 1 user
|
Add to List |
555. Move All Zeroes to the End of the Array
Problem Statement:
Given an array of random numbers, move all the zeros to the end of the array while maintaining the relative order of the non-zero elements.
Example 1:
Input: {0, 1, 0, 3, 12} Output: {1, 3, 12, 0, 0}
Example 2:
Input: {1, 2, 0, 0, 3, 4} Output: {1, 2, 3, 4, 0, 0}
Example 3:
Input: {0, 0, 0, 0} Output: {0, 0, 0, 0}
Naive Solution:
- Create a new result array of the same length as the input array.
- Iterate through the input array and place each non-zero element in the result array.
- Leave the zeroes at the end by default, as the uninitialized values in the result array are zeroes.
Time Complexity: O(N), Space Complexity: O(N)
Output
[0, 1, 0, 3, 12] [1, 3, 12, 0, 0]
Better Solution:
- Use a pointer (or counter) to track the position of non-zero elements.
- Iterate through the array and shift all non-zero elements to the front.
- Fill the remaining spaces with zeroes.
Time Complexity: O(N), Space Complexity: O(1)
Output
Input: [1, 2, 0, 0, 3, 4] Output: [1, 2, 3, 4, 0, 0]