Apply Operations to an Array - Solution & Explanation
Problem Statement
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:
- If
nums[i] == nums[i + 1], then multiplynums[i]by2and setnums[i + 1]to0. Otherwise, you skip this operation.
After performing all the operations, shift all the 0's to the end of the array.
- For example, the array
[1,0,2,0,0,1]after shifting all its0'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] <= 1000
Approach Overview
Problem Overview: You receive an integer array. First, scan left to right and apply a rule: if nums[i] == nums[i+1], double nums[i] and set nums[i+1] to zero. After completing this pass, move all zeros to the end while keeping the relative order of non‑zero elements. The result is the transformed array.
Approach 1: In-Place Modification with Zero Collection (Time: O(n), Space: O(n))
This method directly simulates the problem statement. Iterate through the array once and apply the merge rule: whenever two adjacent values are equal, update nums[i] to 2 * nums[i] and set nums[i+1] to zero. After this pass, build a new result by collecting all non-zero elements in order and appending the required number of zeros at the end. The key insight is separating the two phases: first apply the operation exactly as described, then perform a stable zero shift. This approach is easy to reason about and mirrors the problem statement, making it a solid baseline implementation using a simple array traversal and simulation.
Approach 2: Two-Pointer Technique for Zero Shift (Time: O(n), Space: O(1))
After applying the merge operation in a single left‑to‑right pass, shift non-zero values forward using the two pointers pattern. Maintain a write pointer that marks where the next non-zero element should go. Scan the array with another pointer. When a non-zero value appears, write it at the write index and advance the pointer. After processing all elements, fill the remaining positions with zeros. This avoids creating a new array and keeps the algorithm fully in-place. The insight is that the second phase is identical to the classic “move zeros to the end” problem.
Recommended for interviews: The two-pointer approach is typically preferred. It keeps the algorithm linear at O(n) time while using O(1) extra space. Showing the straightforward simulation first demonstrates that you understand the problem mechanics. Following it with the in-place two-pointer optimization shows stronger algorithmic thinking and familiarity with common array patterns.
Approach 1: In-Place Modification with Zero Collection
This 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.
Complexity
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.
Approach 2: Two-Pointer Technique for Zero Shift
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.
Complexity
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 3: Simulation
We can directly simulate according to the problem description.
First, we traverse the array nums. For any two adjacent elements nums[i] and nums[i+1], if nums[i] = nums[i+1], then we double the value of nums[i] and change the value of nums[i+1] to 0.
Then, we create an answer array ans of length n, and put all non-zero elements of nums into ans in order.
Finally, we return the answer array ans.
The time complexity is O(n), where n is the length of the array nums. Ignoring the space consumption of the answer, the space complexity is O(1).
Complexity Comparison
| 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. |
| Simulation | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| In-Place Modification with Zero Collection | O(n) | O(n) | When clarity is more important than memory usage; mirrors the problem statement directly |
| Two-Pointer Technique for Zero Shift | O(n) | O(1) | Preferred for interviews and production when memory usage must stay constant |
Video Solution
Apply Operations to an Array - Leetcode 2460 - Python • NeetCodeIO • 6,003 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Apply Operations to an Array easy or hard?
Apply Operations to an Array Python/Java solution
How to solve Apply Operations to an Array in O(n)?
What is the best approach for Apply Operations to an Array?
Is Apply Operations to an Array asked at Google/Amazon/Meta?
What data structure is used in Apply Operations to an Array?
What is the time complexity of Apply Operations to an Array?
Ready to solve this problem?
Practice Apply Operations to an Array with our built-in code editor and test cases.
Practice on FleetCode