Python 2460.py
class Solution:
def applyOperations(self, nums: List[int]) -> List[int]:
for i in range(len(nums) - 1):
if nums[i] == nums[i + 1]:
nums[i] *= 2
nums[i + 1] = 0
return sorted(nums, key = lambda x : 1 if x == 0 else 0) # Python has stable sort
Difficulty
and has an acceptance rate of about 75% (300k+ submissions).
Typical patterns to solve this problem:
- Array
- Simulation
- Two Pointers
AI Disclaimer
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The provided Solution class implements a method applyOperations that processes a list of integers in two distinct phases. First, it scans the list from left to right, merging adjacent equal values by doubling the left element and zero-ing the right one. Second, it reorders the resulting list so that all zeroes are moved to the end while preserving the relative order of the non-zero elements. The implementation relies on Python’s built-in list operations and the stability of the default sorting algorithm.
Core Logic
The method begins by iterating over the indices of the input list, stopping one element before the end to avoid an out-of-range access. For each index i, it checks whether the current element and the next element are identical. When a match is found, the current element is multiplied by two, and the following element is replaced with zero. This in-place transformation directly modifies the original list without allocating auxiliary storage.
for i in range(len(nums) - 1):
if nums[i] == nums[i + 1]:
nums[i] *= 2
nums[i + 1] = 0
After the merging pass, the list may contain a mixture of non-zero values and zeros scattered throughout. To collect all zeros at the tail, the method invokes sorted with a custom key function. The key returns 1 for zero elements and 0 for any non-zero element, causing the sorting algorithm to place all zeros after the non-zero values. Because Python’s sort is stable, the original order among the non-zero elements is retained.
return sorted(nums, key = lambda x : 1 if x == 0 else 0) # Python has stable sort
The final returned list therefore reflects the merged values in their original left-to-right order, followed by all zeros.
Edge Cases
The algorithm gracefully handles several boundary conditions:
When the input list contains a single element, the range expression evaluates to an empty sequence, so the merging loop is skipped entirely. The subsequent sorting step still moves a zero (if present) to the end, which for a single-element list simply returns the list unchanged.
If the list consists entirely of zeros, the merging loop never modifies any element because the equality condition is satisfied but the multiplication by two leaves zero unchanged, and the assignment of zero to the next element is redundant. The sorting step then receives a list of zeros; the key function treats each element as 1, preserving the original order, which is already all zeros.
When multiple consecutive equal numbers appear, the algorithm only merges the first pair it encounters. For example, a segment [2, 2, 2] becomes [4, 0, 2] after the first iteration, and the remaining 2 is left untouched because the loop proceeds to the next index, which now points to the zero that was just created. This behavior matches the intended “pairwise” merging rule.
If the list ends with a pair of equal numbers, the loop processes the final valid index (len(nums) - 2). The rightmost element can be doubled and the last element set to zero without risking an index error, because the loop’s range explicitly excludes the last index as a left operand.
Performance Considerations
The implementation leverages in-place updates during the merging phase, avoiding the allocation of a secondary list for intermediate results. This reduces memory pressure, especially for large inputs, because the original list is reused throughout the computation.
The final reordering uses Python’s built-in sorted function with a simple key that distinguishes zeros from non-zeros. By relying on the highly optimized Timsort algorithm, the code benefits from existing performance tuning, such as adaptive merging of already sorted runs. The stability guarantee of Timsort ensures that the relative ordering of non-zero elements is preserved without additional bookkeeping.
Overall, the method combines a linear scan with a single call to an efficient sorting routine, achieving the desired transformation with minimal overhead and without explicit auxiliary data structures.
ELI5 - Simplified Explanation
Imagine you have a long line of numbered toy blocks sitting in a row. The code starts by walking down the line from the front to see if any two blocks sitting right next to each other have the same number. If it finds two neighbors that match, it makes the first block twice as big as it was before and turns the second block into a zero. Think of the zero as an empty space where a toy used to be. After checking every pair of blocks, there will be empty gaps scattered throughout the line. The very last part of the process acts like a little robot that slides all the blocks with numbers over to one side and pushes all the empty zero spaces to the very back of the line so everything is neat and tidy again.
Code Quality
Complexity Analysis
As a rule of thumb, the maximum input size for one second execution time is
- factorial: up to 10 elements
- exponential: up to 20 elements
- polynomial: a few thousand elements
- loglinear: up to 100,000 elements
- linear: a few million elements
- logarithmic: a billion elements
- constant: practically unlimited
Other Solutions
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| author | solutions | |||||||||
| www | AlgoMonster | Java | C++ | Python | TS | |||||
| WalkCCC | Java | C++ | Python | |||||||
| leetcode.ca | Java | C++ | Go | Python | Rust | TS | ||||
| Progiez | Java | C++ | Python | |||||||
| github | charles-wangkai | Java | ||||||||
| everthis | JS | |||||||||
| fartem | Ruby | |||||||||
| fsq | C++ | |||||||||
| JoshCrozier | JS | |||||||||
| Shamik07 | Dart | |||||||||
| varunu28 | Java | |||||||||
| AlgoMonster | C++, Python, Java, TypeScript | |||||||||
| WalkCCC | C++, Python, Java | |||||||||
| leetcode.ca | C++, Go, Java, Python, Rust, TypeScript | |||||||||
| Progiez | C++, Java, Python | |||||||||
| charles-wangkai | Java | |||||||||
| everthis | JavaScript | |||||||||
| fartem | Ruby | |||||||||
| fsq | C++ | |||||||||
| JoshCrozier | JavaScript | |||||||||
| Shamik07 | Dart | |||||||||
| varunu28 | Java |
Videos
Similar Problems
- problem 26: Remove Duplicates from Sorted Array
- problem 283: Move Zeroes
Solved On The Same Day
- problem 2410: Maximum Matching of Players With Trainers
- problem 2420: Find All Good Indices
- problem 2486: Append Characters to String to Make Subsequence
Extra
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality