Problem Informations

• Problem Index: 2460
• Problem Link: Apply Operations to an Array
• Topics: Array, Two Pointers, Simulation

Problem 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^{th}$ operation (0-indexed), you will apply the following on the $i^{th}$ 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 \leq nums.length \leq 2000$
• $0 \leq nums[i] \leq 1000$

Intuition

The problem involves processing an array of non-negative integers by performing a series of operations and then rearranging it to move zeroes to the end. The operations required are specifically defined by conditions involving adjacent elements being equal. The intuition here is to process the array linearly while adjusting it in place to manage space efficiently. This ensures that we maintain the order of non-zero elements while performing the operations according to the problem specification. The key challenge lies in correctly chaining operations and handling the zero-shifting efficiently.

Approach

The approach involves iterating through the array while maintaining two indices: a read index to traverse each element and a write index to update the array as operations are performed. The method followed can be detailed as:

1. Initialize Pointers: Set both readIndex and writeIndex to the start of the array. readIndex will traverse the entire array, whereas writeIndex will be used to modify the array in place.

2. Traverse Array:

   • Loop through the array using readIndex from 0 to n - 1 (n being the length of nums).

   • If nums[readIndex] is zero, skip to the next element since operations involving zero are irrelevant and we want to push zeroes to the end eventually.

   • If nums[readIndex] is not zero:

     • Check if nums[readIndex] equals nums[readIndex + 1] (ensuring readIndex + 1 is within bounds). If they are equal, perform the operation by multiplying nums[readIndex] by 2, then set nums[readIndex + 1] to 0, and move the result to nums[writeIndex]. Increment both readIndex (to skip the next element already modified to 0) and writeIndex.

     • If they are not equal, simply copy nums[readIndex] to nums[writeIndex] and increment writeIndex.

3. Fill Zeros at End: Once all valid operations are performed, fill the remaining part of the array starting from the current writeIndex to the end with zeros to ensure all non-zero elements are compacted towards the beginning followed by zeros.

4. Return the Modified Array: Finally, return the modified array which now contains all operations applied correctly, and all zeros shifted to the end.

This algorithm runs in $O(n)$ time complexity, which is efficient given the constraints, as it involves a single pass to perform all necessary operations and another pass to fill in zeros. The space complexity is $O(1)$, because we modify the array in place without requiring extra space.

Code

C++

class Solution {
public:
    vector<int> applyOperations(vector<int>& nums) {
        int writeIndex = 0;
        int readIndex = 0;

        // Iterate through the input array
        for (; readIndex < nums.size(); readIndex++) {
            // Skip the current element if it is zero
            if (nums[readIndex] == 0) 
                continue;
            
            // If the current element is equal to the next element, multiply it by 2 and mark the next as zero
            else if (readIndex < nums.size() - 1 && nums[readIndex] == nums[readIndex + 1]) {
                nums[writeIndex++] = nums[readIndex++] * 2;
            }
            // Otherwise, just move the current element to the write position
            else {
                nums[writeIndex++] = nums[readIndex];
            }
        }

        // Fill the rest of the array with zeros
        for (; writeIndex < nums.size(); writeIndex++) 
            nums[writeIndex] = 0;

        return nums;
    }
};

Python

class Solution:
    def applyOperations(self, nums):
        writeIndex = 0
        readIndex = 0

        # Iterate through the input array
        while readIndex < len(nums):
            # Skip the current element if it is zero
            if nums[readIndex] == 0:
                readIndex += 1
                continue

            # If the current element is equal to the next element, multiply it by 2 and mark the next as zero
            elif readIndex < len(nums) - 1 and nums[readIndex] == nums[readIndex + 1]:
                nums[writeIndex] = nums[readIndex] * 2
                writeIndex += 1
                readIndex += 1

            # Otherwise, just move the current element to the write position
            else:
                nums[writeIndex] = nums[readIndex]
                writeIndex += 1

            readIndex += 1

        # Fill the rest of the array with zeros
        while writeIndex < len(nums):
            nums[writeIndex] = 0
            writeIndex += 1

        return nums

Complexity

• Time complexity: $O(n)$
  The algorithm consists of two main loops. The first loop iterates over the elements of the array to apply operations and rearrange non-zero elements, and the second loop fills in zeros at the end of the array. Each loop runs at most $n$ times, where $n$ is the size of the array nums. Hence, the overall time complexity is $O(n)$.

• Space complexity: $O(1)$
  The algorithm operates directly on the input array nums without using any additional data structures that scale with the input size, apart from a few integer variables for indexing. Thus, the space complexity is $O(1)$.