#2460

Easy

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Apply Operations to an Array

Name: Interview AiBox
Availability: InStock
Rating: 4.9 (10000 reviews)

Transform an array by applying adjacent doubling operations and shifting zeros efficiently using two-pointer scanning techniques.

array two pointers simulation

Problem Statement

You are given a 0-indexed array nums of length n containing non-negative integers. For each index i from 0 to n - 2, if nums[i] equals nums[i + 1], double nums[i] and set nums[i + 1] to zero. After completing all operations, shift all zeros to the end while preserving the order of non-zero elements.

Return the final state of the array after applying the operations and moving all zeros to the end. Focus on efficiently simulating this process using two-pointer scanning with invariant tracking to avoid unnecessary swaps.

Examples

Example 1

Input: nums = [1,2,2,1,1,0]

Output: [1,4,2,0,0,0]

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]

No operation can be applied, we just shift the 0 to the end.

Constraints

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

Solution Approach

Simulate operations with one pass

Iterate over the array using a single loop, checking if nums[i] equals nums[i + 1]. If they are equal, multiply nums[i] by 2 and set nums[i + 1] to zero immediately. This preserves the two-pointer invariant of the next element being ready for comparison.

Shift zeros efficiently

After performing all doubling operations, use a write pointer to overwrite zeros by copying non-zero elements forward. Then fill the remaining positions with zeros. This avoids nested loops and keeps the time complexity linear.

Maintain constant space

All operations are done in-place, and no extra arrays are needed. The two-pointer scanning and zero-shifting together guarantee O(1) extra space while respecting the order of non-zero elements.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

Time complexity is O(n) because each element is scanned once for doubling and once for zero-shifting. Space complexity is O(1) since operations modify the array in-place without additional storage.

What Interviewers Usually Probe

Do you understand how to detect adjacent equal values efficiently?
Can you maintain element order while moving zeros to the end?
Will your approach handle the full range of array lengths within O(n) time?

Common Pitfalls or Variants

Common pitfalls

Forgetting to set the second element to zero after doubling, breaking the simulation invariant.
Using nested loops for zero-shifting, which increases time complexity unnecessarily.
Altering the relative order of non-zero elements when moving zeros to the end.

Follow-up variants

Apply similar operations but triple the first element instead of doubling if adjacent elements match.
Allow operations to skip a fixed number of elements instead of only adjacent pairs.
Modify the problem to handle negative numbers while still doubling and shifting zeros.

FAQ

What is the core pattern used in Apply Operations to an Array?

The problem uses two-pointer scanning with invariant tracking to efficiently detect adjacent equal values and move zeros to the end.

Can I solve this problem without extra space?

Yes, by modifying the array in-place and using a write pointer for zero-shifting, you achieve O(1) extra space.

Why is a single pass enough for the doubling operations?

Because each operation only affects the current and next elements, scanning once preserves the required simulation order.

How do I maintain the relative order of non-zero elements?

Use a write pointer to place non-zero elements sequentially and fill remaining positions with zeros after all operations.

What common mistakes should I avoid in this problem?

Do not forget to zero the second element after doubling, do not use nested loops for zero-shifting, and always preserve non-zero order.

terminal

Solution

Solution 1: Simulation

We can directly simulate according to the problem description.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def applyOperations(self, nums: List[int]) -> List[int]:
        n = len(nums)
        for i in range(n - 1):
            if nums[i] == nums[i + 1]:
                nums[i] <<= 1
                nums[i + 1] = 0
        ans = [0] * n
        i = 0
        for x in nums:
            if x:
                ans[i] = x
                i += 1
        return ans

Continue Practicing

#2462 total cost to hire k workers #2562 find the array concatenation value #2161 partition array according to given pivot