title: Apply Operations to an Array
slug: apply-operations-to-an-array
difficulty: easy
leetcode_id: 2460
leetcode_url: https://leetcode.com/problems/apply-operations-to-an-array/
categories:
  - arrays
  - two-pointers
patterns:
  - slug: two-pointers
    is_optimal: true

function_signature: "def apply_operations(nums: list[int]) -> list[int]:"

test_cases:
  visible:
    - input: { nums: [1, 2, 2, 1, 1, 0] }
      expected: [1, 4, 2, 0, 0, 0]
    - input: { nums: [0, 1] }
      expected: [1, 0]
  hidden:
    - input: { nums: [1, 1] }
      expected: [2, 0]
    - input: { nums: [2, 2, 2] }
      expected: [4, 2, 0]
    - input: { nums: [0, 0, 0] }
      expected: [0, 0, 0]
    - input: { nums: [1, 2, 3, 4] }
      expected: [1, 2, 3, 4]
    - input: { nums: [1, 1, 1, 1] }
      expected: [2, 2, 0, 0]

description: |
  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 i<sup>th</sup> operation (**0-indexed**), you will apply the following on the i<sup>th</sup> element of `nums`:

  - If `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.

  - For example, 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.

constraints: |
  - `2 <= nums.length <= 2000`
  - `0 <= nums[i] <= 1000`

examples:
  - 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].
  - input: "nums = [0,1]"
    output: "[1,0]"
    explanation: "No operation can be applied, we just shift the 0 to the end."

explanation:
  intuition: |
    This problem breaks down into two distinct phases that can be tackled independently.

    Think of it like a two-step assembly line process: first, you walk through the array performing "merges" where adjacent equal elements combine (the left one doubles, the right one becomes zero). Then, as a separate cleanup step, you push all the zeros to the back — like sweeping debris to one side of a factory floor.

    The key insight is that the **order of operations matters**. Since we process elements sequentially from left to right, a merge at position `i` can create new zeros that might affect subsequent comparisons. For example, if we have `[2, 2, 2]`, merging at index 0 gives us `[4, 0, 2]` — the newly created zero at index 1 doesn't equal the `2` at index 2, so no further merge happens there.

    The second phase — shifting zeros to the end — is a classic **two-pointer** pattern. Instead of actually "moving" zeros, we place all non-zero elements at the front in order, then fill the remaining positions with zeros.

  approach: |
    We solve this in two phases:

    **Phase 1: Apply the merge operations**

    - Iterate through indices `0` to `n - 2` (we compare `nums[i]` with `nums[i + 1]`)
    - For each index `i`, check if `nums[i] == nums[i + 1]`
    - If equal: double `nums[i]` and set `nums[i + 1] = 0`
    - If not equal: skip to the next index

    &nbsp;

    **Phase 2: Shift zeros to the end (Two Pointers)**

    - Use a `write_index` pointer starting at `0`
    - Iterate through the array with a `read_index`
    - When we find a non-zero element, write it to `write_index` and increment `write_index`
    - After processing all elements, fill positions from `write_index` to end with zeros

    &nbsp;

    **Step 3: Return the result**

    - The array is now modified in-place with all operations applied and zeros shifted to the end

  common_pitfalls:
    - title: Forgetting Sequential Processing
      description: |
        The operations must be applied **sequentially**, not all at once. If you scan the array for all equal adjacent pairs first and then apply all merges simultaneously, you'll get wrong results.

        For example, with `[1, 1, 1]`:
        - **Correct (sequential):** At i=0, merge to get `[2, 0, 1]`. At i=1, `0 != 1`, skip. Result after shifting: `[2, 1, 0]`
        - **Wrong (simultaneous):** Both pairs (0,1) and (1,2) are equal, so you might merge both, getting `[2, 0, 2]` which is incorrect.

        Always process one index at a time, using the updated array state for subsequent comparisons.
      wrong_approach: "Pre-scan for all matches, then apply all merges"
      correct_approach: "Process index by index, applying changes immediately"

    - title: Off-by-One in the Loop Boundary
      description: |
        When iterating to apply operations, you compare `nums[i]` with `nums[i + 1]`. If your loop goes to `n - 1` (inclusive), you'll access `nums[n]` which is out of bounds.

        The loop should run from `i = 0` to `i = n - 2` (or equivalently, `i < n - 1`).
      wrong_approach: "for i in range(n)"
      correct_approach: "for i in range(n - 1)"

    - title: Creating a New Array Instead of In-Place Modification
      description: |
        While creating a new result array works, it uses O(n) extra space unnecessarily. The problem can be solved in-place with O(1) extra space using the two-pointer technique for the zero-shifting phase.

        The two-pointer approach overwrites elements as it goes, which is safe because the write pointer never exceeds the read pointer.

  key_takeaways:
    - "**Two-phase problems**: Breaking a problem into distinct phases (merge, then shift) simplifies the logic and makes each part easier to reason about"
    - "**Two-pointer for partitioning**: Moving zeros to the end is a classic application of the two-pointer pattern — one pointer reads, another writes"
    - "**Sequential vs. parallel operations**: Always clarify whether operations in a problem should be applied one at a time (sequential) or all at once (parallel)"
    - "**In-place modification**: When the problem allows modifying the input, use two pointers to achieve O(1) space complexity"

  time_complexity: "O(n). We make two passes through the array: one for the merge operations and one for shifting zeros."
  space_complexity: "O(1). We modify the array in-place and only use a constant number of pointer variables."

solutions:
  - approach_name: Two-Phase Simulation
    is_optimal: true
    code: |
      def apply_operations(nums: list[int]) -> list[int]:
          n = len(nums)

          # Phase 1: Apply merge operations sequentially
          for i in range(n - 1):
              if nums[i] == nums[i + 1]:
                  # Double the current element
                  nums[i] *= 2
                  # Set the next element to zero
                  nums[i + 1] = 0

          # Phase 2: Shift zeros to the end using two pointers
          write_index = 0  # Position to place next non-zero element

          # Move all non-zero elements to the front
          for read_index in range(n):
              if nums[read_index] != 0:
                  nums[write_index] = nums[read_index]
                  write_index += 1

          # Fill remaining positions with zeros
          while write_index < n:
              nums[write_index] = 0
              write_index += 1

          return nums
    explanation: |
      **Time Complexity:** O(n) — Two passes through the array.

      **Space Complexity:** O(1) — In-place modification with only pointer variables.

      We first iterate through the array applying the merge operations. Then we use a classic two-pointer technique to partition the array: non-zero elements move to the front while zeros fill the remaining positions.

  - approach_name: Two-Phase with List Comprehension
    is_optimal: false
    code: |
      def apply_operations(nums: list[int]) -> list[int]:
          n = len(nums)

          # Phase 1: Apply merge operations
          for i in range(n - 1):
              if nums[i] == nums[i + 1]:
                  nums[i] *= 2
                  nums[i + 1] = 0

          # Phase 2: Collect non-zeros, then append zeros
          non_zeros = [x for x in nums if x != 0]
          zeros = [0] * (n - len(non_zeros))

          return non_zeros + zeros
    explanation: |
      **Time Complexity:** O(n) — One pass for merges, one pass for filtering.

      **Space Complexity:** O(n) — Creates new lists for non-zeros and zeros.

      This approach is more readable but uses O(n) extra space. The list comprehension collects all non-zero elements, then we create the appropriate number of zeros and concatenate. Suitable when simplicity is preferred over space efficiency.
