3776. Minimum Moves to Balance Circular Array

MediumGreedyArraySorting

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given a circular array balance of length n, where balance[i] represents the net balance of person i. Because the array is circular, person 0 and person n - 1 are considered neighbors.

In one move, a person can transfer exactly 1 unit of balance to either their left or right neighbor.

Your task is to return the minimum number of moves required so that every person ends up with a non-negative balance. If achieving this is impossible, return -1.

It becomes impossible only when there is not enough total balance to cover the shortfall — that is, when the sum of all balances is less than 0.

Note: You are guaranteed that at most 1 index has a negative balance initially. This means there is at most one person who owes balance, and the moves are used to pull balance from other people toward that single negative position.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Greedy Algorithms?

This problem maps to Greedy Algorithms through a short path in the full flowchart.

Taking balance from the closest neighbors first to satisfy a single deficit position is a greedy minimization strategy on a circular array.

Open in Flowchart

Intuition

The key observation comes from the Note: at most one index has a negative balance. This greatly simplifies the problem. Instead of dealing with many deficits scattered around the circle, we only have a single person who is short, and everyone else either has zero or extra balance to give away.

The first thing to check is feasibility. Every move only moves balance around — it never creates or destroys balance. So the total sum stays constant. If the total sum is less than 0, then no matter how we shuffle the units, the overall balance can never be made non-negative, and we return -1. If the minimum balance is already 0 or more, everyone is fine and the answer is 0.

Now think about the single negative position. Let its shortfall be need = -min(balance). We must pull exactly need units of balance into this position from the rest of the circle. The cost of moving one unit of balance from a position that is d steps away from the negative index is exactly d moves, because each transfer covers one step toward the target.

To minimize the total moves, we want to grab the needed units from the closest positions first, since closer positions cost fewer moves per unit. This is the greedy idea: take as much as possible from distance 1 neighbors, then distance 2, and so on, until the need is fully satisfied.

Because the array is circular, both directions matter. At each distance j, we look at the person j steps to the left and the person j steps to the right of the negative index. From each of them, we take min(available, need) units, add j moves per unit taken to the answer, and reduce need accordingly. Expanding outward symmetrically guarantees we always consume the cheapest available balance first, which yields the minimum total number of moves.

Pattern Learn more about Greedy and Sorting patterns.

Solution Approach

We follow a simulation combined with a greedy strategy.

Step 1: Check feasibility.

We first compute sum(balance). Since moves never change the total amount of balance, if this sum is less than 0, it is impossible to make everyone non-negative, so we return -1.

Step 2: Handle the trivial case.

We find the minimum balance mn = min(balance). If mn >= 0, everyone already has a non-negative balance, so no moves are needed and we return 0.

Step 3: Set up the deficit.

The single negative position is at i = balance.index(mn), and the amount it needs is need = -mn. Let n = len(balance) and initialize the answer ans = 0.

Step 4: Expand outward greedily.

We loop with j from 1 to n - 1, where j is the distance from the negative index. At each distance, we look at the two positions that are j steps away on each side:

The position j steps to the left: a = balance[(i - j + n) % n]
The position j steps to the right: b = balance[(i + j - n) % n]

The modulo arithmetic handles the circular wrap-around, so indices always stay within [0, n - 1].

For each of these positions, we take as much balance as we still need:

From the left side, take c1 = min(a, need), then update need -= c1 and add the cost ans += c1 * j (each unit moved across distance j costs j moves).
From the right side, do the same with c2 = min(b, need), updating need -= c2 and ans += c2 * j.

Because we process distances from nearest to farthest, the cheapest units are always consumed first, guaranteeing the minimum total number of moves.

Step 5: Return the result.

Once the loop finishes, need has been fully satisfied (the feasibility check guarantees enough balance exists), and ans holds the minimum number of moves, which we return.

The time complexity is O(n), since we scan the array a constant number of times, and the space complexity is O(1), as only a few extra variables are used.

Example Walkthrough

Let's trace through a small example to see the greedy expansion in action.

Input: balance = [2, -5, 1, 3, 0], so n = 5.

Step 1: Check feasibility.

Compute the total sum:

sum = 2 + (-5) + 1 + 3 + 0 = 1

Since sum = 1 is not less than 0, the problem is feasible. We continue.

Step 2: Handle the trivial case.

Find the minimum balance:

mn = min([2, -5, 1, 3, 0]) = -5

Since mn = -5 < 0, at least one person is in deficit, so we cannot return 0. We proceed.

Step 3: Set up the deficit.

The negative position is at index i = 1 (where -5 lives). The amount needed is:

need = -mn = 5
ans  = 0

We must pull 5 units toward index 1, taking from the cheapest (closest) positions first.

Step 4: Expand outward greedily.

We loop j from 1 to n - 1 = 4.

Iteration j = 1 (distance 1 from index 1):

Left position: (i - j + n) % n = (1 - 1 + 5) % 5 = 0 → balance[0] = 2
- c1 = min(2, 5) = 2, so need = 5 - 2 = 3, ans = 0 + 2 * 1 = 2
Right position: (i + j) % n = (1 + 1) % 5 = 2 → balance[2] = 1
- c2 = min(1, 3) = 1, so need = 3 - 1 = 2, ans = 2 + 1 * 1 = 3

After j = 1: need = 2, ans = 3.

Iteration j = 2 (distance 2 from index 1):

Left position: (1 - 2 + 5) % 5 = 4 → balance[4] = 0
- c1 = min(0, 2) = 0, so need stays 2, ans stays 3
Right position: (1 + 2) % 5 = 3 → balance[3] = 3
- c2 = min(3, 2) = 2, so need = 2 - 2 = 0, ans = 3 + 2 * 2 = 7

After j = 2: need = 0, the deficit is fully covered.

Step 5: Return the result.

The loop may continue, but since need = 0, every subsequent min(..., 0) = 0 contributes nothing. The final answer is:

ans = 7

Why this is minimal: We grabbed the 2 units from the immediate left neighbor (distance 1, cost 2), 1 unit from the immediate right neighbor (distance 1, cost 1), and the remaining 2 units from index 3 (distance 2, cost 4). Total = 2 + 1 + 4 = 7. By always consuming the nearest available balance first, no cheaper alternative was skipped, guaranteeing the minimum number of moves.

Solution Implementation

1from typing import List
2
3
4class Solution:
5    def minMoves(self, balance: List[int]) -> int:
6        # If the total balance is negative, it's impossible to cover all deficits.
7        if sum(balance) < 0:
8            return -1
9
10        # If there is no negative balance, no moves are required.
11        minimum_balance = min(balance)
12        if minimum_balance >= 0:
13            return 0
14
15        # The amount that needs to be filled at the most negative position.
16        remaining_need = -minimum_balance
17
18        # Index of the most negative position; this is where deficits are filled.
19        deficit_index = balance.index(minimum_balance)
20        length = len(balance)
21
22        total_moves = 0
23
24        # Expand outward from the deficit position by increasing distance `distance`.
25        for distance in range(1, length):
26            # Neighbor on the "left" side of the circular array at the current distance.
27            left_value = balance[(deficit_index - distance + length) % length]
28            # Neighbor on the "right" side of the circular array at the current distance.
29            right_value = balance[(deficit_index + distance - length) % length]
30
31            # Take as much as possible from the left neighbor to satisfy the need.
32            take_from_left = min(left_value, remaining_need)
33            remaining_need -= take_from_left
34            total_moves += take_from_left * distance
35
36            # Take as much as possible from the right neighbor to satisfy the need.
37            take_from_right = min(right_value, remaining_need)
38            remaining_need -= take_from_right
39            total_moves += take_from_right * distance
40
41        return total_moves
42

1class Solution {
2    public long minMoves(int[] balance) {
3        // Step 1: Compute the total sum of all balances.
4        // If the total is negative, the deficits can never be fully covered,
5        // so it is impossible to make every position non-negative.
6        long totalSum = 0;
7        for (int value : balance) {
8            totalSum += value;
9        }
10        if (totalSum < 0) {
11            return -1;
12        }
13
14        int length = balance.length;
15
16        // Step 2: Find the position with the minimum (most negative) balance.
17        // This is the position that needs to be "filled" by moving value from
18        // surrounding positions, and it dominates the cost computation.
19        int minValue = balance[0];
20        int minIndex = 0;
21        for (int i = 1; i < length; i++) {
22            if (balance[i] < minValue) {
23                minValue = balance[i];
24                minIndex = i;
25            }
26        }
27
28        // Step 3: If the smallest balance is already non-negative,
29        // every position is non-negative and no moves are required.
30        if (minValue >= 0) {
31            return 0;
32        }
33
34        // The amount that must be transferred into the deficit position.
35        int needed = -minValue;
36        long answer = 0;
37
38        // Step 4: Spread outward from the deficit position symmetrically.
39        // For each distance j, look at the position j steps to the left and
40        // j steps to the right (using circular indexing). Pull as much value
41        // as possible from each, accumulating cost = amount * distance.
42        for (int distance = 1; distance < length; distance++) {
43            int leftValue = balance[(minIndex - distance + length) % length];
44            int rightValue = balance[(minIndex + distance) % length];
45
46            // Take as much as needed from the left neighbor.
47            int takeFromLeft = Math.min(leftValue, needed);
48            needed -= takeFromLeft;
49            answer += (long) takeFromLeft * distance;
50
51            // Take as much as needed from the right neighbor.
52            int takeFromRight = Math.min(rightValue, needed);
53            needed -= takeFromRight;
54            answer += (long) takeFromRight * distance;
55        }
56
57        return answer;
58    }
59}
60

1class Solution {
2public:
3    long long minMoves(vector<int>& balance) {
4        // Step 1: Compute the total sum of all balances.
5        // If the total sum is negative, it is impossible to make every
6        // position non-negative, so we return -1.
7        long long totalSum = 0;
8        for (int value : balance) {
9            totalSum += value;
10        }
11        if (totalSum < 0) {
12            return -1;
13        }
14
15        int size = balance.size();
16
17        // Step 2: Find the position with the minimum balance.
18        // This is the "deficit" position that needs to be filled first.
19        int minValue = balance[0];
20        int minIndex = 0;
21        for (int i = 1; i < size; i++) {
22            if (balance[i] < minValue) {
23                minValue = balance[i];
24                minIndex = i;
25            }
26        }
27
28        // Step 3: If the smallest balance is already non-negative,
29        // no moves are needed.
30        if (minValue >= 0) {
31            return 0;
32        }
33
34        // Step 4: Determine how much we still need to cover the deficit.
35        // We greedily pull "balance" from the nearest neighbors outward,
36        // alternating between the left and right sides of minIndex.
37        int need = -minValue;
38        long long answer = 0;
39
40        for (int distance = 1; distance < size; distance++) {
41            // The neighbor on the left at the current distance.
42            int leftNeighbor = balance[(minIndex - distance + size) % size];
43            // The neighbor on the right at the current distance.
44            int rightNeighbor = balance[(minIndex + distance) % size];
45
46            // Take as much as possible from the left neighbor,
47            // each unit costs "distance" moves to transfer.
48            int takeLeft = min(leftNeighbor, need);
49            need -= takeLeft;
50            answer += 1LL * takeLeft * distance;
51
52            // Take as much as possible from the right neighbor,
53            // each unit costs "distance" moves to transfer.
54            int takeRight = min(rightNeighbor, need);
55            need -= takeRight;
56            answer += 1LL * takeRight * distance;
57        }
58
59        return answer;
60    }
61};
62

1/**
2 * Computes the minimum number of moves required to balance the array.
3 *
4 * Each element in `balance` represents the surplus (positive) or deficit
5 * (negative) at a position arranged in a circle. A single move transfers one
6 * unit between two adjacent positions. The cost of moving a unit from one
7 * position to another equals the circular distance between them.
8 *
9 * The strategy:
10 *  1. If the total sum is negative, balancing is impossible -> return -1.
11 *  2. Find the position with the most severe deficit (the minimum value).
12 *  3. Fill that deficit by pulling surplus from the nearest positions
13 *     (expanding outward symmetrically), accumulating cost = amount * distance.
14 *
15 * @param balance - circular array of surpluses/deficits at each position.
16 * @returns the minimum total cost, or -1 if balancing is impossible.
17 */
18function minMoves(balance: number[]): number {
19    // Total surplus across all positions. If negative, demand exceeds supply.
20    const sum: number = balance.reduce((acc, value) => acc + value, 0);
21    if (sum < 0) {
22        return -1;
23    }
24
25    const n: number = balance.length;
26
27    // Locate the position holding the minimum value (largest deficit).
28    let minValue: number = balance[0];
29    let minIndex: number = 0;
30    for (let i = 1; i < n; i++) {
31        if (balance[i] < minValue) {
32            minValue = balance[i];
33            minIndex = i;
34        }
35    }
36
37    // No deficit anywhere means nothing needs to be moved.
38    if (minValue >= 0) {
39        return 0;
40    }
41
42    // Amount still required to cover the deficit at `minIndex`.
43    let need: number = -minValue;
44
45    // Accumulated cost of all transfers.
46    let answer: number = 0;
47
48    // Expand outward from `minIndex` in both directions, distance `j`.
49    for (let distance = 1; distance < n; distance++) {
50        // Surplus on the left side at the current distance (circular index).
51        const leftValue: number = balance[(minIndex - distance + n) % n];
52        // Surplus on the right side at the current distance (circular index).
53        const rightValue: number = balance[(minIndex + distance) % n];
54
55        // Take as much as available (and needed) from the left neighbor.
56        const takeFromLeft: number = Math.min(leftValue, need);
57        need -= takeFromLeft;
58        answer += takeFromLeft * distance;
59
60        // Take as much as available (and needed) from the right neighbor.
61        const takeFromRight: number = Math.min(rightValue, need);
62        need -= takeFromRight;
63        answer += takeFromRight * distance;
64    }
65
66    return answer;
67}
68

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array balance.

The analysis breaks down as follows:

Computing sum(balance) requires traversing the entire array once, costing O(n).
Finding min(balance) via min() is another O(n) traversal.
Locating the minimum index with balance.index(mn) takes O(n) in the worst case.
The main for loop iterates j from 1 to n - 1, performing a constant amount of work (array indexing, min of two scalars, arithmetic) in each iteration, contributing O(n).

Since these operations are sequential rather than nested, the total time complexity is O(n) + O(n) + O(n) + O(n) = O(n).

Space Complexity: O(1).

Only a fixed number of scalar variables (mn, need, i, n, ans, a, b, c1, c2, j) are used, and no auxiliary data structures grow with the input size. Therefore, the extra space consumed is constant, O(1).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrect Circular Indexing on the Right Side

The most subtle and dangerous pitfall lies in how the right-side neighbor is computed:

right_value = balance[(deficit_index + distance - length) % length]

The expression (deficit_index + distance - length) % length happens to produce a correct index only because Python's modulo operator always returns a non-negative result for a positive divisor. Subtracting length here is unnecessary and confusing — the natural and intended form is:

right_value = balance[(deficit_index + distance) % length]

Both expressions are mathematically equivalent in Python (since (x - length) % length == x % length), but the - length version is a trap for two reasons:

Readability/correctness confusion: It mirrors the left side's + length, leading a reader to assume symmetry. But on the left we add length to avoid a negative index; on the right we should simply add distance. Mixing the two invites copy-paste bugs.
Language portability: If this logic is ported to a language where % can return a negative value (C, C++, Java, Go), (deficit_index + distance - length) % length can yield a negative index and crash or read garbage, while (deficit_index + distance) % length stays safe.

Solution: Use the clean, symmetric, and portable forms:

left_value  = balance[(deficit_index - distance) % length]   # Python handles negatives
right_value = balance[(deficit_index + distance) % length]

If targeting a language without guaranteed non-negative modulo, normalize explicitly:

left_index  = ((deficit_index - distance) % length + length) % length
right_index = (deficit_index + distance) % length

Pitfall 2: Double-Counting a Position When `n` Is Even

When the array length n is even, the loop runs distance from 1 to n - 1. At distance = n // 2, the "left" and "right" expansions land on the same index:

(deficit_index - n/2) % n  ==  (deficit_index + n/2) % n

The current code takes balance from left_value and right_value separately, but both refer to the same person. Since remaining_need is decremented between the two min(...) calls, the code happens to avoid over-withdrawing more than that person holds in total — but it can still double-process the same physical balance value, and in a naive variant (e.g., if someone refactored to take both mins against the original need) this silently steals balance that doesn't exist.

Solution: Guard the mid-point so each index is consulted once:

for distance in range(1, length):
    left_index  = (deficit_index - distance) % length
    right_index = (deficit_index + distance) % length

    take = min(balance[left_index], remaining_need)
    remaining_need -= take
    total_moves += take * distance

    if right_index != left_index:          # avoid double-counting the meeting point
        take = min(balance[right_index], remaining_need)
        remaining_need -= take
        total_moves += take * distance

    if remaining_need == 0:
        break

The right_index != left_index check protects the even-length meeting point, and the early break avoids needless iterations once the deficit is satisfied.

Pitfall 3: Relying on `min`/`index` Instead of the Stated Guarantee

The code uses min(balance) and balance.index(...) to find the single negative position. This works, but it implicitly assumes the "at most one negative index" guarantee from the problem. If that guarantee were relaxed (multiple negatives), balance.index(min) would find only one of them, and the greedy single-source expansion would produce a wrong answer rather than failing loudly.

Solution: Either validate the assumption defensively, or detect multiple negatives and fall back to a general algorithm:

negatives = [k for k, v in enumerate(balance) if v < 0]
if len(negatives) > 1:
    # The single-source greedy no longer applies; a general
    # circular-balancing (gas-station-style prefix) approach is needed.
    raise ValueError("Solution assumes at most one negative position")

This makes the hidden precondition explicit and prevents silent incorrect results if the input ever violates it.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering