Given an array of integers representing chocolate packets, where 0 indicates an empty packet, the task is to move all empty packets (zeros) to the end of the array while maintaining the relative order of the non-empty packets.
Input: N = 8, arr = [4, 5, 0, 1, 9, 0, 5, 0]
Output: [4, 5, 1, 9, 5, 0, 0, 0]
Explanation: The three zeros are moved to the end, and the non-zero elements retain their original order.
Input: N = 5, arr = [0, 1, 0, 3, 12]
Output: [1, 3, 12, 0, 0]
Explanation: Zeros are moved to the end, and non-zero elements keep their order.
Input: N = 3, arr = [0, 0, 1]
Output: [1, 0, 0]
Explanation: The non-zero element is moved to the front, and zeros to the end.
The key insight is to maintain the relative order of non-zero elements while efficiently moving zeros to the end. This can be achieved by tracking the next available position for a non-zero element during a single pass through the array.
index to 0, representing the next position for a non-zero element.i. For each non-zero element at arr[i], place it at arr[index] and increment index.index to the end of the array with zeros.void moveZeroes(vector<int>& arr) {
int index = 0;
for (int i = 0; i < arr.size(); i++) {
if (arr[i] != 0) {
arr[index] = arr[i];
index++;
}
}
for (int i = index; i < arr.size(); i++) {
arr[i] = 0;
}
}public void moveZeroes(int[] arr) {
int index = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] != 0) {
arr[index++] = arr[i];
}
}
while (index < arr.length) {
arr[index++] = 0;
}
}def move_zeroes(arr):
index = 0
for i in range(len(arr)):
if arr[i] != 0:
arr[index] = arr[i]
index += 1
for i in range(index, len(arr)):
arr[i] = 0function moveZeroes(arr) {
let index = 0;
for (let i = 0; i < arr.length; i++) {
if (arr[i] !== 0) {
arr[index] = arr[i];
index++;
}
}
for (let i = index; i < arr.length; i++) {
arr[i] = 0;
}
}Time Complexity: O(N), where N is the size of the array. We perform two linear passes (one for non-zero elements, one for zeros), each of O(N) time.
Space Complexity: O(1), as we modify the array in-place without using any extra space.
Your notes are automatically saved in your browser's local storage and will persist across sessions on this device.