Minimum Moves to Balance Circular Array - Video Solutions
Minimum Moves to Balance Circular Array | Clean Intuition | Contest Problem 3 | Leetcode 3776 | MIK
Minimum Moves to Balance Circular Array - Video Solution
Watch 10 video solutions for Minimum Moves to Balance Circular Array, a medium level problem involving Array, Greedy, Sorting. This walkthrough by codestorywithMIK has 4,495 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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.
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 |