Apply Operations to an Array

Difficulty: Easy | Acceptance: 74.70% | Paid: No Topics: Array, Two Pointers, Simulation

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 element with index i:

If nums[i] == nums[i + 1], then nums[i] becomes 2 * nums[i], otherwise nums[i] becomes 0. After performing all operations, shift all the 0’s of the array to the right end of the array.

For example, the array [1,0,2,0,0,1] after shifting all 0’s to the right becomes [1,2,1,0,0,0].

Return the resulting array.

• Examples
• Constraints
• In-place Simulation
• Auxiliary Array

Examples

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 double nums[1] and replace nums[2] with 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 double nums[3] and replace nums[4] with 0. The array becomes [1,4,0,2,0,0].
- i = 4: nums[4] and nums[5] are not equal, so we skip this operation.
After performing the operations, the array becomes [1,4,0,2,0,0].
After shifting the zeros, the array becomes [1,4,2,0,0,0].

Example 2:

Input: nums = [0,1]
Output: [1,0]
Explanation: No operation is needed, just shift the 0 to the right.

Constraints

1 <= nums.length <= 2000
0 <= nums[i] <= 1000

In-place Simulation

Intuition We first iterate through the array to apply the doubling and zeroing logic. Then, we use a two-pointer technique to move all non-zero elements to the front, effectively shifting zeros to the end without using extra space.

Steps

• Iterate from the first element to the second-to-last element.
• If the current element equals the next element, double the current element and set the next element to 0.
• Use a pointer to track the position for the next non-zero element.
• Iterate through the array again, copying non-zero elements to the front.
• Fill the remaining positions in the array with zeros.

class Solution:
    def applyOperations(self, nums: List[int]) -> List[int]:
        n = len(nums)
        
        # Step 1: Apply operations
        for i in range(n - 1):
            if nums[i] == nums[i + 1]:
                nums[i] *= 2
                nums[i + 1] = 0
        
        # Step 2: Shift zeros to the end
        insert_pos = 0
        for i in range(n):
            if nums[i] != 0:
                nums[insert_pos] = nums[i]
                insert_pos += 1
        
        # Fill remaining with zeros
        while insert_pos < n:
            nums[insert_pos] = 0
            insert_pos += 1
            
        return nums

Complexity

• Time: O(n) — We traverse the array a constant number of times.
• Space: O(1) — We modify the array in place without using extra data structures proportional to the input size.
• Notes: This is the most space-efficient approach.

Auxiliary Array

Intuition We create a new array to store the result. We iterate through the original array, apply the operations, and immediately place non-zero elements into the new array. Finally, we fill the rest of the new array with zeros.

Steps

• Create a result array of the same size as the input.
• Iterate through the input array up to the second-to-last element.
• Apply the doubling and zeroing logic to the input array.
• Iterate through the modified input array and copy non-zero elements to the result array.
• Fill the remaining slots in the result array with zeros.

class Solution:
    def applyOperations(self, nums: List[int]) -> List[int]:
        n = len(nums)
        res = []
        
        # Apply operations
        for i in range(n - 1):
            if nums[i] == nums[i + 1]:
                nums[i] *= 2
                nums[i + 1] = 0
        
        # Build result array
        for num in nums:
            if num != 0:
                res.append(num)
        
        # Append remaining zeros
        res.extend([0] * (n - len(res)))
        return res

Complexity

• Time: O(n) — We iterate through the array a constant number of times.
• Space: O(n) — We allocate a new array to store the result.
• Notes: This approach is often easier to implement and reason about but uses more memory.