Leetcode: 2460. Apply Operations to an Array

Problem Statement

Understand the problem

Given an array \(a\) of non-negative integers. Simulate the following rules:

  • \(a[i]=a[i]*2\) and \(a[i+1]=0\) if \(a[i]=a[i+1]\);
  • \(a[i]\) doesn't change.

Useful prompts

Devise a plan

Simulate the rules while saving the new non-zero values. After that, we shift all number different than zero to the beginning of the array and fill the rest of the array with zeros. Time is \(O(n)\) and space is \(O(1)\).

Carry out the plan

class Solution:
    def applyOperations(self, nums: List[int]) -> List[int]:
        N = len(nums)
        for i in range(N):
            if i + 1 < N and nums[i] == nums[i + 1]:
                nums[i] = nums[i] * 2
                nums[i + 1] = 0
        i = 0
        for n in nums:
            if n > 0:
                nums[i] = n
                i += 1
        while i < N:
            nums[i] = 0
            i += 1
        return nums