# Apply Operations to an Array
**Difficulty:** EASY
[External](https://leetcode.com/problems/apply-operations-to-an-array)
Canonical: https://scaleengineer.com/dsa/problems/apply-operations-to-an-array
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** Array
---
## Problem
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 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.

**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 <= 2000`
* `0 <= nums[i] <= 1000`

# Approaches
## Two-Pass Simulation with Extra Array
This approach directly simulates the problem statement in two distinct phases. First, it applies all the operations on the input array. Second, it creates a new array and populates it with the non-zero elements from the modified input array, effectively shifting all zeros to the end.
**Time:** O(n) - The first loop runs `n-1` times, and the second loop runs `n` times. This gives a total time complexity of O(n-1 + n) which simplifies to O(n). · **Space:** O(n) - We use an additional array `result` of size `n` to store the final arrangement.
**Pros:** Simple to understand and implement as it directly follows the problem description's two steps.
**Cons:** Uses extra space proportional to the input size, which is inefficient for large arrays.
### Explanation
### Phase 1: Apply Operations
We iterate through the `nums` array from the first element up to the second-to-last element (`i` from 0 to `n-2`). In each iteration, we check if `nums[i]` is equal to `nums[i+1]`. If they are equal, we double `nums[i]` and set `nums[i+1]` to zero. This is done in-place on the original `nums` array.

### Phase 2: Shift Zeros
We create a new array, `result`, of the same size `n`, which is by default initialized with zeros in Java. We use a pointer, `writeIndex`, initialized to 0, to keep track of the next position to fill in the `result` array. We iterate through the modified `nums` array. For each element, if it's not zero, we copy it to `result[writeIndex]` and increment `writeIndex`. After iterating through all elements of `nums`, the `result` array will contain all non-zero elements at the beginning, followed by zeros.

```java
class Solution {
    public int[] applyOperations(int[] nums) {
        int n = nums.length;

        // Phase 1: Apply operations
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] == nums[i + 1]) {
                nums[i] *= 2;
                nums[i + 1] = 0;
            }
        }

        // Phase 2: Shift zeros to the end using an extra array
        int[] result = new int[n];
        int writeIndex = 0;
        for (int num : nums) {
            if (num != 0) {
                result[writeIndex++] = num;
            }
        }
        
        return result;
    }
}
```
### Algorithm
- 1. Iterate from `i = 0` to `n-2` on the `nums` array.
- 2. If `nums[i]` equals `nums[i+1]`, update `nums[i] = nums[i] * 2` and `nums[i+1] = 0`.
- 3. Create a new integer array `result` of size `n`.
- 4. Initialize a `writeIndex` to 0.
- 5. Iterate through the modified `nums` array.
- 6. If the current element `num` is not 0, set `result[writeIndex] = num` and increment `writeIndex`.
- 7. Return the `result` array.

## Two-Pass In-Place Modification
This approach improves upon the previous one by eliminating the need for an extra array. It still performs the two main steps sequentially, but the second step (shifting zeros) is done in-place, thus saving space.
**Time:** O(n) - The first loop for operations is O(n). The second phase involves two loops that together iterate through the array once, which is also O(n). The total complexity is O(n) + O(n) = O(n). · **Space:** O(1) - The modifications are done in-place, and we only use a few extra variables for indices, resulting in constant extra space.
**Pros:** Space-efficient as it avoids creating a new array, using only constant extra space.
**Cons:** Requires two separate passes over the array data, which might be slightly less performant than a single-pass solution due to cache effects.
### Explanation
### Phase 1: Apply Operations
This phase is identical to the first approach. We iterate from `i = 0` to `n-2` and apply the specified operations directly on the `nums` array.

### Phase 2: Shift Zeros In-Place
We use a "write pointer" (`writeIndex`) to manage the placement of non-zero elements. This pointer starts at index 0. We iterate through the `nums` array with a "read pointer" (`i`). Whenever we encounter a non-zero element at `nums[i]`, we move it to the `nums[writeIndex]` position and then increment `writeIndex`. This effectively collects all non-zero elements at the beginning of the array, preserving their relative order. After this loop, all non-zero elements are in `nums[0...writeIndex-1]`. We then perform a second loop from `writeIndex` to `n-1` to fill the remaining positions of the array with zeros.

```java
class Solution {
    public int[] applyOperations(int[] nums) {
        int n = nums.length;

        // Phase 1: Apply operations
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] == nums[i + 1]) {
                nums[i] *= 2;
                nums[i + 1] = 0;
            }
        }

        // Phase 2: Shift zeros to the end in-place
        int writeIndex = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] != 0) {
                nums[writeIndex++] = nums[i];
            }
        }

        // Fill the rest of the array with zeros
        while (writeIndex < n) {
            nums[writeIndex++] = 0;
        }
        
        return nums;
    }
}
```
### Algorithm
- 1. Iterate from `i = 0` to `n-2` on the `nums` array.
- 2. If `nums[i]` equals `nums[i+1]`, update `nums[i] = nums[i] * 2` and `nums[i+1] = 0`.
- 3. Initialize a `writeIndex` to 0.
- 4. Iterate through `nums` from `i = 0` to `n-1`.
- 5. If `nums[i]` is not 0, set `nums[writeIndex] = nums[i]` and increment `writeIndex`.
- 6. Iterate from `writeIndex` to `n-1`.
- 7. Set `nums[i] = 0` for each element in this range.
- 8. Return the modified `nums` array.

## Optimized Single-Pass In-Place Approach
This is the most efficient approach, combining both the operation and zero-shifting steps into a single pass over the array. It modifies the array in-place, using a write pointer to build the final result without needing extra space or multiple passes.
**Time:** O(n) - We iterate through the array only once. · **Space:** O(1) - All operations are performed in-place.
**Pros:** Most efficient in both time and space.; It avoids multiple passes over the array, which can improve performance due to better data locality and cache usage.
**Cons:** The logic is slightly more complex to reason about compared to the two-pass approaches, as operations and shifting are interleaved.
### Explanation
The core idea is to process each element `nums[i]` and immediately place its final, post-operation value into the correct position in the array. We use a `writeIndex` pointer, initialized to 0, to track the position for the next non-zero element. We iterate through the array with a read pointer `i` from `0` to `n-1`. In each iteration, we first apply the operation if applicable (i.e., if `i < n-1`). After this, the value of `nums[i]` is final. If it's non-zero, we swap it into the `nums[writeIndex]` position. This works because any element at `nums[writeIndex]` that gets swapped back to `nums[i]` must be a zero that has already been processed. After the single loop, all non-zero elements are compacted at the front, and the rest of the array is filled with zeros automatically as a result of the swaps.

```java
class Solution {
    public int[] applyOperations(int[] nums) {
        int n = nums.length;
        int writeIndex = 0;

        for (int i = 0; i < n; i++) {
            // Apply operation if possible
            if (i + 1 < n && nums[i] == nums[i + 1]) {
                nums[i] *= 2;
                nums[i + 1] = 0;
            }
            
            // If current element is non-zero, move it to the write position
            if (nums[i] != 0) {
                // Swap non-zero element to the front
                int temp = nums[i];
                nums[i] = nums[writeIndex];
                nums[writeIndex] = temp;
                writeIndex++;
            }
        }
        
        return nums;
    }
}
```
### Algorithm
- 1. Initialize a `writeIndex` to 0.
- 2. Iterate through the `nums` array with a read index `i` from `0` to `n-1`.
- 3. Inside the loop, first check if `i < n-1` and `nums[i] == nums[i+1]`. If so, apply the operation: `nums[i] *= 2` and `nums[i+1] = 0`.
- 4. After the potential operation, check if the current element `nums[i]` is non-zero.
- 5. If `nums[i]` is non-zero, swap `nums[i]` with `nums[writeIndex]`, and then increment `writeIndex`.
- 6. After the loop, the array is in the desired final state. Return `nums`.

# Solutions
### Java

```java
class Solution {
public
  int[] applyOperations(int[] nums) {
    int n = nums.length;
    for (int i = 0; i < n - 1; ++i) {
      if (nums[i] == nums[i + 1]) {
        nums[i] <<= 1;
        nums[i + 1] = 0;
      }
    }
    int[] ans = new int[n];
    int i = 0;
    for (int x : nums) {
      if (x > 0) {
        ans[i++] = x;
      }
    }
    return ans;
  }
}

```

### Python

```python
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

```

### CPP

```cpp
class Solution {
public:
  vector<int> applyOperations(vector<int> &nums) {
    int n = nums.size();
    for (int i = 0; i < n - 1; ++i) {
      if (nums[i] == nums[i + 1]) {
        nums[i] <<= 1;
        nums[i + 1] = 0;
      }
    }
    vector<int> ans(n);
    int i = 0;
    for (int &x : nums) {
      if (x) {
        ans[i++] = x;
      }
    }
    return ans;
  }
};

```