Stone game vi

Array Math Greedy Sorting Heap (Priority Queue) Game Theory

60.5% acceptance

Feb 25, 2026

894

Alice and Bob take turns playing. There are n stones in a pile. On each turn, a player removes a stone and receives points based on their value array. Sort by aliceValues[i]+bobValues[i] descending. They play optimally. Return 1 if Alice wins, -1 if Bob wins, 0 if draw.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn stone_game_vi(alice_values: Vec<i32>, bob_values: Vec<i32>) -> i32 {
    let n = alice_values.len();
    let mut combined: Vec<(i32, i32, i32)> = (0..n)
      .map(|i| (alice_values[i] + bob_values[i], alice_values[i], bob_values[i]))
      .collect();
    combined.sort_unstable_by(|a, b| b.0.cmp(&a.0));
    let mut alice = 0i32;
    let mut bob = 0i32;
    for (turn, (_, av, bv)) in combined.iter().enumerate() {
      if turn % 2 == 0 {
        alice += av;
      } else {
        bob += bv;
      }
    }
    if alice > bob { 1 } else if alice < bob { -1 } else { 0 }
  }
}