2460. Apply Operations to an Array - Detailed Explanation

Problem Statement

You are given a 0-indexed array of non-negative integers. You must perform the following two-step process on the array:

1. Apply Operations:
   Iterate through the array from index 0 to n - 2. For every index i, if the element at index i is equal to the element at index i + 1, then:

   • Double the element at index i (i.e. set it to 2 * nums[i]).
   • Set the element at index i + 1 to 0.

2. Shift Non-Zero Elements:
   After all operations have been applied, shift all non-zero elements to the beginning of the array while maintaining their original order, and move all zeros to the end of the array.

Example 1

Input:

nums = [1, 2, 2, 1, 1, 0]

Output:

[1, 4, 2, 0, 0, 0]

Explanation:

• Operation Phase:

  • At i = 0: 1 and 2 are not equal, so no change.
  • At i = 1: 2 equals 2, so update: nums[1] becomes 4, and nums[2] becomes 0.
    Array becomes: [1, 4, 0, 1, 1, 0]
  • At i = 2: 0 and 1 are not equal, so no change.
  • At i = 3: 1 equals 1, so update: nums[3] becomes 2, and nums[4] becomes 0.
    Array becomes: [1, 4, 0, 2, 0, 0]
  • At i = 4: 0 and 0 are equal. Even though doubling 0 gives 0, we update: nums[4] becomes 0 and nums[5] becomes 0.
    Array remains: [1, 4, 0, 2, 0, 0]

• Shift Phase:

  • Extract non-zero elements in order: [1, 4, 2]
  • Fill the remaining positions with zeros to obtain: [1, 4, 2, 0, 0, 0]

Example 2

Input:

nums = [0, 1]

Output:

[1, 0]

Explanation:

• Operation Phase:
  • At i = 0: 0 and 1 are not equal, so no change.
• Shift Phase:
  • Non-zero elements: [1]
  • Append zeros: [1, 0]

Example 3

Input:

nums = [1, 1, 1, 1]

Output:

[2, 2, 0, 0]

Explanation:

• Operation Phase:
  • At i = 0: 1 equals 1, update: nums[0] becomes 2, nums[1] becomes 0.
    Array becomes: [2, 0, 1, 1]
  • At i = 1: 0 and 1 are not equal, so no change.
  • At i = 2: 1 equals 1, update: nums[2] becomes 2, nums[3] becomes 0.
    Array becomes: [2, 0, 2, 0]
• Shift Phase:
  • Non-zero elements: [2, 2]
  • Append zeros: [2, 2, 0, 0]

Constraints

• 1 ≤ nums.length ≤ 2000
• 0 ≤ nums[i] ≤ 10⁵

Hints

1. Direct Simulation:
   The problem can be solved by simulating the two-step process. First, iterate over the array and apply the doubling operation when adjacent elements are equal.

2. Shifting Technique:
   Once the operations are complete, use a two-pointer technique or list comprehension to collect non-zero elements in order and fill the remainder with zeros.

Approach 1: Direct Simulation and Post-Processing

Explanation

• Operation Phase:
  Iterate from index 0 to n - 2. For each index i, check if nums[i] equals nums[i+1]. If true, update nums[i] to 2 * nums[i] and set nums[i+1] to 0.

• Shift Phase:
  After processing all pairs, construct a new array by first collecting all non-zero elements (maintaining their order) and then appending the appropriate number of zeros at the end.

Complexity

• Time Complexity:
  • O(n) for the first pass (applying operations)
  • O(n) for shifting non-zero elements
    Total: O(n)
• Space Complexity:
  • O(n) if creating a new array for the final result; however, the operation phase is done in-place.

Visual Example

For nums = [1, 2, 2, 1, 1, 0]:

1. Operation Phase:
   • i = 1: [1, 4, 0, 1, 1, 0]
   • i = 3: [1, 4, 0, 2, 0, 0]
2. Shift Phase:
   • Non-zero elements: [1, 4, 2]
   • Fill with zeros: [1, 4, 2, 0, 0, 0]

Approach 2: In-Place Two-Pointer Technique for Shifting

Explanation

• Perform the operation phase exactly as in Approach 1.

• Use two pointers: one pointer traverses the array, while the other pointer tracks the index to place the next non-zero element.

• After the traversal, fill the remainder of the array with zeros.

Complexity

• Time Complexity: O(n) for a single pass to apply the operation and another pass for the two-pointer shifting.

• Space Complexity: O(1) extra space if shifting is done in-place.

Python Code

Java Code