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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Apply Operations to an Array

Number: 2551

Difficulty: Easy

Paid? No

Companies: Google, Meta, Amazon

Problem Description

Given an array of non-negative integers, perform n - 1 sequential operations. For the i-th operation, if the element at index i is equal to the element at index i + 1, double the element at index i and set the element at index i + 1 to 0. After processing all operations, shift all the 0's to the end of the array while maintaining the order of the non-zero elements. Return the resulting array.

Key Insights

  • Operations are applied sequentially, influencing subsequent comparisons.
  • Only adjacent equal numbers are merged (doubled) and the next one is set to zero.
  • After merging, shifting zeros to the end can be efficiently done using a two-pointer approach.
  • The overall approach is a simulation followed by an in-place "partition" of non-zero elements.

Space and Time Complexity

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

Solution

The solution comprises two primary phases:

  1. Processing Phase: Iterate through the array and for every index i, if nums[i] equals nums[i + 1], double nums[i] and set nums[i + 1] to 0.
  2. Rearrangement Phase: Use a two-pointer technique to collect all non-zero elements from the processed array and then fill the last portion of the array with 0's. This preserves the order of the non-zero numbers while moving all zeros to the end.

Data structures used include the input array itself and fixed integer variables for tracking positions. The simulation and shifting phases each operate in linear time, ensuring an efficient O(n) solution.

Code Solutions

# Python implementation of the solution.

def apply_operations(nums):
    n = len(nums)
    # Phase 1: Process the merge operations sequentially.
    for i in range(n - 1):
        if nums[i] == nums[i + 1]:
            nums[i] *= 2       # Double the current value.
            nums[i + 1] = 0    # Set the next element to 0.
    
    # Phase 2: Shift non-zero elements to the beginning using a two-pointer approach.
    pos = 0
    for num in nums:
        if num != 0:
            nums[pos] = num  # Place non-zero element at the current position.
            pos += 1
    
    # Fill the rest of the array with zeros.
    while pos < n:
        nums[pos] = 0
        pos += 1
        
    return nums

# Example usage:
nums = [1, 2, 2, 1, 1, 0]
result = apply_operations(nums)
print(result)  # Expected output: [1, 4, 2, 0, 0, 0]
← Back to All Questions