Abstract / Summary

Given a list of positive integers, find the maximum possible frequency that all values can have after changing some elements.

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 38% (50k+ submissions).

Typical patterns to solve this problem:

• Array
• Hash Table

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 implementation solves the problem of finding the longest prefix of an integer array where, after possibly removing a single element, the remaining numbers can all have the same frequency. The algorithm processes the array in a single left-to-right pass, maintaining two complementary data structures: one that records how many times each distinct value has appeared, and another that groups values by their current frequency. By examining the shape of these structures after each insertion, the code decides whether the current prefix satisfies one of the known valid configurations and updates the answer accordingly.

Key Steps

The algorithm begins by initializing the result accumulator and two dictionaries that will be updated incrementally.

result = 0
freq = defaultdict(int)      # maps value -> occurrence count
same = defaultdict(set)      # maps count -> set of values with that count

During the iteration over the input list, the old count for the current number is retrieved, the new count is computed, and both dictionaries are updated to reflect the change.

for i, n in enumerate(nums):
    old = freq[n]
    new = old + 1

    # update the per-value frequency
    freq[n] = new

    # remove the value from the set of its previous count
    if old > 0:
        same[old].discard(n)
        if not same[old]:
            del same[old]

    # add the value to the set of its new count
    same[new].add(n)

The length of the current prefix is derived from the loop index.

length = i + 1

Four distinct conditional blocks examine the current state of freq and same. Each block corresponds to a known pattern that guarantees the prefix can be made uniform by removing at most one element.

if len(freq) == 1:
    result = length

if len(same) <= 2 and 1 in same and len(same[1]) == 1:
    result = length

if len(same) == 2 and len(same[max(same)]) == 1 and max(same) == 1 + min(same):
    result = length

if max(same) == 1:
    result = length

Finally, the algorithm returns the largest prefix length recorded.

return result

Edge Cases Handled

When the input consists of a single distinct value repeated many times, the first condition (len(freq) == 1) captures the situation and updates the result for every prefix.

If the array contains exactly one element that appears only once while all other elements share a common higher frequency, the second condition (len(same) <= 2 and 1 in same and len(same[1]) == 1) detects the “single outlier” pattern.

When two frequencies coexist and the higher frequency exceeds the lower one by exactly one, with only one value holding the higher count, the third condition (len(same) == 2 …) validates the “frequency differs by one” scenario.

The fourth condition (max(same) == 1) covers the case where every number in the prefix appears at most once, meaning the prefix is already uniform after any removal.

Additionally, the code removes empty frequency groups from same (if not same[old]: del same[old]), ensuring that the size checks on same reflect only active frequencies.

Performance Optimizations

The solution relies on defaultdict to avoid explicit existence checks when updating counts and groups, which keeps each update to constant time.

Using a set for each frequency group enables O(1) insertion and removal of values, and the discard method safely handles the case where a value might already be absent without raising an exception.

The explicit deletion of empty sets from same prevents the dictionary from growing with stale keys, keeping the number of entries minimal and making subsequent len(same) and max(same) operations cheap.

By computing the prefix length once per iteration (length = i + 1) and reusing it across all condition checks, the code avoids repeated arithmetic.

The conditional checks are ordered such that the most common and inexpensive patterns are evaluated first, reducing the number of expensive max and min calls when earlier conditions already satisfy the prefix.

Imagine a big toy box filled with colorful blocks. Every time a new block is picked up, it gets sorted into a pile based on how many times that specific color has been seen. The code keeps track of how many of each color are in the box and groups them together by their counts.

If there is only one type of block in the box, that is a perfect match. If there is one extra block that is all by itself while the rest have the same number of friends, that works too. It also checks if all the blocks appear exactly once, because that is a very simple and tidy set. Another way to win is if there are only two types of counts and the higher count is just one block more than the lower count, as removing that single extra block makes everything equal again. As the box fills up, the code watches to see if one of these patterns appears, and it remembers the longest stretch of blocks that fits the rules.

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

not analyzed yet

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