Problem Description

You have an array nums with n non-negative integers (0-indexed). You need to perform n - 1 operations on this array following these rules:

For the i-th operation (where i goes from 0 to n-2):

• Look at elements nums[i] and nums[i + 1]
• If they are equal, multiply nums[i] by 2 and set nums[i + 1] to 0
• If they are not equal, skip this operation and move to the next

After completing all operations, move all zeros to the end of the array while maintaining the relative order of non-zero elements.

Key Points:

• Operations are performed sequentially from left to right (not simultaneously)
• Each operation compares the current element with the next element
• When elements are equal, the first is doubled and the second becomes 0
• After all operations, zeros are shifted to the end

Example: If you start with [1,0,2,0,0,1] and need to shift zeros to the end, you get [1,2,1,0,0,0].

The solution simulates this process by:

1. First traversing the array and performing the doubling operations where adjacent elements are equal
2. Creating a new array and placing all non-zero elements at the beginning
3. The remaining positions are automatically filled with zeros

The code uses bit shifting (nums[i] <<= 1) as an efficient way to double a number (equivalent to multiplying by 2).

Intuition

The problem asks us to do two distinct tasks in sequence: first modify the array based on adjacent equal elements, then rearrange the array to move zeros to the end.

Since the operations must be applied sequentially from left to right, we can't optimize or combine them - we must process each position in order. When we find nums[i] == nums[i+1], we immediately modify both values before moving to the next position. This ensures that each comparison uses the most up-to-date values.

The key insight is that these two tasks are independent:

1. First pass: Perform all the doubling operations
2. Second pass: Rearrange to move zeros to the end

For the first pass, a simple loop from index 0 to n-2 handles all comparisons. We check each adjacent pair and modify them according to the rule.

For the second pass, instead of trying to swap elements in place (which can be complex), we can build a new array. We iterate through the modified array and place all non-zero elements at the beginning of our result array. Since we initialize the result array with zeros, we don't need to explicitly add zeros at the end - they're already there.

The elegance of this approach is its simplicity: we don't need complex logic for shifting or swapping. By separating the two tasks and using a fresh array for the final arrangement, we avoid the complexity of in-place rearrangement while maintaining O(n) time complexity.

The use of nums[i] <<= 1 for doubling is a small optimization - left shifting by 1 bit is equivalent to multiplying by 2, but it's a faster operation at the hardware level.

Learn more about Two Pointers patterns.

Solution Approach

The solution follows a straightforward simulation approach with two distinct phases:

Phase 1: Apply Operations

We traverse the array from index 0 to n-2 (since we need to compare each element with its next neighbor):

for i in range(n - 1):
    if nums[i] == nums[i + 1]:
        nums[i] <<= 1      # Double the current element
        nums[i + 1] = 0    # Set the next element to 0

The bit shift operation <<= 1 efficiently doubles the value by shifting all bits one position to the left. For example, if nums[i] = 3 (binary: 11), then nums[i] <<= 1 makes it 6 (binary: 110).

Phase 2: Move Zeros to End

Instead of complex in-place swapping, we create a new result array initialized with zeros:

ans = [0] * n

Then we iterate through the modified nums array and place all non-zero elements at the beginning of ans:

i = 0
for x in nums:
    if x:              # If x is non-zero
        ans[i] = x     # Place it at the current position
        i += 1         # Move to the next position

The pointer i keeps track of where to place the next non-zero element. Since ans is pre-filled with zeros, we don't need to explicitly handle the zeros - they're already in the right positions at the end.

Time and Space Complexity:

• Time: O(n) - We make two passes through the array
• Space: O(n) - We create a new array of size n for the result

This approach elegantly separates concerns: first handle the doubling logic, then handle the rearrangement, making the code clean and easy to understand.

Example Walkthrough

Let's walk through the solution with the array nums = [1, 5, 2, 2, 2, 0, 0].

Initial State: [1, 5, 2, 2, 2, 0, 0]

Phase 1: Apply Operations (comparing adjacent pairs)

• Operation 0 (i=0): Compare nums[0]=1 and nums[1]=5

  • They're not equal, skip
  • Array: [1, 5, 2, 2, 2, 0, 0]

• Operation 1 (i=1): Compare nums[1]=5 and nums[2]=2

  • They're not equal, skip
  • Array: [1, 5, 2, 2, 2, 0, 0]

• Operation 2 (i=2): Compare nums[2]=2 and nums[3]=2

  • They're equal! Double nums[2] and set nums[3]=0
  • nums[2] = 2 << 1 = 4, nums[3] = 0
  • Array: [1, 5, 4, 0, 2, 0, 0]

• Operation 3 (i=3): Compare nums[3]=0 and nums[4]=2

  • They're not equal, skip
  • Array: [1, 5, 4, 0, 2, 0, 0]

• Operation 4 (i=4): Compare nums[4]=2 and nums[5]=0

  • They're not equal, skip
  • Array: [1, 5, 4, 0, 2, 0, 0]

• Operation 5 (i=5): Compare nums[5]=0 and nums[6]=0

  • They're equal! Double nums[5] and set nums[6]=0
  • nums[5] = 0 << 1 = 0, nums[6] = 0
  • Array: [1, 5, 4, 0, 2, 0, 0]

Phase 2: Move Zeros to End

Create new array ans = [0, 0, 0, 0, 0, 0, 0] and pointer i = 0

• Process nums[0]=1: Non-zero, place at ans[0], increment i to 1

  • ans = [1, 0, 0, 0, 0, 0, 0]

• Process nums[1]=5: Non-zero, place at ans[1], increment i to 2

  • ans = [1, 5, 0, 0, 0, 0, 0]

• Process nums[2]=4: Non-zero, place at ans[2], increment i to 3

  • ans = [1, 5, 4, 0, 0, 0, 0]

• Process nums[3]=0: Zero, skip

• Process nums[4]=2: Non-zero, place at ans[3], increment i to 4

  • ans = [1, 5, 4, 2, 0, 0, 0]

• Process nums[5]=0: Zero, skip

• Process nums[6]=0: Zero, skip

Final Result: [1, 5, 4, 2, 0, 0, 0]

The solution correctly doubled the adjacent equal elements (2 and 2 became 4 and 0) and moved all zeros to the end while maintaining the relative order of non-zero elements.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array nums.

The algorithm consists of two sequential passes through the array:

• First loop: Iterates through n-1 elements to check adjacent pairs and apply operations. Each operation (comparison, left shift, and assignment) takes O(1) time. Total: O(n-1) = O(n).
• Second loop: Iterates through all n elements to rearrange non-zero values. Each iteration involves a constant-time check and potential assignment. Total: O(n).

Overall time complexity: O(n) + O(n) = O(n).

Space Complexity: O(n) for the total space used, or O(1) if we exclude the space required for the output array.

The algorithm allocates:

• ans: A new array of size n to store the result, requiring O(n) space.
• i: A single integer variable for indexing, requiring O(1) space.
• The input array nums is modified in-place during the first loop.

If we follow the convention of excluding the output array from space complexity analysis (as the reference answer suggests), the auxiliary space complexity is O(1) since only a constant amount of extra space is used beyond the input and output.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Modifying Elements During Iteration Affects Subsequent Comparisons

The Problem: A common mistake is not realizing that when you modify nums[i+1] = 0 during operation i, this affects the next comparison at operation i+1. This can lead to unexpected behavior when consecutive equal elements appear.

Example: Consider the array [2, 2, 2, 1]:

• Operation 0: nums[0] == nums[1] (2 == 2), so nums[0] = 4, nums[1] = 0
• Operation 1: nums[1] == nums[2] (0 == 2), which is false, so no change
• Operation 2: nums[2] == nums[3] (2 == 1), which is false, so no change
• Result after operations: [4, 0, 2, 1]
• After moving zeros: [4, 2, 1, 0]

If someone mistakenly thinks all three 2's should merge, they'd expect [8, 1, 0, 0], but that's incorrect because the operations are sequential, not simultaneous.

Solution: Process the array sequentially as intended. The current implementation is correct - each operation uses the current state of the array, not the original state.

Pitfall 2: Using In-Place Zero Movement Incorrectly

The Problem: Trying to move zeros to the end in-place using swap operations can be tricky and error-prone, especially when trying to maintain the relative order of non-zero elements.

Incorrect Approach:

# Wrong: This doesn't maintain relative order
left, right = 0, n - 1
while left < right:
    if nums[left] == 0:
        nums[left], nums[right] = nums[right], nums[left]
        right -= 1
    else:
        left += 1

This would incorrectly change [1, 0, 2, 0, 3] to [1, 3, 2, 0, 0] instead of [1, 2, 3, 0, 0].

Solution: Use the two-pointer technique correctly or create a new array as shown in the solution:

# Correct in-place approach (alternative to creating new array)
write_pos = 0
for i in range(n):
    if nums[i] != 0:
        nums[write_pos] = nums[i]
        if write_pos != i:
            nums[i] = 0
        write_pos += 1

Pitfall 3: Edge Case with All Zeros or Single Element

The Problem: Not handling edge cases properly:

• Array with all zeros: [0, 0, 0]
• Single element array: [5]
• Array starting with zeros: [0, 0, 1, 1]

Solution: The current implementation handles these correctly:

• For single element arrays, the loop range(n-1) simply doesn't execute when n=1
• Arrays with zeros work because we check equality regardless of value
• The zero-moving phase handles any configuration of zeros correctly

Pitfall 4: Integer Overflow with Large Numbers

The Problem: When doubling large numbers, there's a risk of integer overflow in languages with fixed integer sizes. While Python handles arbitrary precision integers, this could be an issue in other languages.

Example: If nums[i] = 2^31 - 1 (maximum 32-bit signed integer), doubling it would cause overflow in languages like Java or C++.

Solution:

• In Python: No action needed due to arbitrary precision
• In other languages: Add overflow checking or use appropriate data types (e.g., long long in C++)

# For languages with overflow concerns, add validation:
if nums[i] > MAX_INT // 2:
    # Handle overflow case
    pass