Skip to main content

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).

  1. Initialize two pointers, i.e., front = 0 and back = n - 1.
  2. The pointer front will be used to iterate through the array from the beginning.
  3. 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.
  4. If arr[back] is 0, just decrement back.
  5. If arr[front] is 0, swap arr[front] with arr[back] and increment front and decrement back.
  6. If arr[front] is not 0, just increment front.
  7. Continue this process until front index is less than or equal to back index.

Algorithm

  1. Initialize two pointers, front = 0 and back = n - 1.
  2. 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.
  3. 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

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.




Comment

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