Problem

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 (0-indexed), you will apply the following on the ith element of nums:

  • If nums[i] == nums[i + 1], then multiply nums[i] by 2 and set nums[i + 1] to 0. Otherwise, you skip this operation.

After performing all the operations, shift all the 0’s to the end of the array.

  • For example, the array [1,0,2,0,0,1] after shifting all its 0’s to the end, is [1,2,1,0,0,0].

Return the resulting array.

Note that the operations are applied sequentially, not all at once.

Examples

Example 1:

1
2
3
4
5
6
7
8
9

Input: nums = [1,2,2,1,1,0]
Output: [1,4,2,0,0,0]
Explanation: We do the following operations:
- i = 0: nums[0] and nums[1] are not equal, so we skip this operation.
- i = 1: nums[1] and nums[2] are equal, we multiply nums[1] by 2 and change nums[2] to 0. The array becomes [1,**_4_** ,**_0_** ,1,1,0].
- i = 2: nums[2] and nums[3] are not equal, so we skip this operation.
- i = 3: nums[3] and nums[4] are equal, we multiply nums[3] by 2 and change nums[4] to 0. The array becomes [1,4,0,**_2_** ,**_0_** ,0].
- i = 4: nums[4] and nums[5] are equal, we multiply nums[4] by 2 and change nums[5] to 0. The array becomes [1,4,0,2,**_0_** ,**_0_**].
After that, we shift the 0's to the end, which gives the array [1,4,2,0,0,0].

Example 2:

1
2
3

Input: nums = [0,1]
Output: [1,0]
Explanation: No operation can be applied, we just shift the 0 to the end.

Constraints:

  • 2 <= nums.length <= 2000
  • 0 <= nums[i] <= 1000

Solution

Video explanation

Here is the video explaining below methods in detail. Please check it out:

Method 1 - Run the simulation with extra array

Here is the approach:

  1. Iterate Over The Array: Start iterating over nums from index 0 to n - 2.
    • If nums[i] == nums[i + 1], multiply nums[i] by 2 and set nums[i + 1] to 0.
  2. Shifting Zeros: After the above operations, shift all the zeros in the array to the end.
    • This can be done by creating a new array where non-zero elements retain their relative order, followed by appending the zeros at the end.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public int[] applyOperations(int[] nums) {
        int n = nums.length;
        // Apply the operations
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] == nums[i + 1]) {
                nums[i] *= 2;
                nums[i + 1] = 0;
            }
        }
        
        // Shifting zeros
        int[] ans = new int[n];
        int idx = 0;
        for (int num : nums) {
            if (num != 0) {
                ans[idx++] = num;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def applyOperations(self, nums: List[int]) -> List[int]:
        n: int = len(nums)
        # Applying the operations
        for i in range(n - 1):
            if nums[i] == nums[i + 1]:
                nums[i] *= 2
                nums[i + 1] = 0
        
        # Shifting zeros
        ans: List[int] = [x for x in nums if x != 0]
        ans.extend([0] * (n - len(ans)))
        return ans

Complexity

  • ⏰ Time complexity: O(n)
    1. Iteration over the array is O(n) to apply operations.
    2. Shifting zeros involves another O(n) pass.
  • 🧺 Space complexity: O(n) 3. The operations can be performed in-place (O(1) space) for the main operations. 4. However, shifting zeros explicitly uses a secondary array which requires O(n) space.

Method 2 - Run the simulation in-place

Here is the approach:

  1. Apply Operations In-Place:
    • Iterate over the array and perform the same operation (nums[i] *= 2, nums[i + 1] = 0) directly in the array if nums[i] == nums[i + 1].
  2. Shift Non-Zero Elements In-Place:
    • Use a pointer (write) to track the position where non-zero elements should be placed.
    • Traverse the array and copy non-zero values to the write position.
    • After all non-zero values are placed, fill the remaining positions with 0.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
    public int[] applyOperations(int[] nums) {
        int n = nums.length;

        // Step 1: Apply operations in-place
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] == nums[i + 1]) {
                nums[i] *= 2;
                nums[i + 1] = 0;
            }
        }

        // Step 2: Shift non-zero elements in-place
        int write = 0; // Pointer to place the next non-zero element
        for (int i = 0; i < n; i++) {
            if (nums[i] != 0) {
                nums[write++] = nums[i];
            }
        }

        // Fill remaining indices with zeros
        while (write < n) {
            nums[write++] = 0;
        }

        return nums;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def applyOperations(self, nums: List[int]) -> List[int]:
        n: int = len(nums)
        
        # Step 1: Apply operations in-place
        for i in range(n - 1):
            if nums[i] == nums[i + 1]:
                nums[i] *= 2
                nums[i + 1] = 0
        
        # Step 2: Shift non-zero elements in-place
        write: int = 0  # Pointer to place the next non-zero element
        for i in range(n):
            if nums[i] != 0:
                nums[write] = nums[i]
                write += 1
        
        # Fill the rest with zeros
        for i in range(write, n):
            nums[i] = 0
        
        return nums

Complexity

  • ⏰ Time complexity: O(n)
    1. Applying the operations: O(n)
    2. Shifting non-zero elements: O(n)
  • 🧺 Space complexity: O(1)

Method 3 - Run the simulation in-place one pass

Here is the approach:

  1. Apply Operations In-Place:
    • Iterate over the array and perform the same operation (nums[i] *= 2, nums[i + 1] = 0) directly in the array if nums[i] == nums[i + 1].
  2. Shift Non-Zero Elements In-Place:
    • Use a pointer (write) to track the position where non-zero elements should be placed.
    • Traverse the array and copy non-zero values to the write position.
    • After all non-zero values are placed, fill the remaining positions with 0.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    public int[] applyOperations(int[] nums) {
        int n = nums.length;
        int write = 0; // Tracks the position to write non-zero elements

        for (int read = 0; read < n; read++) {
            // Apply operation if possible
            if (read < n - 1 && nums[read] == nums[read + 1]) {
                nums[read] *= 2;
                nums[read + 1] = 0;
            }

            // Shift non-zero elements to correct position in-place
            if (nums[read] != 0) {
                nums[write] = nums[read];
                if (write != read) { // Avoid redundant overwrites
                    nums[read] = 0;
                }
                write++;
            }
        }

        return nums;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def applyOperations(self, nums: List[int]) -> List[int]:
        n: int = len(nums)
        write: int = 0  # Tracks the position to write non-zero elements

        for read in range(n):
            # Apply operation if possible
            if read < n - 1 and nums[read] == nums[read + 1]:
                nums[read] *= 2
                nums[read + 1] = 0

            # Shift non-zero elements to correct position in-place
            if nums[read] != 0:
                nums[write] = nums[read]
                if write != read:  # Avoid redundant overwrites
                    nums[read] = 0
                write += 1

        return nums

Complexity

  • ⏰ Time complexity: O(n). The entire process runs in O(n) as read iterates from 0 to n - 1 once.
  • 🧺 Space complexity: O(1)