algoadvance

You are given a 0-indexed array nums of size n consisting of non-negative integers.

You need to apply the following operations until the array cannot be changed further:

  1. If nums[i] == nums[i + 1] for some i (0 <= i < n - 1), then set nums[i] = 2 * nums[i] and nums[i + 1] = 0.
  2. After the above operation has been applied to the entire array, shift all 0s to the end of the array.

Return the resulting array after applying the above operations.

Example

Input: nums = [1,2,2,1,1,0] Output: [1,4,2,0,0,0]

Clarifying Questions

  1. What are the constraints on the size of nums?
    • Typically, array problems on LeetCode have constraints provided, e.g., 1 <= nums.length <= 10^4. Let’s assume it is reasonable for typical in-memory processing.
  2. Are there any constraints on the values in nums?
    • The problem states non-negative integers. Usually, this implies integers like 0, 1, 2, etc.
  3. What should we return if the input array has length 1?
    • Given no operation can be performed, we should return the array as-is for length 1.

Strategy

  1. Identify and Apply Operations:
    • Traverse the list and whenever we find two consecutive identical elements (nums[i] == nums[i + 1]), we update nums[i] to 2 * nums[i] and set nums[i + 1] to 0.
  2. Shift Zeros:
    • After performing the above operations, create a new list by pulling in all non-zero elements first and then appending zeros to the end until the length matches the original array length.

Code Implementation

def applyOperations(nums):
    n = len(nums)
    
    # Apply the specified operations
    for i in range(n - 1):
        if nums[i] == nums[i + 1] and nums[i] != 0:
            nums[i] = 2 * nums[i]
            nums[i + 1] = 0
    
    # Shift all zeroes to the end
    result = [num for num in nums if num != 0]
    result += [0] * (n - len(result))
    
    return result

# Example Usage
nums = [1, 2, 2, 1, 1, 0]
print(applyOperations(nums))  # Output: [1, 4, 2, 0, 0, 0]

Time Complexity

  1. Applying Operations:
    • We traverse the list once to check and apply the merging operation. This takes O(n) time.
  2. Shifting Zeros:
    • We create a new list by iterating through the original list to pick non-zero elements and then append zeros. This also takes O(n) time.

Thus, the overall time complexity is O(n), where n is the length of the input array.

We have designed the solution to be efficient and straightforward, ensuring that the operations are performed in linear time.

Try our interview co-pilot at AlgoAdvance.com