Solving Array Operations Efficiently

Problem Statement

Given a 0-indexed array nums of size n consisting of non-negative integers., we need to:

1. Apply n-1 operations where:

   • If nums[i] == nums[i+1], double nums[i] and set nums[i+1] to 0.

   • Otherwise, skip the operation.

2. Shift all 0s to the end while maintaining relative order of non-zero elements.

Example:

• Input: nums = [1,2,2,1,1,0]

• Output: [1,4,2,0,0,0]

---

Thought Process Before Solving

1. Optimal approach:

   • Step 1: Perform the operations sequentially.

   • Step 2: Shift all zeros to the end of the array.

2. Think About Edge Cases:

   • What if all elements are the same?

   • What if the array contains only zeros?

3. Optimize for Efficiency:

   • Aim for a solution that runs in linear time, i.e., O(n).

   • Avoid unnecessary nested loops or operations that increase time complexity.

---

Solution Code

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] *= 2; 
                nums[i+1] = 0;
            }
        }
        int j = 0; 
        for(int i = 0; i < n; i++) {
            if(nums[i] != 0) {
                nums[j++] = nums[i];
            }
        }
        while(j < n) {
            nums[j++] = 0;
        }
        return nums; 
    }
};

---

Time & Space Complexity Analysis

Time Complexity:

• First loop runs O(n-1) ≈ O(n).

• Second loop to shift non-zero elements runs in O(n).

• Final loop to fill zeros runs in O(n).

• Total Complexity: O(n) + O(n) + O(n) = O(n) (Linear time complexity)

Space Complexity:

• We modify the array in-place, so no extra space is used.

• Space Complexity: O(1) (Constant space)

---