Move all zeroes to end of array
The problem is to move all zeroes to the end of the array while maintaining the order of non-zero elements. The goal is to rearrange the elements in such a way that all zeroes appear after all the non-zero elements in the array.
Example
Consider the following array:
[0, 1, 4, 7, 2, 2, 1, 2, 0, 0, 6, 0, 1, 1, 0]
After moving all zeroes to the end, the array could be rearranged as:
[1, 1, 4, 7, 2, 2, 1, 2, 1, 6, 0, 0, 0, 0, 0]
|<---------->|
All non-zero elements appear first, followed by all zeroes. The relative order of non-zero elements is maintained.
Idea to Solve the Problem
To move all zeroes to the end of the array, we can use a two-pointer approach. The idea is to have two pointers, one at the front of the array (starting from index 0) and the other at the end of the array (starting from index n - 1).
- Initialize two pointers, i.e., front = 0 and back = n - 1.
- The pointer front will be used to iterate through the array from the beginning.
- The pointer back will be used to keep track of the next available position for a non-zero element from the end of the array.
- If arr[back] is 0, just decrement back.
- If arr[front] is 0, swap arr[front] with arr[back] and increment front and decrement back.
- If arr[front] is not 0, just increment front.
- Continue this process until front index is less than or equal to back index.
Algorithm
- Initialize two pointers, front = 0 and back = n - 1.
- While front is less than or equal to back, do the following: a. If arr[back] is 0, decrement back. b. If arr[front] is 0, swap arr[front] with arr[back], increment front, and decrement back. c. If arr[front] is not 0, just increment front.
- The array is now rearranged with all zeroes moved to the end.
Pseudocode
function moveZeroToEnd(arr, n):
front = 0
back = n - 1
while front <= back:
if arr[back] is 0:
decrement back
else if arr[front] is 0:
swap arr[front] with arr[back]
increment front
decrement back
else:
increment front
end if
end while
end function
Code Solution
-
1) Move all zeroes to end of array in java
2) Move all zeroes to end of array in c
3) Move all zeroes to end of array in c++
4) Move all zeroes to end of array c# program
5) Move all zeroes to end of array in golang
6) Move all zeroes to end of array in node js
7) Move all zeroes to end of array in ruby
8) Move all zeroes to end of list python
9) Move all zeroes to end of array swift
10) Move all zeroes to end of array in php
11) Move all zeroes to end of array in typescript
12) Move all zeroes to end of array in scala
13) Move all zeroes to end of array in kotlin
14) Move all zeroes to end of array in vb.net
Time Complexity
- The above algorithm has a time complexity of O(N), where N is the number of elements in the array.
- The algorithm processes each element in the array exactly once, so it runs in linear time with respect to the number of elements.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment