Given an integer array nums, move all 0‘s to the end of it while maintaining the relative order of the non-zero elements.
Note that you must do this in-place without making a copy of the array.
Here’s the [Problem Link] to begin with.
BRUTE FORCE SOLUTION
1. Problem Statement
Our goal is to moving all zeros in a given array nums to the end while maintaining the relative order of the non-zero elements. The operation is done in-place, modifying the original array without returning any value.
Input:
- nums: A list of integers, where zeros and non-zeros are mixed.
Output:
- No explicit output; the function modifies the array nums directly, placing all zero elements at the end while keeping the order of non-zero elements unchanged.
2. Intuition and Approach
The approach taken in this code involves separating the non-zero elements from the zeros to streamline the rearrangement process:
- Traverse the array and copy all non-zero elements into a temporary list called temp.
- Replace the beginning of the original array with the contents of temp, effectively moving all non-zero elements to the front.
- Fill the remainder of the array with zeros, starting from the index where the non-zero elements end.
This method ensures that non-zero elements retain their original sequence, and all zeros are pushed to the end of the array.
3. Code
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
n = len(nums)
temp = []
# Copy non-zero elements from original to temp array
for i in range(n):
if nums[i] != 0:
temp.append(nums[i])
# Number of non-zero elements
nz = len(temp)
# Copy elements from temp to fill first nz fields of original array
for i in range(nz):
nums[i] = temp[i]
# Fill the rest of the cells with 0
for i in range(nz, n):
nums[i] = 0- Initialization and Temporary Storage:
- A temporary list temp is created to store non-zero elements found during the traversal of nums.
- Extract Non-Zero Elements:
- The array nums is traversed, and each non-zero element is appended to temp.
- Refill Original Array with Non-Zero Elements:
- The length of temp, stored in nz, indicates the number of non-zero elements.
- The first nz positions of nums are overwritten with the elements from temp, placing all non-zero elements at the start of nums.
- Fill Remaining Positions with Zeros:
- The remainder of the array from index nz to n (length of nums) is filled with zeros, moving all zeros to the end of the array.
4. Dry Run
Let’s go through the code step by step, using images to illustrate the detailed dry run process.
First, put all the non-zero elements in temp variable.
Now put all the non zero elements in start indexes.
5. Edge Cases
- All Zeros: If nums contains only zeros (e.g., nums = [0, 0, 0]), the function should fill nums with zeros, which it does effectively.
- No Zeros: If there are no zeros (e.g., nums = [1, 2, 3]), nums remains unchanged after the operation, as expected.
- Empty Array: If nums is empty, the function should handle this by performing no operations.
6. Time and Space Complexity
- Time Complexity: The complexity is O(n) due to three separate but sequential traversals of the array (n is the length of nums): one to fill temp, one to copy non-zeros back, and one to add zeros.
- Space Complexity: The space complexity is O(n) for the temporary list temp, which in the worst case (no zeros) stores a copy of all elements from nums.
Efficiency: The method is effective for its clarity and ensures that all non-zero elements maintain their order relative to each other. However, the space efficiency could be improved by using a different approach that does not require additional storage, such as a two-pointer technique that swaps zeros with non-zero elements in-place without extra storage.
OPTIMAL SOLUTION
1. Problem Statement
Our goal is to rearrange an array nums by moving all zero elements to the end while maintaining the relative order of the non-zero elements. The task is accomplished in-place, modifying the original array without returning any value.
Input:
- nums: A list of integers where zero and non-zero elements may be mixed.
Output:
- No explicit output is provided; the array nums is modified directly, with all zero elements moved to the end.
2. Intuition and Approach
The approach used here employs the two-pointer technique to efficiently separate zero and non-zero elements:
- The first pointer, i, is used to find the first zero in the array.
- The second pointer, j, starts from i + 1 and is used to find the next non-zero element to swap with the zero at index i.
- This process continues, incrementally moving the i pointer each time a swap is made, effectively “collecting” non-zero elements at the start of the array and pushing zeros to the end.
This method ensures that the operations are done in-place, and by avoiding the use of extra storage or multiple passes, it optimizes both space and time efficiency.
3. Code
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
if len(nums) == 1:
return
i = 0
while i < len(nums):
if nums[i] == 0:
break
i += 1
else:
return
j = i + 1
while j < len(nums):
if nums[j] != 0:
nums[i], nums[j] = nums[j], nums[i]
i += 1
j += 1- Initial Checks:
- If the array contains only one element, no action is needed, and the function returns immediately.
- Find First Zero:
- The i pointer is used to locate the first zero in the array. If no zero is found and i reaches the end of the array, the function exits as no zeros need moving.
- Rearranging Elements:
- The j pointer starts from the next index after i and scans for non-zero elements.
- When a non-zero element is found, it is swapped with the zero at the i index. After the swap, i is incremented to point to the next zero, ready for a future swap.
- This process continues until j has scanned through to the end of the array.
4. Dry Run
Let’s go through the code step by step, using images to illustrate the detailed dry run process.
5. Edge Cases
- All Zeros: If nums contains only zeros (e.g., nums = [0, 0, 0]), the array remains unchanged, but the method handles it efficiently.
- No Zeros: If there are no zeros (e.g., nums = [1, 2, 3]), the method terminates early after the initial scan, leaving the array unchanged.
- Empty Array: If nums is empty, the function does nothing, as expected.
- Single Element: A single element (whether zero or non-zero) needs no action, as handled by the initial return.
6. Time and Space Complexity
- Time Complexity: The complexity is O(n), where n is the length of the array. Each element is considered at most once by the j pointer.
- Space Complexity: The complexity is O(1) as the solution modifies the array in place without using additional storage.
Efficiency: This method is space-efficient due to its in-place operation and time-efficient due to its linear complexity. By directly moving non-zero elements forward and letting zeros fill the remaining indices, it maintains the order of non-zero elements without additional data structures.
For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.
