Difficulty | Source | Tags | |
---|---|---|---|
Easy |
160 Days of Problem Solving |
|
The problem can be found at the following link: Problem Link
Given an array arr[]
, move all the zeros in the array to the end while maintaining the relative order of non-zero elements. The modification should be done in-place.
Input:
arr[] = [1, 2, 0, 4, 3, 0, 5, 0]
Output:
[1, 2, 4, 3, 5, 0, 0, 0]
Explanation:
The three zeros are moved to the end while the relative order of non-zero elements is maintained.
Input:
arr[] = [10, 20, 30]
Output:
[10, 20, 30]
Explanation:
No change in the array as there are no zeros.
Input:
arr[] = [0, 0]
Output:
[0, 0]
Explanation:
No change in the array as all elements are zeros.
-
Two-Pointer Technique:
- Use a pointer
nonZeroIndex
to track the position where the next non-zero element should be placed. - Traverse the array, and whenever a non-zero element is encountered, swap it with the element at the
nonZeroIndex
and increment the pointer. - This ensures all non-zero elements are shifted to the front, and zeros naturally move to the end.
- Use a pointer
-
Edge Cases:
- If the array contains no zeros, return the array as is.
- If the array contains only zeros, no changes are needed.
- Expected Time Complexity: O(n), where
n
is the number of elements in the array. Each element is traversed once to determine its position. - Expected Auxiliary Space Complexity: O(1), as no additional space is used apart from a few variables.
class Solution {
public:
void pushZerosToEnd(std::vector<int>& arr) {
int n = arr.size();
int nonZeroIndex = 0;
for (int i = 0; i < n; i++) {
if (arr[i] != 0) {
std::swap(arr[nonZeroIndex++], arr[i]);
}
}
}
};
class Solution {
void pushZerosToEnd(int[] arr) {
int n = arr.length;
int nonZeroIndex = 0;
for (int i = 0; i < n; i++) {
if (arr[i] != 0) {
int temp = arr[nonZeroIndex];
arr[nonZeroIndex] = arr[i];
arr[i] = temp;
nonZeroIndex++;
}
}
}
}
class Solution:
def pushZerosToEnd(self, arr):
n = len(arr)
nonZeroIndex = 0
for i in range(n):
if arr[i] != 0:
arr[nonZeroIndex], arr[i] = arr[i], arr[nonZeroIndex]
nonZeroIndex += 1
For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!
⭐ If you find this helpful, please give this repository a star! ⭐