LeetCode Problem 2460

Difficulty: 🟢 Easy
Topics: Array, Two Pointers, Simulation

Solution

LeetCode 2460 - Apply Operations to an Array

Problem Understanding

This problem gives us a 0-indexed array nums containing non-negative integers. We must perform a sequence of operations on adjacent elements, then rearrange the resulting array by moving all zeros to the end.

The first phase consists of processing the array from left to right. For every index i from 0 to n - 2, we compare nums[i] and nums[i + 1].

If the two values are equal, we:

1. Double the value at nums[i]
2. Set nums[i + 1] to 0

If the values are not equal, we do nothing and move on.

A crucial detail is that the operations are applied sequentially. Changes made during one operation affect later operations. We are not comparing against the original array, but against the current state of the array after previous modifications.

After all n - 1 operations have been processed, we perform a second phase where all zeros are shifted to the end of the array while preserving the relative order of the non-zero elements.

The output is the final array after both phases.

The constraints are relatively small:

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

Since the array contains at most 2000 elements, even quadratic solutions would technically pass. However, the problem naturally admits a linear-time solution, which is the preferred approach.

Several edge cases are important:

• Adjacent equal values can create zeros that participate in later comparisons.
• Multiple consecutive equal values require careful sequential processing.
• Arrays containing many zeros must still follow the operation rules because 0 == 0.
• Arrays that are already free of zeros after merging still need the zero-shifting phase.
• Arrays with no equal adjacent elements should simply move existing zeros to the end.

Approaches

Brute Force Approach

A straightforward solution is to first simulate all merge operations exactly as described. After that, repeatedly move zeros toward the end by scanning the array and swapping zeros with later non-zero elements.

This approach is correct because it directly follows the problem statement. However, the zero-shifting step can become inefficient. In the worst case, each zero may need to be moved across many positions, leading to quadratic time complexity.

Although the constraints are small enough that this would still work, it is not the most efficient solution.

Optimal Approach

The key observation is that the problem naturally separates into two phases.

First, we simulate all merge operations exactly as required. This takes a single pass through the array.

Second, instead of repeatedly swapping zeros, we use a two-pointer compaction technique. We write all non-zero values into the front of the array while preserving their order. After all non-zero values have been placed, we fill the remaining positions with zeros.

This allows the entire solution to run in linear time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Simulate operations, then repeatedly move zeros through swaps
Optimal	O(n)	O(1)	Simulate operations, then compact non-zero values using two pointers

Algorithm Walkthrough

Optimal Algorithm

1. Iterate through indices 0 to n - 2.
2. For each index i, check whether nums[i] == nums[i + 1].
3. If the values are equal, double nums[i] and set nums[i + 1] to 0.
4. Continue processing the array from left to right until all merge operations have been completed.
5. Create a write pointer initialized to 0. This pointer represents the next position where a non-zero value should be placed.
6. Scan the array from left to right again.
7. Whenever a non-zero value is found, copy it to position write and increment write.
8. After all non-zero values have been written, every position from write to the end of the array should contain 0.
9. Fill those remaining positions with zeros.
10. Return the modified array.

Why it works

The first pass exactly reproduces the sequential operations required by the problem statement. Because we process indices in increasing order and immediately update the array, every later comparison sees the correct current state.

After the first phase, the only remaining task is moving all zeros to the end while preserving the order of non-zero elements. The two-pointer compaction process maintains the invariant that positions before write contain all previously encountered non-zero values in their original order. Therefore, once the scan finishes, the front portion of the array contains the correct sequence of non-zero elements, and filling the remainder with zeros produces exactly the required result.

Python Solution

from typing import List

class Solution:
    def applyOperations(self, nums: List[int]) -> List[int]:
        n = len(nums)

        # Apply merge operations
        for i in range(n - 1):
            if nums[i] == nums[i + 1]:
                nums[i] *= 2
                nums[i + 1] = 0

        # Move non-zero elements forward
        write = 0
        for num in nums:
            if num != 0:
                nums[write] = num
                write += 1

        # Fill remaining positions with zeros
        while write < n:
            nums[write] = 0
            write += 1

        return nums

The implementation follows the algorithm directly.

The first loop performs the required sequential merge operations. Whenever two adjacent values are equal, the left value is doubled and the right value becomes zero.

The second loop performs the compaction step. The variable write tracks the next available position for a non-zero value. As we scan the array, every non-zero value is copied to the earliest available location.

Finally, any positions after the last non-zero element are filled with zeros. The resulting array satisfies the requirement that all zeros appear at the end while preserving the relative order of non-zero elements.

Go Solution

func applyOperations(nums []int) []int {
	n := len(nums)

	// Apply merge operations
	for i := 0; i < n-1; i++ {
		if nums[i] == nums[i+1] {
			nums[i] *= 2
			nums[i+1] = 0
		}
	}

	// Move non-zero values forward
	write := 0
	for _, num := range nums {
		if num != 0 {
			nums[write] = num
			write++
		}
	}

	// Fill remaining positions with zeros
	for write < n {
		nums[write] = 0
		write++
	}

	return nums
}

The Go implementation mirrors the Python solution closely. Since slices are mutable, all modifications occur in place. Integer overflow is not a concern under the given constraints because values remain comfortably within Go's integer range. No special handling for nil slices is necessary because the problem guarantees an array length of at least two.

Worked Examples

Example 1

Input

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

Phase 1: Apply Operations

i	Comparison	Action	Array State
0	1 vs 2	No change	[1,2,2,1,1,0]
1	2 vs 2	Merge	[1,4,0,1,1,0]
2	0 vs 1	No change	[1,4,0,1,1,0]
3	1 vs 1	Merge	[1,4,0,2,0,0]
4	0 vs 0	Merge	[1,4,0,2,0,0]

After phase 1:

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

Phase 2: Move Non-Zero Values

Read Value	Write Position	Array Front
1	0	[1]
4	1	[1,4]
0	Skip	[1,4]
2	2	[1,4,2]
0	Skip	[1,4,2]
0	Skip	[1,4,2]

Fill remaining positions with zeros:

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

Output

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

Example 2

Input

nums = [0,1]

Phase 1: Apply Operations

i	Comparison	Action	Array State
0	0 vs 1	No change	[0,1]

After phase 1:

[0,1]

Phase 2: Move Non-Zero Values

Read Value	Write Position	Array Front
0	Skip	[]
1	0	[1]

Fill remaining positions with zeros:

[1,0]

Output

[1,0]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	One pass for merging and one pass for zero compaction
Space	O(1)	All modifications are performed in place

The algorithm performs two linear scans of the array. Since constant factors are ignored in asymptotic analysis, the overall running time remains O(n). No auxiliary data structures proportional to the input size are used, so the extra space consumption is constant.

Test Cases

from typing import List

s = Solution()

assert s.applyOperations([1, 2, 2, 1, 1, 0]) == [1, 4, 2, 0, 0, 0]  # example 1
assert s.applyOperations([0, 1]) == [1, 0]  # example 2

assert s.applyOperations([1, 2]) == [1, 2]  # no merges
assert s.applyOperations([2, 2]) == [4, 0]  # single merge
assert s.applyOperations([0, 0]) == [0, 0]  # merging zeros

assert s.applyOperations([2, 2, 2]) == [4, 2, 0]  # sequential effect
assert s.applyOperations([1, 1, 1, 1]) == [2, 2, 0, 0]  # multiple merges

assert s.applyOperations([0, 0, 1]) == [1, 0, 0]  # leading zeros
assert s.applyOperations([1, 0, 0, 2]) == [1, 2, 0, 0]  # scattered zeros

assert s.applyOperations([4, 4, 8, 8]) == [8, 16, 0, 0]  # multiple independent merges
assert s.applyOperations([0, 0, 0, 0]) == [0, 0, 0, 0]  # all zeros

assert s.applyOperations([1000, 1000]) == [2000, 0]  # maximum value merge
assert s.applyOperations([3, 3, 0, 0]) == [6, 0, 0, 0]  # merges involving zeros

Test Summary

Test	Why
[1,2,2,1,1,0]	Official example with multiple merges
[0,1]	Official example with zero shifting only
[1,2]	No adjacent equal values
[2,2]	Simplest merge case
[0,0]	Zero values can also merge
[2,2,2]	Tests sequential processing behavior
[1,1,1,1]	Multiple consecutive merges
[0,0,1]	Leading zeros
[1,0,0,2]	Internal zeros requiring compaction
[4,4,8,8]	Multiple independent merge regions
[0,0,0,0]	Entire array is zeros
[1000,1000]	Largest input value merge
[3,3,0,0]	Regular merge followed by zero merge

Edge Cases

Consecutive Equal Values

An input such as [2,2,2] can be tricky because operations are sequential. After processing index 0, the array becomes [4,0,2]. The comparison at index 1 is then between 0 and 2, not between the original values. A solution that attempts to process all equal pairs simultaneously would produce the wrong result. The implementation correctly updates the array in place as it moves from left to right.

Arrays Containing Many Zeros

An input like [0,0,0,0] demonstrates that zeros participate in comparisons just like any other value. Since 0 == 0, merge operations occur, although doubling zero still produces zero. The implementation follows the problem statement exactly and therefore handles these cases correctly.

Existing Zeros Mixed with Non-Zero Values

An input such as [1,0,0,2] contains zeros that are already present before any operations occur. After the merge phase, the array may contain additional zeros. The two-pointer compaction step preserves the order of non-zero elements while moving every zero to the end, ensuring the final arrangement is correct.

No Merge Opportunities

An input like [1,2,3,4] contains no adjacent equal values. The first phase leaves the array unchanged. The second phase simply rewrites the same non-zero values back into their original positions. The result remains unchanged, which matches the expected behavior.

Single Merge at the Beginning or End

Inputs such as [5,5,1,2] or [1,2,5,5] verify that merges near array boundaries are handled correctly. The loop processes every valid adjacent pair exactly once, ensuring that edge positions receive the same treatment as middle positions.