Apply Operations to an Array

The key to this question is to track the prev element, so we know when we have to apply the operation. Our plan is to sort all the non-zero elements first, before iterating through the remaining elements in the array and setting them equal to zero.

To do this, we initialise prev = -1 and index = 0, to track where the next element should be placed, before iterating through the entire array:

• if nums[i] == 0, then we can skip this element and set prev = -1 (so the operation will not be triggered)
• if nums[i] != 0, then:
  • if prev == nums[i], we know we have to apply the operation, so we multiply the previous index by 2, before setting prev = -1 (so the operations will not be triggered)
  • if prev != nums[i], we know we do not apply the operation, but instead set nums[index] = nums[i], update prev = nums[i] and increment index by 1

Now, if index != nums.size(), that implies that there still exists 0 elements that have not been shifted to the end yet. Therefore, we can finish the question by setting all the remaining elements to 0.

code

class Solution {
public:
    vector<int> applyOperations(vector<int>& nums) {
        int index = 0;
        int prev = -1;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] != 0) {
                if (prev != nums[i]) {
                    prev = nums[i];
                    nums[index++] = prev;
                } else if (prev == nums[i]) {
                    nums[index-1] *= 2;
                    prev = -1;
                }
            } else {
                prev = -1;
            }
        }

        for (; index < nums.size(); ++index) {
            nums[index] = 0;
        }
        return nums;
    }
};

complexity

• Time: O(n)
• Space: O(1)