You are given a 0-indexed array nums of size n consisting of non-negative integers.
You need to apply n - 1 operations to this array where, in the ith operation (0-indexed), you will apply the following on the ith element of nums:
nums[i] == nums[i + 1], then multiply nums[i] by 2 and set nums[i + 1] to 0. Otherwise, you skip this operation.After performing all the operations, shift all the 0's to the end of the array.
[1,0,2,0,0,1] after shifting all its 0's to the end, is [1,2,1,0,0,0].Return the resulting array.
Note that the operations are applied sequentially, not all at once.
Example 1:
Input: nums = [1,2,2,1,1,0] Output: [1,4,2,0,0,0] Explanation: We do the following operations: - i = 0: nums[0] and nums[1] are not equal, so we skip this operation. - i = 1: nums[1] and nums[2] are equal, we multiply nums[1] by 2 and change nums[2] to 0. The array becomes [1,4,0,1,1,0]. - i = 2: nums[2] and nums[3] are not equal, so we skip this operation. - i = 3: nums[3] and nums[4] are equal, we multiply nums[3] by 2 and change nums[4] to 0. The array becomes [1,4,0,2,0,0]. - i = 4: nums[4] and nums[5] are equal, we multiply nums[4] by 2 and change nums[5] to 0. The array becomes [1,4,0,2,0,0]. After that, we shift the 0's to the end, which gives the array [1,4,2,0,0,0].
Example 2:
Input: nums = [0,1] Output: [1,0] Explanation: No operation can be applied, we just shift the 0 to the end.
Constraints:
2 <= nums.length <= 20000 <= nums[i] <= 1000This approach involves iterating through the array and applying operations only when an element is equal to the next one. After completing all operations, traverse the array again to collect non-zero elements, thus effectively moving all zeros to the end.
The function first iterates through the array to apply the given operations: whenever nums[i] == nums[i+1], it multiplies nums[i] by 2 and sets nums[i+1] to zero. Then, it creates a new list of non-zero elements and appends the appropriate number of zeros to the end.
C
C++
Java
C#
JavaScript
Time complexity is O(n), as we iterate through the array twice, which is efficient given the constraints. Space complexity is O(n) due to the construction of the result array, which is necessary to shift zeros to the end.
This alternative employs a two-pointer technique whereby one pointer processes operational changes and another places non-zero values, thereby compactly reordering elements without needing an auxiliary array.
Utilizing a write_position, this method writes non-zero elements to the front, efficiently shifting zeros to the end. This guarantees minimum in-place changes, effectively combining both stages of operation and zero positioning.
C
C++
Java
C#
JavaScript
Time complexity remains O(n) as the list is traversed twice; space complexity is constant, O(1), as no extra data structures are used besides a few pointers.
| Approach | Complexity |
|---|---|
| In-Place Modification with Zero Collection | Time complexity is O(n), as we iterate through the array twice, which is efficient given the constraints. Space complexity is O(n) due to the construction of the result array, which is necessary to shift zeros to the end. |
| Two-Pointer Technique for Zero Shift | Time complexity remains O(n) as the list is traversed twice; space complexity is constant, O(1), as no extra data structures are used besides a few pointers. |
Apply Operations to an Array - Leetcode 2460 - Python • NeetCodeIO • 4,796 views views
Watch 9 more video solutions →Practice Apply Operations to an Array with our built-in code editor and test cases.
Practice on FleetCode