Abstract / Summary

Given an array of integers, repeatedly change all numbers to the most frequent value and add the count of changed numbers until all are equal, then return the sum of all changes.

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 65% (200k+ submissions).

Typical patterns to solve this problem:

• Array
• Hash Table
• Heap (Priority Queue)
• Simulation
• Sorting

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 findScore that computes a cumulative score from a list of integers. The algorithm processes the numbers in ascending order, selectively adding values to the result while marking adjacent positions as “skipped.” By iterating over the sorted elements and using a boolean mask, the method ensures that each chosen element contributes to the final sum only if it has not been invalidated by a previously selected neighbor. The overall flow consists of initialization, sorting with index tracking, conditional skipping, score accumulation, and neighbor marking.

Initialization

At the start of the method, two variables are prepared. result holds the running total, and skip is a list of booleans, one per element in nums, indicating whether a position is prohibited from contributing to the score.

result = 0
skip = [ False ] * len(nums)

The boolean list is pre-filled with False, meaning no index is initially excluded.

Sorting with Index Preservation

The core of the algorithm requires processing the numbers from smallest to largest while retaining their original positions. This is achieved by enumerating the input list, converting the enumeration to a list of (index, value) pairs, and sorting that list based on the value component.

for where, what in sorted(list(enumerate(nums)), key = lambda x : x[1]):

The where variable captures the original index, and what holds the numeric value. Sorting by x[1] guarantees that the loop visits elements in non-decreasing order of their magnitude.

Conditional Skipping

Before a value contributes to the score, the algorithm checks whether its index has already been marked as skipped. If skip[where] is True, the current iteration is bypassed, and the loop proceeds to the next element.

if skip[where]:
    continue

This guard ensures that once an element is invalidated-either because it was a neighbor of a previously selected element or because it was itself marked earlier-it does not affect the final total.

Score Accumulation

When an element passes the skip check, its value is added to result. This step represents the inclusion of the current number in the cumulative score.

result += what

Because the loop processes numbers from smallest to largest, the algorithm prefers lower values when multiple candidates are available, which influences which neighbors become skipped.

Neighbor Marking

After a value has been added, the algorithm marks its immediate left and right neighbors as skipped, provided those neighbors exist within the bounds of the list. This is performed with two separate conditional blocks that update the skip list.

if where > 0:
    skip[where - 1] = True
if where < len(skip) - 1:
    skip[where + 1] = True

By setting the adjacent positions to True, the method guarantees that no two selected elements will be adjacent in the original ordering. The boundary checks (where > 0 and where < len(skip) - 1) prevent out-of-range indexing for the first and last elements.

Edge Cases Handled

The implementation gracefully manages several edge conditions without additional code paths. When the input list is empty, the initial skip list is also empty, the sorting step yields an empty iterator, and the method returns the initial result of zero. For a single-element list, the sorting loop runs once, the element is added to result, and the neighbor marking conditions evaluate to false because there are no valid neighbors, leaving skip unchanged. When the list contains duplicate values, the stable sorting of (index, value) pairs ensures that each occurrence is considered in order of its original index, preserving deterministic behavior. The boundary checks in the neighbor marking stage prevent attempts to access indices outside the valid range, thereby handling the first and last positions safely.

Performance Optimizations Observed

The algorithm leverages a few implicit efficiencies. By constructing the skip list once and updating it in place, the method avoids repeated allocation of auxiliary structures during iteration. The use of sorted(list(enumerate(nums)), key = lambda x : x[1]) creates a single sorted view of the data, allowing the main loop to run in a straightforward linear pass without additional lookups or nested loops. The early continue on already-skipped indices eliminates unnecessary work for elements that cannot contribute, reducing the number of additions and neighbor updates. Moreover, the conditional neighbor marking only executes when the current index has valid neighbors, avoiding superfluous assignments for edge positions.

Overall, the code follows a clear procedural pattern: initialize state, order data, iterate with conditional logic, update state, and return the accumulated result. The design ensures that each element is examined at most once after sorting, and the boolean mask efficiently tracks exclusion without resorting to more complex data structures.

Imagine a long row of numbered toy blocks sitting on the floor. Each block has a different number written on it. The goal is to pick the smallest numbers first to get a big score.

First, look at all the blocks and figure out which one has the smallest number. Pick that block up and add its number to the secret score. Once a block is picked, the blocks sitting right next to it on the left and the right become grumpy and cannot be picked anymore.

Keep looking for the next smallest number that is still available to be picked. If a block is already grumpy because its neighbor was picked earlier, just skip over it. Whenever a new block is picked, remember to make its two neighbors grumpy too. Repeat this process until every single block has either been picked for the score or made grumpy.

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

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

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	TS
	Progiez	Java		C++		Python
github	charles-wangkai	Java
	fsq			C++
	Shamik07		Dart
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
fsq	C++
Shamik07	Dart

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