Minimum Moves to Balance Circular Array solution and explanation
9 more videos on this problem
Minimum Moves to Balance Circular Array | Clean Intuition | Contest Problem 3 | Leetcode 3776 | MIKcodestorywithMIK · 33:01 · 4K views
Minimum Moves to Balance Circular Array 🔥 | LeetCode 3776 | Weekly Contest 480 Q3 | Greedy Solution Study Placement · 22:41 · 852 views
Minimum Moves to Balance Circular Array | LeetCode 3776 | Weekly Contest 480Sanyam IIT Guwahati · 21:07 · 462 views
LeetCode 3776 | Minimum Moves to Balance Circular Array | Step-by-Step ExplanationRaman Bhari · 30:01 · 262 views
3776. Minimum Moves to Balance Circular Array (Leetcode Medium)Programming Live with Larry · 23:28 · 144 views
Leetcode 3776 | Minimum Moves to Balance Circular ArrayCodeWithMeGuys · 8:02 · 131 views
Leetcode|3776 Minimum Moves to Balance Circular Array | Circular Array|Weekly Contest- 80Cakot Coding · 19:14 · 117 views
Leetcode 3776. Minimum Moves to Balance Circular Array | Greedy | Two-pointers | MediumLeet's Code · 31:25 · 82 views
Minimum Moves to Balance Circular Array | 3776 | Weekly Contest 480 | Java Code | Developer CoderDeveloper Coder · 26:06 · 73 views
3776. Minimum Moves to Balance Circular Array | Leetcode contest 488 | C++ | SolutionCodeWithKundan · 15:38 · 38 views
The problem
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:
- Move 1 unit from
i = 1toi = 2, resulting inbalance = [5, 0, -3] - Move 1 unit from
i = 0toi = 2, resulting inbalance = [4, 0, -2] - Move 1 unit from
i = 0toi = 2, resulting inbalance = [3, 0, -1] - Move 1 unit from
i = 0toi = 2, resulting inbalance = [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:
- Move 1 unit from
i = 1toi = 2, resulting inbalance = [1, 1, -4, 2] - Move 1 unit from
i = 1toi = 2, resulting inbalance = [1, 0, -3, 2] - Move 1 unit from
i = 3toi = 2, resulting inbalance = [1, 0, -2, 1] - Move 1 unit from
i = 3toi = 2, resulting inbalance = [1, 0, -1, 0] - Move 1 unit from
i = 0toi = 1, resulting inbalance = [0, 1, -1, 0] - Move 1 unit from
i = 1toi = 2, resulting inbalance = [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] <= 109- There is at most one negative value in
balanceinitially.
Approach overview
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.
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).
class Solution:
def minMoves(self, balance: List[int]) -> int:
if sum(balance) < 0:
return -1
mn = min(balance)
if mn >= 0:
return 0
need = -mn
i = balance.index(mn)
n = len(balance)
ans = 0
for j in range(1, n):
a = balance[(i - j + n) % n]
b = balance[(i + j - n) % n]
c1 = min(a, need)
need -= c1
ans += c1 * j
c2 = min(b, need)
need -= c2
ans += c2 * j
return ansclass Solution {
public long minMoves(int[] balance) {
long sum = 0;
for (int b : balance) {
sum += b;
}
if (sum < 0) {
return -1;
}
int n = balance.length;
int mn = balance[0];
int idx = 0;
for (int i = 1; i < n; i++) {
if (balance[i] < mn) {
mn = balance[i];
idx = i;
}
}
if (mn >= 0) {
return 0;
}
int need = -mn;
long ans = 0;
for (int j = 1; j < n; j++) {
int a = balance[(idx - j + n) % n];
int b = balance[(idx + j) % n];
int c1 = Math.min(a, need);
need -= c1;
ans += (long) c1 * j;
int c2 = Math.min(b, need);
need -= c2;
ans += (long) c2 * j;
}
return ans;
}
}class Solution {
public:
long long minMoves(vector<int>& balance) {
long long sum = 0;
for (int b : balance) {
sum += b;
}
if (sum < 0) {
return -1;
}
int n = balance.size();
int mn = balance[0];
int idx = 0;
for (int i = 1; i < n; i++) {
if (balance[i] < mn) {
mn = balance[i];
idx = i;
}
}
if (mn >= 0) {
return 0;
}
int need = -mn;
long long ans = 0;
for (int j = 1; j < n; j++) {
int a = balance[(idx - j + n) % n];
int b = balance[(idx + j) % n];
int c1 = min(a, need);
need -= c1;
ans += 1LL * c1 * j;
int c2 = min(b, need);
need -= c2;
ans += 1LL * c2 * j;
}
return ans;
}
};function minMoves(balance: number[]): number {
const sum = balance.reduce((a, b) => a + b, 0);
if (sum < 0) {
return -1;
}
const n = balance.length;
let mn = balance[0],
idx = 0;
for (let i = 1; i < n; i++) {
if (balance[i] < mn) {
mn = balance[i];
idx = i;
}
}
if (mn >= 0) {
return 0;
}
let need = -mn;
let ans = 0;
for (let j = 1; j < n; j++) {
const a = balance[(idx - j + n) % n];
const b = balance[(idx + j) % n];
const c1 = Math.min(a, need);
need -= c1;
ans += c1 * j;
const c2 = Math.min(b, need);
need -= c2;
ans += c2 * j;
}
return ans;
}func minMoves(balance []int) int64 {
var sum int64
for _, b := range balance {
sum += int64(b)
}
if sum < 0 {
return -1
}
n := len(balance)
mn := balance[0]
idx := 0
for i := 1; i < n; i++ {
if balance[i] < mn {
mn = balance[i]
idx = i
}
}
if mn >= 0 {
return 0
}
need := -mn
var ans int64
for j := 1; j < n; j++ {
a := balance[(idx-j+n)%n]
b := balance[(idx+j)%n]
c1 := min(a, need)
need -= c1
ans += int64(c1) * int64(j)
c2 := min(b, need)
need -= c2
ans += int64(c2) * int64(j)
}
return ans
}Complexity analysis
| 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 |
Frequently asked questions
Is Minimum Moves to Balance Circular Array easy or hard?
Minimum Moves to Balance Circular Array is typically classified as a Medium problem. The challenge lies in recognizing that transfers can be counted using cumulative surplus flow rather than explicitly simulating each move.
Minimum Moves to Balance Circular Array Python/Java solution
Implement the greedy simulation by computing the target value, iterating through the array, and maintaining a running flow variable. Add the absolute value of the flow to the answer at each step. The same logic works across Python, Java, C++, Go, and TypeScript with constant extra space.
How to solve Minimum Moves to Balance Circular Array in O(n)?
First compute the target value as total sum divided by array length. Replace each value with its difference from the target and iterate through the array while maintaining a running prefix flow. Each step adds the difference to the flow and contributes abs(flow) to the move count. Choosing the rotation with the smallest prefix start ensures the minimal circular transfer cost.
What is the best approach for Minimum Moves to Balance Circular Array?
The greedy prefix-flow simulation is the most efficient approach. Convert the array into surplus/deficit values relative to the average, then scan once while tracking cumulative flow across boundaries. Summing the absolute value of the running flow gives the minimum number of transfers. This runs in O(n) time and O(1) space.
Is Minimum Moves to Balance Circular Array asked at Google/Amazon/Meta?
Problems involving balancing arrays, load redistribution, and circular prefix flow appear frequently in interviews at large tech companies. Variants similar to load balancing or the Super Washing Machines problem have been reported in interviews at companies like Google, Amazon, and Meta.
What data structure is used in Minimum Moves to Balance Circular Array?
The solution mainly uses a simple array traversal with a running prefix sum to track surplus flow. No advanced data structures are required. The logic relies on greedy redistribution and cumulative flow tracking.
What is the time complexity of Minimum Moves to Balance Circular Array?
The optimal greedy solution runs in O(n) time because the array is processed once to compute surplus flow and transfer counts. Space complexity is O(1) since only a few running variables are required. A brute-force circular simulation can take O(n^2) time if every rotation is tested.