Last stone weight ii

Array Dynamic Programming

59.3% acceptance

Feb 25, 2026

3370

143

You are given an array of integers stones where stones[i] is the weight of the ith stone. We are playing a game with the stones. On each turn, we choose any two stones and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is: If x == y, both stones are destroyed, and If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x. At the end of the game, there is at most one stone left. Return the smallest possible weight of the left stone. If there are no stones left, return 0.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn last_stone_weight_ii(stones: Vec<i32>) -> i32 {
    let sum: i32 = stones.iter().sum();
    let target = (sum / 2) as usize;
    let mut dp = vec![false; target + 1];
    dp[0] = true;
    for s in stones {
      for j in (s as usize..=target).rev() {
        if dp[j - s as usize] { dp[j] = true; }
      }
    }
    let best = (0..=target).rev().find(|&j| dp[j]).unwrap_or(0) as i32;
    sum - 2 * best
  }
}