Abstract / Summary

Given an array, find the least moves to make all elements equal by repeatedly increasing or decreasing any element by one.

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 42% (40k+ submissions).

Typical patterns to solve this problem:

• Array
• Dynamic Programming
• Matrix

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 minimumOperations method receives a two-dimensional integer matrix grid. The goal is to transform the matrix so that each column contains a single repeated value (condition 1) and any two adjacent columns contain different values (condition 2). The method returns the smallest number of cell modifications required to achieve both constraints.

Key Steps

Determine grid dimensions

The algorithm first extracts the number of rows (height) and columns (width) from the input matrix.

height = len(grid)
width  = len(grid[0])

Compute per-column change cost

For a given column index x, the inner function deeper builds an array need of length 10. Each entry need[d] represents how many cells in column x must be altered to make the entire column equal to digit d. The initial value for each digit is the column height, and the count for the existing digit at each row is decremented.

need = [height] * 10
for y in range(height):
    need[grid[y][x]] -= 1

Recursive evaluation with memoization

deeper is decorated with @cache, turning it into a memoized function. This ensures that the cost array for each column index is computed at most once, avoiding exponential recomputation when the recursion explores many digit combinations.

@cache
def deeper(x):
    ...
    if x == width - 1:
        return need
    next = deeper(x + 1)
    ...

Combine costs across columns respecting adjacency

When processing a column that is not the last one, the algorithm merges the current column’s need array with the cost array of the column to its right (next). For each possible digit one in the current column, it examines every digit two for the next column, discarding pairs where one == two to enforce the adjacency rule. The minimal combined cost for each one is stored in best.

best = [+inf] * 10
for one in range(10):
    for two in range(10):
        if one != two:               # enforce condition 2
            best[one] = min(best[one], need[one] + next[two])
return best

Finally, the outer call selects the smallest entry from the cost array for the first column, yielding the minimal total number of operations.

return min(deeper(0))

Edge Cases Handled

When the grid consists of a single column, the recursion reaches the base case x == width - 1 immediately, and the function returns the need array directly. This correctly computes the cost of making that sole column uniform without needing to consider adjacency.

If the grid has only one row, each column already contains a single value, so need[d] becomes zero for the digit present in that cell and height - 1 (which equals zero) for all other digits. The algorithm therefore returns zero modifications if the existing digits already satisfy the adjacency constraint, or the minimal number of changes required to adjust any conflicting adjacent columns.

When all columns are already uniform and already satisfy the adjacency rule, the need array for each column contains a zero at the existing digit and positive values elsewhere. The nested loops will select the zero entries, and the final min call yields zero, indicating no operations are needed.

If a column contains a mixture of digits, the need computation correctly counts how many cells must be altered to achieve uniformity for each possible target digit, ensuring that the algorithm accounts for any distribution of values within the column.

Performance Optimizations

The use of @cache on the recursive deeper function eliminates redundant calculations of the cost arrays for column indices that are revisited during the double-loop combination step. Because each column index is processed only once, the overall work scales linearly with the number of columns, despite the inner double loop over the ten possible digits.

The need array is allocated with a fixed size of ten elements, matching the limited digit range. This constant-size structure enables fast index-based updates and lookups without dynamic resizing or hash-based structures.

By initializing best with positive infinity and updating it only when a strictly better combination is found, the algorithm avoids unnecessary assignments and ensures that the minimal cost for each digit is retained throughout the nested loops.

The early return for the last column (if x == width - 1: return need) prevents further recursive calls and combination logic when there is no right neighbor, reducing the call depth and associated overhead.

Overall, the design leverages memoization, fixed-size arrays, and early termination to keep the execution efficient while exploring all valid digit assignments across columns.

Imagine a giant grid filled with lots of colorful building blocks stacked in columns. Each column has blocks of different colors, like red, blue, or yellow. The goal is to make every single block in one column the exact same color, but there is a special rule. If a column is colored red, the column right next to it cannot be red. It has to be a different color.

The code starts by looking at each column one by one to see how many blocks need to be changed so they all match. For example, if a column has five blocks and three are already blue, only two blocks need to become blue to finish that column.

After figuring out the cost for all possible colors, the code moves to the next column. It uses a clever trick to remember which colors were used before so it never picks a color that clashes with the neighbor. It keeps checking every column until it reaches the very end of the line. By comparing all the different paths, it finds the smallest number of blocks that need to be swapped to make the whole grid satisfy the color rule. This is like solving a puzzle where every piece must fit perfectly without touching another piece of its own kind.

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