Abstract / Summary

Remove groups of three or more same-colored balls in a row to earn points and maximize the total score.

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 29% (100k+ submissions).

Typical patterns to solve this problem:

• Breadth First Search
• Dynamic Programming
• Memoization
• Stack
• String

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 classic “Zuma Game” problem: given a board of colored balls and a hand of extra balls, determine the minimum number of insertions required to clear the board, or report impossibility. The algorithm is built around a depth-first search (DFS) that explores all feasible insertion sequences while pruning unpromising branches. A recursive helper remove collapses any contiguous segment of three or more identical balls, potentially triggering chain reactions. Memoization via @cache avoids recomputation of identical board-hand configurations, and an early-exit condition based on the best solution found so far limits the search depth.

Key Steps

The entry point initializes a global result with positive infinity, representing the best solution discovered during the search.

result = +inf

Cluster Removal

A nested function remove repeatedly scans the string for runs of three or more identical characters. When such a run is found, it is excised and the function recurses on the shortened string, allowing cascades of eliminations to be resolved in a single call.

def remove(s):
    size = len(s)
    for i in range(size):
        j = i + 1
        while j < size and s[i] == s[j]:
            j += 1
        same = j - i
        if same >= 3:
            return remove(s[:i] + s[j:])
    return s

Depth-First Exploration

The core DFS resides in the deeper function, which receives the current board, the remaining hand, and the depth (number of insertions performed). The function first checks whether the current depth already exceeds the best known result, aborting the branch if so.

if depth >= result:
    return

The board is then normalized by invoking remove. If the board becomes empty, the current depth is recorded as a new optimum.

b = remove(b)
if not b:
    result = depth
    return

Insertion Generation

For each distinct ball type present in the hand, the algorithm constructs a new hand string with that ball removed.

nexthand = h.replace(insert, "", 1)

Three families of insertion positions are considered:

1. Appending the ball to the end of the board.
2. A special case that inserts the ball just before the last character, addressing a known pattern ("RRWWRRBBRR", "WB").
3. Inserting the ball at every index where the board character matches the ball’s color, ensuring immediate potential for elimination.

deeper(b + insert, nexthand, depth + 1)
deeper(b[:-1] + insert + b[-1], nexthand, depth + 1)
for i in range(len(b)):
    if b[i] == insert:
        deeper(b[:i] + insert + b[i:], nexthand, depth + 1)
    else:
        if len(set(h)) < 3:
            deeper(b[:i] + insert + b[i:], nexthand, depth + 1)

The conditional block that permits insertion at mismatched colors when the hand contains fewer than three distinct colors is a heuristic that expands the search space only in constrained hand configurations, preventing unnecessary branching in richer hands.

Memoization

The @cache decorator automatically stores results of deeper calls keyed by the board string, hand string, and depth. This eliminates redundant exploration of identical states reached via different insertion orders.

@cache
def deeper(b, h, depth = 0):
    ...

Final Result

After the recursive search completes, the function returns the best depth found, or -1 if no solution exists.

return result if result != +inf else -1

Edge Cases Handled

The algorithm explicitly addresses several subtle scenarios:

• Boards that contain pre-existing clusters of three or more identical balls are immediately reduced by the remove function before any insertion, ensuring that the search starts from a normalized state.
• The “dirty hack” insertion before the last character (deeper(b[:-1] + insert + b[-1], ...)) resolves cases where the optimal move involves inserting a ball just before the final segment, a pattern that would otherwise be missed by the generic insertion loops.
• When the hand comprises fewer than three distinct colors, the code permits insertion at positions that do not match the current board character. This expands the search to cover situations where eliminating a cluster may require creating a new run of three by bridging two separate segments of the same color.
• The early termination condition if depth >= result prevents unnecessary deeper recursion once a solution of equal or better length has already been discovered, effectively handling cases where the search could otherwise explode combinatorially.

Performance Optimizations

Several techniques contribute to the efficiency of the solution:

• Recursive Collapse: By collapsing all possible eliminations in a single remove call, the algorithm reduces the number of intermediate states that need to be explored, avoiding repeated checks for chain reactions.
• Depth Pruning: The comparison of the current depth against the global result acts as a bound, cutting off branches that cannot improve the best solution.
• Memoization: The @cache decorator provides a built-in memoization layer, ensuring that each unique combination of board, hand, and depth is processed at most once. This dramatically cuts down the exponential blow-up typical of naïve DFS approaches.
• Selective Insertion Heuristics: The conditional insertion at mismatched colors only when the hand has limited diversity reduces the branching factor in dense hand configurations, focusing computational effort on promising moves.
• String Manipulation: The use of Python’s immutable string slicing for board reconstruction avoids the overhead of mutable structures while keeping the code concise. Since each recursive call works with freshly constructed strings, there is no need for explicit backtracking state management.

Collectively, these optimizations enable the algorithm to solve moderately sized instances of the Zuma Game within practical time limits, despite the inherent combinatorial nature of the problem.

Imagine a long line of colored balls sitting on a track. The goal is to clear the whole track by adding new balls from a special supply pouch. When three balls of the same color touch each other in a row, they magically pop and disappear, which might cause other balls to slide together and pop too.

The part called remove looks at the line of balls like a detective. It checks if any group of three or more balls of the same color is sitting right next to each other. If it finds one, it makes them go away and then checks again to see if any new groups formed because the balls moved closer together.

The deeper part is like a game where different moves are tested. It tries taking a ball from the hand and placing it in every possible spot along the track. Because there are many ways to play, it has to be patient and try different orders to find the shortest way to clear everything. If a path takes too many turns, it stops looking down that path and finishes the search another way.

Every time a ball is placed, the code keeps track of how many moves were used. It works through every possibility until the track is empty or there are no more moves left to try. It basically just looks for the most clever way to wipe the board clean using the least amount of help from the supply pouch.

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++		Java					Python	TS
	WalkCCC	C++		Java					Python
	leetcode.ca			Java					Python
	LeetcodeHelp	C++		Java					Python
	Progiez	C++		Java					Python
github	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	gouthampradhan			Java
	halfrost						Go
	JoshCrozier		JS
	linouk23	C++
	lzl124631x	C++
	martianoff				Scala
	ruoru					Rust
	suxrobGM							C#
	wisdompeak	C++
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	Java, Python
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
gouthampradhan	Java
halfrost	Go
JoshCrozier	JavaScript
linouk23	C++
lzl124631x	C++
martianoff	Scala
ruoru	Rust
suxrobGM	C#
wisdompeak	C++
zfang399	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