You are given a circular array balance of length n, where balance[i] is the net balance of person i.
In one move, a person can transfer exactly 1 unit of balance to either their left or right neighbor.
Return the minimum number of moves required so that every person has a non-negative balance. If it is impossible, return -1.
Note: You are guaranteed that at most 1 index has a negative balance initially.
Example 1:
Input: balance = [5,1,-4]
Output: 4
Explanation:
One optimal sequence of moves is:
i = 1 to i = 2, resulting in balance = [5, 0, -3]i = 0 to i = 2, resulting in balance = [4, 0, -2]i = 0 to i = 2, resulting in balance = [3, 0, -1]i = 0 to i = 2, resulting in balance = [2, 0, 0]Thus, the minimum number of moves required is 4.
Example 2:
Input: balance = [1,2,-5,2]
Output: 6
Explanation:
One optimal sequence of moves is:
i = 1 to i = 2, resulting in balance = [1, 1, -4, 2]i = 1 to i = 2, resulting in balance = [1, 0, -3, 2]i = 3 to i = 2, resulting in balance = [1, 0, -2, 1]i = 3 to i = 2, resulting in balance = [1, 0, -1, 0]i = 0 to i = 1, resulting in balance = [0, 1, -1, 0]i = 1 to i = 2, resulting in balance = [0, 0, 0, 0]Thus, the minimum number of moves required is 6.
Example 3:
Input: balance = [-3,2]
Output: -1
Explanation:
It is impossible to make all balances non-negative for balance = [-3, 2], so the answer is -1.
Constraints:
1 <= n == balance.length <= 105-109 <= balance[i] <= 109balance initially.Problem Overview: You are given a circular array where a move transfers one unit between neighboring positions. The goal is to make every element equal (the array average) using the minimum number of moves while respecting the circular structure.
Approach 1: Brute Force Simulation (O(n^2) time, O(1) space)
Compute the target value target = sum(nums) / n. Because the array is circular, choose each index as a possible starting point and simulate balancing from that position. Iterate through the array, track surplus or deficit at each step, and push extra units to the next index. Count the absolute number of transfers performed. Repeat the simulation for all n rotations and keep the minimum result. This approach directly models the balancing process but repeats work for each rotation, leading to quadratic time.
Approach 2: Greedy Prefix Flow Simulation (O(n) time, O(1) space)
First compute the target value and convert the array into a difference array where diff[i] = nums[i] - target. While scanning the array, maintain a running prefix flow representing how many units must move across the current boundary. Each step adds diff[i] to the flow, and the number of moves increases by abs(flow). Intuitively, positive flow means surplus units move forward, while negative flow means units must be received from the next positions. Because the array is circular, choose the rotation where the prefix flow starts from the smallest cumulative value so the transfer chain is minimized. This greedy observation removes the need to simulate every rotation and processes the array once.
The key insight is that balancing is equivalent to redistributing surplus across boundaries. Counting how much cumulative surplus crosses each boundary directly yields the minimum number of transfers. This technique appears frequently in array redistribution problems and relies on a greedy prefix-flow idea. Some implementations also preprocess prefix values with sorting or scanning to find the optimal starting point.
Recommended for interviews: The greedy prefix-flow simulation is what interviewers typically expect. The brute-force rotation simulation demonstrates understanding of the circular constraint, but the O(n) greedy approach shows you recognize the surplus-flow invariant and can convert a simulation into a linear-time solution.
We first calculate the sum of the array balance. If the sum is less than 0, it is impossible to make all balances non-negative, so we directly return -1. Then we find the minimum balance in the array and its index. If the minimum balance is greater than or equal to 0, all balances are already non-negative, so we directly return 0.
Next, we calculate the amount of balance needed need, which is the opposite of the minimum balance. Then starting from the index of the minimum balance, we traverse the array to the left and right, taking as much balance as possible from each position to fill need, and calculate the number of moves. We continue until need becomes 0, and return the total number of moves.
The time complexity is O(n), where n is the length of the array balance. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Rotation Simulation | O(n^2) | O(1) | When verifying logic or handling very small arrays where trying every circular start is acceptable |
| Greedy Prefix Flow Simulation | O(n) | O(1) | General case and interview solution; computes minimal transfers using cumulative surplus |
Minimum Moves to Balance Circular Array | Clean Intuition | Contest Problem 3 | Leetcode 3776 | MIK • codestorywithMIK • 4,022 views views
Watch 9 more video solutions →Practice Minimum Moves to Balance Circular Array with our built-in code editor and test cases.
Practice on FleetCode