Problem 2460

Abstract / Summary

Repeatedly remove the largest and smallest elements from the array until one or none remain.

Note

The full problem description, including helpful examples, can be found on LeetCode.

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
7 lines | 316 bytes | submitted February 18, 2024 | GitHub   14% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 75% (300k+ submissions).

Typical patterns to solve this problem:
  • Array
  • Simulation
  • Two Pointers
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
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.
LeetCode profile | GitHub repo

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.

written by openai gpt

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.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 7 | μ = 6.48 | σ = 1.40

Complexity Analysis

Time: loglinear
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
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
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
23 links | 11 authors | 9 languages

Videos

5 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

2 similar problems

Solved On The Same Day

5 solutions   February 18, 2024

Extra

There are a few extra pages giving you some insights into my setup:
  • 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