Last Stone Weight - Practice Coding Problems

Last Stone Weight - 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 the heaviest two stones and smash them together. Suppose the heaviest two 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 weight of the last remaining stone. If there are no stones left, return 0.

Input & Output

Example 1 — Multiple Smashes

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

› Output: 1

💡 Note: Smash 8,7 → 1 remains. Smash 4,2 → 2 remains. Smash 2,1 → 1 remains. Smash 1,1 → both destroyed. Final stone: 1

Example 2 — Equal Stones

$ Input: stones = [1]

› Output: 1

💡 Note: Only one stone remains, return its weight: 1

Example 3 — All Destroyed

$ Input: stones = [3,3]

› Output: 0

💡 Note: Smash 3,3 → both stones destroyed (equal weights), no stones left, return 0

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Stones

Array of stone weights ready for smashing

Smash Process

Repeatedly find and smash two heaviest stones

Final Result

Weight of last remaining stone or 0

Key Takeaway

🎯 Key Insight: Max heap efficiently maintains access to the heaviest stones at each step

Asked in

a Amazon 35 G Google 25 M Microsoft 20 f Facebook 15

The key insight is to use a max heap to efficiently get the two heaviest stones. Best approach is Max Heap with Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Linear Search	O(n³)	O(1)	Find two heaviest stones by scanning entire array each turn
Max Heap (Priority Queue)	O(n log n)	O(n)	Use max heap to efficiently get the two heaviest stones

Brute Force - Linear Search — Algorithm Steps

Step 1: Scan array to find heaviest stone
Step 2: Scan again to find second heaviest stone
Step 3: Remove both stones and add difference if needed
Step 4: Repeat until ≤1 stone remains

Visualization

Tap to expand

Step-by-Step Walkthrough

Scan Array

Find heaviest stone by checking each element

Scan Again

Find second heaviest from remaining stones

Smash & Repeat

Remove both, add difference, repeat process

Code -

solution.c — C

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

int solution(int* stones, int size) {
    while (size > 1) {
        // Find heaviest stone
        int max1Idx = 0;
        for (int i = 1; i < size; i++) {
            if (stones[i] > stones[max1Idx]) {
                max1Idx = i;
            }
        }
        
        int max1 = stones[max1Idx];
        // Remove max1 by shifting elements
        for (int i = max1Idx; i < size - 1; i++) {
            stones[i] = stones[i + 1];
        }
        size--;
        
        // Find second heaviest stone
        int max2Idx = 0;
        for (int i = 1; i < size; i++) {
            if (stones[i] > stones[max2Idx]) {
                max2Idx = i;
            }
        }
        
        int max2 = stones[max2Idx];
        // Remove max2 by shifting elements
        for (int i = max2Idx; i < size - 1; i++) {
            stones[i] = stones[i + 1];
        }
        size--;
        
        // Add difference back if stones are different
        if (max1 != max2) {
            stones[size] = max1 - max2;
            size++;
        }
    }
    
    return size == 0 ? 0 : stones[0];
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n³)

O(n) turns × O(n) to find max twice × O(n) to remove elements

⚠ Quadratic Growth

Space Complexity

O(1)

Only using a few variables, no extra data structures

✓ Linear Space

180.0K Views

Medium Frequency

~15 min Avg. Time

2.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

Brute Force - Linear Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler