Last Stone Weight II - Practice Coding Problems

Last Stone Weight II - Problem

You are given an array of integers stones where stones[i] is the weight of the i-th 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
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.

Input & Output

Example 1 — Balanced Partition

$ Input: stones = [2,7,4,1]

› Output: 0

💡 Note: We can partition stones into {7} and {2,4,1}. Both groups have weight 7, so when all stones are smashed optimally, the final weight is |7-7| = 0.

Example 2 — Unbalanced Result

$ Input: stones = [31,26,33,21,40]

› Output: 5

💡 Note: Total weight is 151. Best partition is around 75-76. We can achieve 76 vs 75, giving minimum final weight of |76-75| = 1. But optimal stone smashing gives us 5.

Example 3 — Single Stone

$ Input: stones = [1]

› Output: 1

💡 Note: Only one stone remains untouched, so the answer is 1.

Constraints

1 ≤ stones.length ≤ 30
1 ≤ stones[i] ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input

Array of stone weights to be smashed

Transform

Convert to partition problem for minimal difference

Output

Minimum possible final stone weight

Key Takeaway

🎯 Key Insight: Stone smashing game is equivalent to partitioning into two balanced groups

Asked in

a Amazon 15 G Google 8

The key insight is that this stone smashing game is equivalent to partitioning stones into two groups with minimal weight difference. The optimal approach uses dynamic programming to find all possible subset sums, then selects the partition closest to half the total weight. Time: O(n × sum), Space: O(sum).

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming - Subset Sum	O(n × sum)	O(sum)	Transform the problem into finding the closest partition to half the total weight
Brute Force Simulation	O(2ⁿ)	O(n)	Simulate all possible stone smashing sequences using recursion

Dynamic Programming - Subset Sum — Algorithm Steps

Calculate total weight of all stones
Use DP to find all possible subset sums up to total/2
Find the largest achievable sum ≤ total/2
Return total - 2 * closest_sum

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Total

Sum all stone weights

DP Table

Build table of possible sums

Find Closest

Get closest sum to total/2

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int solution(int* stones, int size) {
    int total = 0;
    for (int i = 0; i < size; i++) {
        total += stones[i];
    }
    int target = total / 2;
    
    // DP to find all possible sums
    bool* dp = (bool*)calloc(target + 1, sizeof(bool));
    dp[0] = true;
    
    for (int i = 0; i < size; i++) {
        for (int j = target; j >= stones[i]; j--) {
            dp[j] = dp[j] || dp[j - stones[i]];
        }
    }
    
    // Find the closest sum to target
    int closest = 0;
    for (int i = 0; i <= target; i++) {
        if (dp[i]) {
            closest = i;
        }
    }
    
    free(dp);
    return total - 2 * closest;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    int stones[100];
    int size = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        stones[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(stones, size));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × sum)

DP table has n stones × sum possible values, each cell computed once

✓ Linear Growth

Space Complexity

O(sum)

DP array stores boolean values for each possible sum up to total weight

✓ Linear Space

89.0K Views

Medium Frequency

~15 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming - Subset Sum — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler