Skip to main content
Talentd

Minimum Moves to Balance Circular Array II - Solution & Explanation

HardPremiumFree on FleetCode19 min read
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.

 

Example 1:

Input: balance = [-1,2,-1]

Output: 2

Explanation:

One optimal sequence of moves is:

  • Move 1 unit from i = 1 to i = 0, resulting in balance = [0, 1, -1]
  • Move 1 unit from i = 1 to i = 2, resulting in balance = [0, 0, 0]

Thus, the minimum number of moves required is 2.

Example 2:

Input: balance = [4,-1,-2]

Output: 3

Explanation:

One optimal sequence of moves is:

  • Move 1 unit from i = 0 to i = 1, resulting in balance = [3, 0, -2]
  • Move 1 unit from i = 0 to i = 2, resulting in balance = [2, 0, -1]
  • Move 1 unit from i = 0 to i = 2, resulting in balance = [1, 0, 0]

Thus, the minimum number of moves required is 3.

Example 3:

Input: balance = [-3,-3,5]

Output: -1

Explanation:

It is impossible to make all balances non-negative for balance = [-3, -3, 5], so the answer is -1.

 

Constraints:

  • 1 <= n == balance.length <= 1000
  • -105 <= balance[i] <= 105

Approach Overview

Problem Overview: Given a circular array, find the minimum number of moves required to make all elements equal, where each move increments or decrements an element by 1.

Approach 1: Brute Force (O(n^2))

Try every possible target value from the array. For each target, calculate the total moves needed by summing absolute differences between each element and the target. This approach is inefficient but demonstrates understanding of the problem constraints.

Approach 2: Median-based Optimization (O(n log n))

Sort the array and use the median as the target value. The median minimizes the sum of absolute deviations, reducing the total moves. This approach leverages the property that the median provides the optimal balance point in a sorted array.

Recommended for interviews: The median-based approach is expected in interviews. It shows you understand mathematical optimization and can apply sorting to reduce complexity from O(n^2) to O(n log n). Mention that brute force is a starting point but median is optimal.

Solution

Let n be the length of balance. If the sum of all balances is negative, it is impossible to make everyone's balance non-negative, so we return -1 directly.

Otherwise, we model the problem as a minimum cost flow problem:

  • Create a source s and a sink t;
  • For each person i with balance[i] > 0 (a surplus), add an edge from s to i with capacity balance[i] and unit cost 0;
  • For each person i with balance[i] < 0 (a deficit), add an edge from i to t with capacity -balance[i] and unit cost 0;
  • For each i, add an edge from i to each of its two neighbors with infinite capacity and unit cost 1, representing that transferring 1 unit of balance to a neighbor takes 1 move.

Let totalDeficit = sum_{balance[i] < 0} (-balance[i]) be the total deficit. The answer is the minimum cost of sending totalDeficit units of flow from s to t. Since the circular edges connect everyone in both directions, all the required flow can always be delivered as long as the total balance is non-negative. We use SPFA-based successive shortest path augmentation to solve the minimum cost flow problem.

Note that each augmentation pushes the entire bottleneck flow along a shortest path instead of just 1 unit: the bottleneck edge is either an edge connected to the source or the sink (which then gets saturated), or a reverse circular edge (which reroutes all the existing flow on the corresponding forward edge). Hence the number of augmentations does not depend on the magnitudes of the balances and stays on the order of O(n) for the constraints of this problem. Each augmentation uses SPFA to find a shortest augmenting path, which takes O(VE) time in the worst case, where V = n + 2 and E = O(n).

The time complexity is O(n^3) in the worst case, and the space complexity is O(n). Note that O(n^3) is a very conservative bound: on the one hand, there are only O(n) augmentations in practice; on the other hand, the graph in this problem is a unit-cost cycle, on which SPFA behaves almost like BFS — each node is dequeued only a constant number of times on average, so one augmentation actually costs about O(n). The total amount of work is therefore about O(n^2) in practice, roughly 10^7 simple operations when n = 1000, which is fast enough to pass. For a strictly provable bound, SPFA can be replaced by Dijkstra's algorithm with Johnson's potentials, giving O(n^2 log n) time.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute ForceO(n^2)O(1)Only for small arrays
Median-basedO(n log n)O(1)General case

Frequently Asked Questions

Minimum Moves to Balance Circular Array II Python solution
Python solutions typically involve sorting the array and calculating the median, then summing absolute differences for the result.
Is Minimum Moves to Balance Circular Array II easy or hard?
This problem is rated Hard due to the need for mathematical insight (median optimization) beyond brute force approaches.
How to solve Minimum Moves to Balance Circular Array II in O(n log n)?
Sort the array and use the median as the target. The sum of absolute differences between each element and the median gives the minimum moves.
What is the best approach for Minimum Moves to Balance Circular Array II?
The median-based approach is optimal, reducing the problem to O(n log n) time by sorting the array and using the median as the target value.
Is Minimum Moves to Balance Circular Array II asked at Google/Amazon/Meta?
This problem tests array manipulation and optimization, skills relevant to interviews at top tech companies like Google and Amazon.
What data structure is used in Minimum Moves to Balance Circular Array II?
The problem primarily uses arrays. Sorting the array enables the median-based optimization.
What is the time complexity of Minimum Moves to Balance Circular Array II?
The optimal solution has O(n log n) time complexity due to sorting, with O(1) space complexity if sorted in-place.

Ready to solve this problem?

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

Practice on FleetCode