grid47 Exploring patterns and algorithms
Oct 9, 2024
4 min read
Solution to LeetCode 283: Move Zeroes Problem
Given an integer array nums, move all the zeros to the end while maintaining the relative order of the non-zero elements. Perform the operation in-place without making a copy of the array.
Problem
Approach
Steps
Complexity
Input: The input is an array `nums` of integers.
Example: For example, `nums = [0, 5, 0, 2, 8]`.
Constraints:
• 1 <= nums.length <= 10^4
• -2^31 <= nums[i] <= 2^31 - 1
Output: Return the array with all zeros moved to the end while keeping the relative order of non-zero elements intact.
Example: For `nums = [0, 5, 0, 2, 8]`, the output should be `[5, 2, 8, 0, 0]`.
Constraints:
• The operation must be performed in-place.
Goal: Move all zeros in the `nums` array to the end while maintaining the relative order of non-zero elements.
Steps:
• Use a variable `j` to track the position of the next non-zero element.
• Iterate through the array, and for each non-zero element, swap it with the element at position `j`, then increment `j`.
• After the iteration, all elements from `j` to the end of the array should be zeros.
Goal: The input array should be modified in-place.
Steps:
• The array length must be between 1 and 10^4.
• Each element must be a 32-bit integer.
Assumptions:
• The array may contain any number of zeros, including zero zeros.
• Input: For `nums = [0, 5, 0, 2, 8]`
• Explanation: All zeros are moved to the end while keeping the relative order of the non-zero elements intact. The output is `[5, 2, 8, 0, 0]`.
• Input: For `nums = [4, 0, 1, 3]`
• Explanation: The zeros are moved to the end while maintaining the relative order of the non-zero elements. The output is `[4, 1, 3, 0]`.
Approach: We will iterate over the array and swap each non-zero element with the element at the position tracked by `j`. This will push all zeros to the end of the array.
Observations:
• The problem requires an in-place solution, meaning no extra array should be created.
• The approach involves shifting non-zero elements to the left while moving zeros to the right in a single pass.
Steps:
• Initialize a variable `j` to 0, which will keep track of the position for the next non-zero element.
• Iterate through the array. For each non-zero element, swap it with the element at index `j`, then increment `j`.
• After the loop ends, set all elements from `j` to the end of the array to zero.
Empty Inputs:
• An empty array should not result in any errors, but it should return an empty array.
Large Inputs:
• Ensure that the solution works efficiently for arrays of the maximum allowed length (10^4).
Special Values:
• If the array contains no zeros, the array should remain unchanged.
Constraints:
• The solution must work within the given time and space constraints.
voidmoveZeroes(vector<int>& nums) {
int j =0;
for(int i =0; i < nums.size(); i++) {
if(nums[i] !=0)
swap(nums[i], nums[j]), j++;
}
while(j < nums.size())
nums[j++] =0;
}
1 : Function Definition
voidmoveZeroes(vector<int>& nums) {
Defines the function `moveZeroes`, which takes a reference to a vector of integers `nums` and moves all zeroes in the array to the end while maintaining the order of the non-zero elements.
2 : Initialize Pointer
int j =0;
Initializes the pointer `j` to keep track of the position where the next non-zero element should be placed.
3 : Loop Through Array
for(int i =0; i < nums.size(); i++) {
Starts a loop to iterate through each element of the array `nums` using index `i`.
4 : Check Non-Zero Element
if(nums[i] !=0)
Checks if the current element is non-zero.
5 : Swap Elements
swap(nums[i], nums[j]), j++;
Swaps the current non-zero element `nums[i]` with the element at position `j` and increments `j` to the next position for the next non-zero element.
6 : Place Remaining Zeros
while(j < nums.size())
Starts a while loop to fill the remaining positions in the array with zeroes, starting from index `j`.
7 : Assign Zeroes
nums[j++] =0;
Assigns zero to the current position `j` and increments `j` until all remaining positions are filled with zeroes.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n) since we are iterating over the array once.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is O(1) as the solution only uses a constant amount of extra space for the variable `j`.
