Given an array of random numbers and zeros, arrange the array such that all the numbers restoring their order are moved in front and move all zeros to end of array. There are so many ways to solve this problem. We can make use of additional arrays, pointers, partitions, etc.
Example to Understand
Let us look at examples to understand the problem well.
Input: {8, 4, 0, 2, 5, 0, 1, 0, 7, 0}
Output: {8, 4, 2, 5, 1, 7, 0, 0, 0, 0}
Input: {1,2}
Output: {1,2}
Input: {0, 0, 8, 2, 3, 0, 5}
Output: {8, 2, 3, 5, 0, 0, 0}
Here, all the non-zeros elements are moved in front, and zeros are moved to the end of the array.
Note: We cannot use sorting in descending order as we are supposed to reserve the order of the rest of the elements in the array.
Method 1: Using Pointers
We can think of an array as a set of two types of elements, zeros, and non-zero. We can make use of a pointer called count and a for loop that traverses the array.
We know that only non-zeros elements can be different and we are required to preserve their order. Zeros are all the same. Thus, as soon as we come across a non-zero element we insert it at the count position and increment count.
This way count will always be equal to or less than the current element’s index and thus, there will be no data loss. Lastly, as we are done traversing the array, we start from count till N(total elements in the array) and insert zeros to move all zeros to end of array.
Approach
- Initialize count = 0.
- Use a for loop to traverse the array.
- If the current element is non-zero, insert the element at count and increment the value of count.
- Finally start a for loop from count till N where N is the total number of elements and insert zeros.
Implementation:
#include <iostream>
void rearrangeArray(int arr[], int N) {
int count = 0; // Initialize a pointer called 'count' to 0
// Traverse the array
for (int i = 0; i < N; i++) {
if (arr[i] != 0) { // Check if the current element is non-zero
arr[count] = arr[i]; // Insert the non-zero element at the 'count' position
count++; // Increment 'count' to move to the next position
}
}
// Fill the remaining elements from 'count' to 'N' with zeros
for (int i = count; i < N; i++) {
arr[i] = 0;
}
}
int main() {
int arr[] = {8, 4, 0, 2, 5, 0, 1, 0, 7, 0};
int N = sizeof(arr) / sizeof(arr[0]);
std::cout << "Original Array: ";
for (int i = 0; i < N; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
rearrangeArray(arr, N);
std::cout << "Rearranged Array: ";
for (int i = 0; i < N; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
return 0;
}
Output:
Original Array: 8 4 0 2 5 0 1 0 7 0
Rearranged Array: 8 4 2 5 1 7 0 0 0 0
Complexity
Time Complexity: O(N) as we are using only single for loop and no nested loops. Here, N is the total number of elements in the array.
Space Complexity: O(1) No additional space is used in this method.
Method 2: Partitioning the Arrays
Here we will partition the array into pivot elements i.e. zero(0) and other elements. We use a for loop to traverse the array and for every non-pivot element we will swap the pivot with the element and increment the pivot index.
Approach
- Initialize j to the starting index.
- Use a for loop to traverse the array with i as iterator.
- If the element at i is not pivoted, swap it with the element at j and increment j.
- The array is rearranged as the required array.
Implementation:
#include <iostream>
// Function to swap two elements in an array
void swap(int& a, int& b) {
int temp = a;
a = b;
b = temp;
}
// Function to partition the array using 0 as the pivot element
void partitionArray(int arr[], int N) {
int j = 0; // Initialize the starting index
// Traverse the array using the 'i' iterator
for (int i = 0; i < N; i++) {
if (arr[i] != 0) { // Check if the element at index 'i' is not the pivot
// Swap the element at index 'i' with the element at index 'j'
swap(arr[i], arr[j]);
j++; // Increment 'j' to move to the next position
}
}
}
int main() {
int arr[] = {8, 4, 0, 2, 5, 0, 1, 0, 7, 0};
int N = sizeof(arr) / sizeof(arr[0]);
std::cout << "Original Array: ";
for (int i = 0; i < N; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
partitionArray(arr, N);
std::cout << "Partitioned Array: ";
for (int i = 0; i < N; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
return 0;
}
Output:
Original Array: 8 4 0 2 5 0 1 0 7 0
Partitioned Array: 8 4 2 5 1 7 0 0 0 0
Complexity
Time Complexity: O(N) Here, N is the total number of elements in the array.
Space Complexity: O(1) No additional space is required in this method.
Method 3: Using C++ STL
Instead of using a fixed-size array, we can also use a dynamic array such as a vector or ArrayList from C++ STL to move all zeros to end of array. We can traverse the array remove all the zeros from the dynamic array and keep a count of all the removed zeros. Lastly, add all the zeros at end of array equal to the count.
Approach
- Initialize count = 0;
- Use a for loop to traverse the array.
- Instead of deleting the zero we simply use that index to put other elements.
- After completion of the iteration, we will insert zeros at the end.
Implementation:
#include <iostream>
#include <vector>
void rearrangeArray(std::vector<int>& arr) {
int N = arr.size();
int count = 0; // Initialize a counter for zeros
// Traverse the array to count and remove zeros
for (int i = 0; i < N; i++) {
if (arr[i] == 0) {
count++; // Increment the zero count
} else {
// Move non-zero elements to the left to fill gaps created by removed zeros
arr[i - count] = arr[i];
}
}
// Append 'count' number of zeros to the end of the array
for (int i = N - count; i < N; i++) {
arr[i] = 0;
}
}
int main() {
std::vector<int> arr = {8, 4, 0, 2, 5, 0, 1, 0, 7, 0};
std::cout << "Original Array: ";
for (int i: arr) {
std::cout << i << " ";
}
std::cout << std::endl;
rearrangeArray(arr);
std::cout << "Rearranged Array: ";
for (int i: arr) {
std::cout << i << " ";
}
std::cout << std::endl;
return 0;
}
Output:
Original Array: 8 4 0 2 5 0 1 0 7 0
Rearranged Array: 8 4 2 5 1 7 0 0 0 0
Complexity
Time Complexity: O(N) As we are traversing the array only once.
Space Complexity: O(1) No additional space is used in this method.
Method 4: Using Extra Space
We can also move all zeros to end of array using the brute force approach where we will be using an extra array. The time complexity of the approach will remain O(N). We will initialize the rearranged array. Traverse the array and for every non-zero element, insert the element in the new array. Lastly, insert all the remaining positions with zero in the new array.
Approach
- Initialize a new array named rearranged of the same size.
- Initialize j with the starting index.
- Use a for loop to traverse the array.
- If the element is not equal to zero, then add the element to the rearranged array at index j and increment j.
- Lastly, start a loop from j to N and insert zeros to move all zeros to end of array.
Implementation:
#include <iostream>
void rearrangeArray(int arr[], int N) {
int rearranged[N]; // Initialize the new array
int j = 0; // Initialize a pointer for the new array
// Traverse the original array
for (int i = 0; i < N; i++) {
if (arr[i] != 0) {
rearranged[j] = arr[i]; // Insert non-zero element into the new array
j++; // Move to the next position in the new array
}
}
// Fill the remaining positions with zeros
while (j < N) {
rearranged[j] = 0;
j++;
}
// Copy the rearranged array back to the original array
for (int i = 0; i < N; i++) {
arr[i] = rearranged[i];
}
}
int main() {
int arr[] = {8, 4, 0, 2, 5, 0, 1, 0, 7, 0};
int N = sizeof(arr) / sizeof(arr[0]);
std::cout << "Original Array: ";
for (int i = 0; i < N; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
rearrangeArray(arr, N);
std::cout << "Rearranged Array: ";
for (int i = 0; i < N; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
return 0;
}
Output:
Original Array: 8 4 0 2 5 0 1 0 7 0
Rearranged Array: 8 4 2 5 1 7 0 0 0 0
Complexity
Time Complexity: O(N) as we are using only a single for loop to traverse the array. Here, N is the total number of elements in the array.
Space Complexity: O(N) We are using an additional array of the same size as the original array.
FAQs
Q. How does Method 2 handle zeros in the array?
A. This method partitions the array using 0 as the pivot element, moving non-zero elements to the front and zeros to the end.
Q. Does the original array remain unchanged in the first 3 methods?
A. No, the original array is modified, and the rearranged elements are stored in the same array.
Q. What additional space does Method 4 use?
A. This method uses an additional array (rearranged) of the same size as the original array.
Q. What is the time complexity of Method 1 to move all zeros to the end of the array?
A. The time complexity is O(N), where N is the size of the array.
Conclusion
- We are given an array with zeros and non-zero. We are supposed to move all zeros to the end of the array without disturbing the order of the non-zero elements in the array.
- This can be quickly done by using another array where we can store all the non-zero elements lastly, we simply insert zeros in the remaining positions.
- We can achieve the same result without using additional space. Method 1 makes use of pointers. We use the pointer count and a for loop to traverse the array. As we come across a non-zero element we insert it at the count position and increment the count pointer. After the first traversal, we insert zeros at the remaining position.
- Method 2 partitions the array into two parts, pivots (0) and rest elements. We will traverse the array and for every non-pivot element, we swap it with the zero element and increment the pivot index.
- Method 3 uses the dynamic arrays approach. Rather than using traditional arrays, we can make use of dynamic memory. We can remove the positions that contain zeros and keep a count of them. Lastly, we will append the count number of zeros to the arraylist or vector.
