Apply Operations to an Array

Problem Statement

The task involves transforming an array nums containing non-negative integers using a series of operations followed by a shifting step. Specifically, the array is processed through n - 1 operations (where n is the length of the array). For each element at index i in the array:

• If the current element nums[i] is equal to the next element nums[i + 1], the current element is doubled (nums[i] * 2), and the next element is then set to 0.
• If they are not equal, the operation is skipped, and the algorithm proceeds to the next index.

After all these operations have been performed, the final step involves moving all 0 values in the array to the end while retaining the sequence of non-zero values.

The result is an adjusted array that reflects the above rules applied sequentially, and then, zeros are shifted to maintain the integer sequence integrity.

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

Approach and Intuition

Given the nature of the problem, the following approach can be employed:

1. Iterate over the array:
   Iterate from 0 to n-2 (since the operation considers the next element, the last possible index to check is n-2).

2. Check and Apply Operation:
   For each element at index i, check if it's equal to nums[i + 1]:

   • If true, multiply nums[i] by 2 and set nums[i + 1] to 0.
   • If false, simply continue to the next element without any modifications.

3. Shift zeroes to the end:
   After updating all necessary elements:

   • Traverse the array to filter and concatenate non-zero entries and zero entries separately.
   • This can be done effectively by counting non-zero elements as you place them at the start of the array, then filling the remainder of the array with zeroes based on the count of non-zero elements.

This approach ensures that operations are applied sequentially as required, and the separation of the "operation application" phase and the "zero shifting" phase simplifies understanding and implementation of the transformation. The constraints provided allow this method to run efficiently within the limits.

Solutions

class Solution {
public:
    vector<int> processVector(vector<int>& vec) {
        int length = vec.size();
    
        for (int i = 0; i < length - 1; i++) {
            if (vec[i] == vec[i + 1] && vec[i] != 0) {
                vec[i] *= 2;
                vec[i + 1] = 0;
            }
        }
    
        int moveIndex = 0;
        for (int j = 0; j < length; j++) {
            if (vec[j] != 0) {
                vec[moveIndex++] = vec[j];
            }
        }
    
        while (moveIndex < length) {
            vec[moveIndex++] = 0;
        }
    
        return vec;
    }
};