Minimum moves to balance circular array

Array Greedy Sorting

40.2% acceptance

Jan 13, 2026

111

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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_moves(balance: Vec<i32>) -> i64 {
    let n = balance.len();
    let total: i64 = balance.iter().map(|&x| x as i64).sum();
    
    // Find negative index
    let neg_pos = match balance.iter().position(|&x| x < 0) {
      Some(p) => p,
      None => return 0, // already all non-negative
    };
    
    let deficit = -(balance[neg_pos] as i64);
    
    // If total sum < 0, impossible
    if total < 0 {
      return -1;
    }
    
    // Rearrange so that deficit position is at index 0
    // Build a linear array of available supplies going right from neg_pos+1
    // right[i] = balance at position (neg_pos + 1 + i) % n, for i in 0..n-1
    // We try all splits x = 0..=n-1: take from right[0..x], left from right[x..n-1]
    // (going clockwise for right, counter-clockwise for left)
    
    // right_supply[i] = balance[(neg_pos + 1 + i) % n]
    // cost from right: we collect in order, person i (0-indexed) has distance (i+1)
    //   we take as much as possible up to what we need
    // cost from left: person at position (neg_pos - 1 - j) % n (j=0,1,...) has distance j+1
    //   but accessing in right[] means index n-1-j
    
    // Build right supply array
    let right: Vec<i64> = (0..n - 1).map(|i| (balance[(neg_pos + 1 + i) % n] as i64).max(0)).collect();
    // Note: only positive balances can supply
    
    // Precompute prefix sums with costs for "taking from right starting at index 0"
    // For split x: take from positions in right[0..x], then take from right[n-1..x] going backwards (left)
    // But we must collect exactly `deficit` units total
    
    // Function to compute minimum cost given we MUST take all deficit from a set of suppliers
    // with given distances (greedy: take from nearest first)
    // right[0] is at distance 1, right[1] at distance 2, etc.
    // left[0] = right[n-2] at distance 1, left[1] = right[n-3] at distance 2, etc.
    
    // For split x: take first x positions from right, rest from left (last n-1-x positions of right in reverse)
    
    // Precompute prefix sums of right
    let mut prefix = vec![0i64; n];
    for i in 0..n - 1 {
      prefix[i + 1] = prefix[i] + right[i];
    }
    
    let total_supply: i64 = prefix[n - 1];
    if total_supply < deficit {
      return -1;
    }
    
    // For a given cut x:
    //   right sources: right[0](d=1), right[1](d=2), ..., right[x-1](d=x)
    //   left sources:  right[n-2](d=1), right[n-3](d=2), ..., right[x](d=n-1-x)
    // Merge both sides by distance and take greedily (nearest first).
    // This correctly handles cases where a closer left source should be used
    // before a farther right source (and vice-versa).
    let compute_cost = |x: usize| -> i64 {
      let l_count = n - 1 - x;
      let mut ri = 0usize; // next right source index (into right[ri], dist ri+1)
      let mut li = 0usize; // next left source index (right[n-2-li], dist li+1)
      let mut rem = deficit;
      let mut cost = 0i64;
      while rem > 0 {
        let r_dist = if ri < x { (ri as i64) + 1 } else { i64::MAX };
        let l_dist = if li < l_count { (li as i64) + 1 } else { i64::MAX };
        if r_dist == i64::MAX && l_dist == i64::MAX {
          return i64::MAX / 2;
        }
        if r_dist <= l_dist {
          let take = rem.min(right[ri]);
          cost += take * r_dist;
          rem -= take;
          ri += 1;
        } else {
          let take = rem.min(right[n - 2 - li]);
          cost += take * l_dist;
          rem -= take;
          li += 1;
        }
      }
      cost
    };
    
    // Ternary search on x in 0..=n-1
    // Use <= so that when both midpoints are equal (flat region), we shrink
    // from the hi side and don't skip the true minimum on the lo side.
    let mut lo = 0usize;
    let mut hi = n - 1;
    while hi - lo > 2 {
      let m1 = lo + (hi - lo) / 3;
      let m2 = hi - (hi - lo) / 3;
      if compute_cost(m1) <= compute_cost(m2) {
        hi = m2;
      } else {
        lo = m1;
      }
    }
    
    (lo..=hi).map(|x| compute_cost(x)).min().unwrap()
  }
}