Abstract / Summary

Remove elements so no three identical values are adjacent in the array.

Note

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

This problem is ranked as

and has an acceptance rate of about 50% (80k+ submissions).

Typical patterns to solve this problem:

• Array
• Greedy
• Stack

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.

Overview

The provided Solution class implements a method minDeletion that computes the minimum number of deletions required to transform an input list of integers into an array that satisfies a specific alternating-index property. The algorithm processes the list in a single forward pass, maintaining a parity flag that indicates whether the current position in the prospective resulting array would be an even index. By incrementing a counter whenever a deletion is necessary and adjusting the parity flag accordingly, the method derives the exact count of elements that must be removed. The final return statement also accounts for the case where the constructed array would end with an odd length, ensuring the result always corresponds to a valid even-length array.

Core Logic

The method begins by initializing a counter named result to zero. This counter accumulates the number of deletions performed during the scan.

result = 0

The size of the input list is stored in the variable size, and a Boolean flag even is set to True to represent that the first element of the target array is expected at an even index.

size = len(nums)
even = True

A for loop iterates from the first element up to the penultimate element (size - 1). The loop body contains the decision logic that determines whether the current element should be kept or deleted.

for i in range(size - 1):
    if even:
        if nums[i] == nums[i + 1]:
            result += 1     # still even
        else:
            even = False    # will be odd
    else:
        even = True

When the even flag is True, the algorithm expects the element at position i to occupy an even index in the resulting array. If the current element is equal to its immediate successor, the algorithm records a deletion by incrementing result. The parity of the expected position remains even because the deletion removes the left element, causing the next element to shift into the same even slot. If the two adjacent elements differ, the algorithm toggles the even flag to False, indicating that the next element will occupy an odd index.

When the even flag is False, the algorithm simply flips the flag back to True. This step reflects the fact that an element placed at an odd index does not impose any equality constraint with its neighbor; the algorithm only needs to advance the parity for the subsequent iteration.

After the loop completes, the method evaluates whether the constructed array would have an odd length. If the even flag is still True, it means the last processed position was expected to be even, implying that the resulting array would contain an odd number of elements. In that situation, one additional deletion is required, which is added to the result before returning.

return result + (1 if even else 0)

The comment clarifies that the loop stops at size - 1, so the final state of the even flag is effectively the negation of the parity of the last element in the original list.

Edge Cases Handled

The algorithm gracefully handles an empty input list. In that scenario, size becomes zero, the for loop does not execute, and the even flag remains True. The final return expression evaluates to 1, which correctly indicates that a single deletion would be needed to achieve an even-length array (the empty array is already even, but the logic treats the absence of elements as requiring one removal to satisfy the parity condition). Because the problem definition typically expects zero deletions for an empty list, the implementation’s handling aligns with the intended parity enforcement.

When the input list contains a single element, the loop again does not run because size - 1 equals zero. The even flag stays True, and the method returns 1. This outcome reflects the requirement that a valid array must have an even number of elements; therefore, the solitary element must be removed.

If the list consists entirely of identical consecutive values, the inner equality check triggers a deletion for every pair of adjacent equal elements while the even flag remains unchanged. This behavior ensures that the resulting array contains no two equal neighbors at even-odd positions, satisfying the alternating-index rule.

When the list already satisfies the alternating-index condition-meaning no two adjacent elements are equal at positions where the left element would be placed at an even index-the algorithm never increments result inside the loop. The parity flag toggles appropriately, and the final return adds an extra deletion only if the length of the original list is odd, thereby preserving the minimal deletion count.

Performance Optimizations

The method achieves its efficiency by performing a single linear traversal of the input list. By avoiding nested loops or auxiliary data structures, the algorithm minimizes overhead and memory usage. The use of a Boolean flag to track expected parity eliminates the need for explicit index calculations or modulo operations, which reduces computational cost per iteration.

Incrementing the deletion counter directly within the conditional block avoids additional function calls or temporary variables. The final adjustment for odd length is performed with a concise conditional expression, eliminating the need for a separate conditional branch after the loop.

Overall, the design leverages straightforward control flow and minimal state to deliver a solution that scales linearly with the size of the input while maintaining a constant auxiliary memory footprint.

Imagine a long line of numbered building blocks standing in a row on the floor. The goal is to make sure that no two blocks next to each other have the same number, but there is a special rule about which spots the blocks occupy.

The code starts by looking at the first block and checking it against the one right next to it. If the two blocks have the exact same number, the first one is taken away. This makes all the blocks behind the gap shift forward one spot to fill the empty space. Because everything moves, the spots change, and the code keeps track of whether it is looking at an even or an odd spot.

If the blocks are different, they get to stay put, and the code moves on to check the next pair. It repeats this over and over as it walks down the line of blocks from the beginning to the end. After checking every pair, there might be an extra block left over at the very end that would make the total number of blocks odd. If that happens, one more block is removed to make sure the final group of blocks is perfectly balanced.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
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

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	C++		Java	Python				TS
	WalkCCC	C++		Java	Python
	leetcode.ca	C++		Java	Python		Go	Rust	TS
	Progiez	C++		Java	Python
github	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	fsq	C++
	JoshCrozier		JS
	lkwq007				Python
	suxrobGM					C#
	varunu28			Java
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
varunu28	Java
wisdompeak	C++

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