Welcome Reader!
We hope that you are doing great with Arrays so far. In the last blog, we discussed the problem of detecting Missing Ranges from Arrays. We hope you enjoyed reading it. In this article, we will discuss the next problem based on “Arrays” i.e. “Move Zeroes.” Before you move any further, it is advised that you give this problem a fair try. Let’s jump to the problem.
Problem Statement:
Given an integer array nums, move all 0s to the end while maintaining the relative order of the non-zero elements.
Understanding the problem:
1. You are given an array with integers.
2. You must shift all the zeros at the last of the array and all non-zero elements in front.
For example:
Sample Input -> [1,0,3,0,12]
Sample Output -> [1,3,12,0,0,0]
HOW?
We can shift all Non-Zero elements in front by traversing and swapping every element with every Zero elements.
Approach:
Create a pointer variable J to keep track of all Non-Zero elements in the array.
Traverse the array from starting till the end of the array.
Check every element, if it is a Non-Zero element or not.
If the element is a Non-Zero element, Swap the Jth element with the Ith element used in traversing the loop.
Increment value of J every time a Non-Zero element is caught.
Let’s try to code this!
1.) Create a variable and initialize it with 0.
2.) Traverse a for loop from 0 to the array's length.
3.) Inside the loop, check for every element if it is a Non-Zero element or not.
4.) If an element is Non-Zero, swap that element with the element on index j (variable initialized in the beginning).
5.) Increment the value of the j variable and traverse further.
Complexities:
Time Complexity: O(N)
Where N = length of the input string.
As we traverse every array element for one time, the time complexity is O(N).
Space Complexity: O(1)
As we have created No extra space, the space complexity is O(1).
Complete Code:
We hope that this article was helpful.
You can contact us via our website. Doubts, suggestions, and feedback are always welcomed. You are also advised to follow the sequence of modules and questions on our website. Keep practicing more and more problems daily. Meditate enough on each step of each problem.
“Don’t let the fear of losing be greater than the excitement of winning.”
-Robert Kiyosaki
All the best for an exciting future!
Happy Coding!
Contributed by: Parth Mathur
Regards,
The Daily Code Team.