Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

1130. Last Stone Weight II

My accepted Python solution to LeetCode problem 1130, Last Stone Weight II, running in 7ms.

  • Difficulty: Medium
  • Python
  • Runtime 7ms
  • Memory 17.4MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 7ms, memory 17.4MB, accepted 2026-01-02.

python
class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        total = sum(stones)
        target = total // 2
        
        # DP to find all possible sums up to target
        dp = {0}
        
        for stone in stones:
            new_dp = set()
            for s in dp:
                if s + stone <= target:
                    new_dp.add(s + stone)
            dp = dp | new_dp
        
        # Find the largest sum <= target
        max_sum = max(dp)
        
        # Answer is total - 2 * max_sum
        return total - 2 * max_sum

Source