Skip to main content
Talentd

Minimum Moves to Balance Circular Array - Solution & Explanation

MediumArrayGreedySorting10 min readAsked at: Bloomberg
Practice this problem

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 = 1 to i = 2, resulting in balance = [5, 0, -3]
  • Move 1 unit from i = 0 to i = 2, resulting in balance = [4, 0, -2]
  • Move 1 unit from i = 0 to i = 2, resulting in balance = [3, 0, -1]
  • Move 1 unit from 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:

  • Move 1 unit from i = 1 to i = 2, resulting in balance = [1, 1, -4, 2]
  • Move 1 unit from i = 1 to i = 2, resulting in balance = [1, 0, -3, 2]
  • Move 1 unit from i = 3 to i = 2, resulting in balance = [1, 0, -2, 1]
  • Move 1 unit from i = 3 to i = 2, resulting in balance = [1, 0, -1, 0]
  • Move 1 unit from i = 0 to i = 1, resulting in balance = [0, 1, -1, 0]
  • Move 1 unit from 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] <= 109
  • There is at most one negative value in balance initially.

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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor ā†’

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Rotation SimulationO(n^2)O(1)When verifying logic or handling very small arrays where trying every circular start is acceptable
Greedy Prefix Flow SimulationO(n)O(1)General case and interview solution; computes minimal transfers using cumulative surplus

Video Solution

Minimum Moves to Balance Circular Array | Clean Intuition | Contest Problem 3 | Leetcode 3776 | MIK ā€¢ codestorywithMIK ā€¢ 4,495 views views

Watch 9 more video solutions ā†’

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.

Ready to solve this problem?

Practice Minimum Moves to Balance Circular Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays