Abstract / Summary

Given a list of machine weights and limits on how much weight can be moved between machines per operation find the least number of moves to balance all machines.

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 45% (90k+ submissions).

Typical patterns to solve this problem:

• Array
• Greedy

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 findMinMoves that determines the minimum number of moves required to balance a sequence of washing machines so that each holds the same number of dresses. The algorithm first checks whether an equal distribution is mathematically possible, computes the target number of dresses per machine, and then iterates through the list while maintaining cumulative imbalance and the maximum load observed. The final result is the greatest of these values, representing the minimal number of moves needed.

Key Steps

The method begins with a feasibility test that uses the total number of dresses and the count of machines:

if sum(machines) % len(machines) > 0:
    return -1

If the total cannot be divided evenly, the function returns -1 to indicate impossibility.

Next, the target number of dresses per machine is calculated as an integer division of the total by the number of machines:

final  = sum(machines) // len(machines)

Two accumulator variables, total and result, are initialized to zero. total tracks the cumulative surplus or deficit up to the current machine, while result records the maximum moves required observed so far.

The core loop processes each machine:

for m in machines:
    diff    = m - final
    total  += diff
    result  = max(result, abs(total), diff)

• diff represents the local deviation of the current machine from the target.
• total aggregates these deviations, reflecting the net number of dresses that must be passed across the boundary between the current machine and the next.
• result is updated with the maximum of three quantities:
  • the current result,
  • the absolute cumulative imbalance abs(total),
  • the local deviation diff.

After the loop, result holds the answer and is returned:

return result

Edge Cases Handled

The initial feasibility check gracefully handles the situation where the total number of dresses cannot be evenly divided among the machines, returning -1 without further computation. This prevents unnecessary processing for impossible configurations.

When the list contains a single machine, the sum modulo length check yields zero, final equals the machine’s count, and the loop runs once. The diff becomes zero, total remains zero, and result stays zero, correctly indicating that no moves are needed.

If all machines already contain the same number of dresses, each diff is zero, total never deviates from zero, and result remains zero throughout, resulting in an immediate answer of zero moves.

The algorithm also correctly processes cases where some machines have a large surplus while others have a large deficit. The cumulative total captures the net flow required across each boundary, and the use of abs(total) ensures that the direction of imbalance does not affect the magnitude of moves counted.

Performance Optimizations

The solution achieves optimal performance by performing a single pass over the input list after the initial feasibility test. The use of integer arithmetic for the target calculation and cumulative updates avoids any overhead from floating-point operations.

By maintaining only three scalar variables (final, total, result) the algorithm operates with constant auxiliary space, regardless of the size of the input list. The max function combines three comparisons in a single statement, reducing the number of conditional branches inside the loop.

The early return on infeasibility eliminates the need for any further processing when the problem has no solution, saving time for inputs that would otherwise require a full traversal. This early exit, combined with the linear scan, ensures that the method scales efficiently with the number of machines.

Imagine you have a row of toy boxes, and each box has a different number of toy cars inside. Some boxes have a lot, and some are nearly empty. The goal is to make every single box have the exact same number of cars.

The code first checks if it is even possible to share the cars perfectly. If the total number of cars cannot be divided evenly among the boxes, the task is impossible, so it stops right there.

If the cars can be shared equally, the code figures out the target number for each box. Then, it walks down the line of boxes one by one. As it looks at each box, it keeps track of how many extra cars are passing through or how many are still needed.

The code uses a special tracker to see how many cars are moving across the gaps between boxes. By checking the difference between what a box has and what it needs, it figures out the busiest moment where cars are being shifted around. It keeps note of the largest number of moves that happen at any single spot to make sure the boxes end up 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			Go	Python	TS
	LeetcodeHelp	C++		Java				Python
	Progiez	C++		Java				Python
github	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	gouthampradhan			Java
	JoshCrozier		JS
	linouk23	C++
	lzl124631x	C++
	ruoru				Rust
	suxrobGM					C#
	wisdompeak	C++
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
gouthampradhan	Java
JoshCrozier	JavaScript
linouk23	C++
lzl124631x	C++
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