We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Apply Operations to an Array

Difficulty: Easy

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 ith operation, if nums[i] == nums[i + 1], then multiply nums[i] by 2 and set nums[i + 1] to 0. After performing all operations, shift all the 0s to the end of the array. Return the resulting array.

Key Insights

  • The operations are applied sequentially, meaning each operation affects the next operations.
  • When two adjacent elements are equal, one is doubled, and the other is set to zero.
  • After all operations, any zeros in the array must be moved to the end while maintaining the order of non-zero elements.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1) (in-place transformation)

Solution

The solution involves iterating through the array and applying the operations as specified. We will use a single pass to apply the operations and a second pass to shift zeros to the end. The algorithm follows these steps:

  1. Iterate through the array, checking pairs of adjacent elements.
  2. If a pair is equal, double the first element and set the second to zero.
  3. After processing all pairs, iterate through the array again to collect non-zero elements and count zeros.
  4. Construct the final result by appending the counted zeros to the end of the non-zero elements.

Code Solutions

def apply_operations(nums):
    n = len(nums)
    
    # Apply operations
    for i in range(n - 1):
        if nums[i] == nums[i + 1]:
            nums[i] *= 2  # Double the current element
            nums[i + 1] = 0  # Set the next element to zero
    
    # Shift zeros to the end
    result = []
    zero_count = 0
    for num in nums:
        if num != 0:
            result.append(num)
        else:
            zero_count += 1
    
    # Append zeros to the end
    result.extend([0] * zero_count)
    return result
← Back to All Questions