Last Stone Weight

Problem Statement:-

You are given an array of integers stones where stones[i] is the weight of the i<sup>th</sup> 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, 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 weight of the last remaining stone. If there are no stones left, return 0.

Link: https://leetcode.com/problems/last-stone-weight/

Problem Explanation with examples:-

Example 1

Input: stones = [2,7,4,1,8,1]
Output: 1
Explanation: 
We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then,
we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then,
we combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of the last stone.

Example 2

Input: stones = [1]
Output: 1
Explanation: There is only 1 stone so we cannot smash it with another stone.

Constraints

• 1 <= stones.length <= 30

• 1 <= stones[i] <= 1000

Intuition:-

• We will keep sorting and extracting the last 2 elements as per the given constraints until there is only 1 element left.

• If the last 2 elements are equal, we will remove them from the list else we will add the difference of the 2 elements to the list.

• If the list is empty, we will return 0 else we will return the last element of the list.

Solution:-

• Create a while loop that will run until there is only 1 element left in the list.

• Sort the list.

• Extract the last 2 elements of the list.

• Remove the last 2 elements from the list.

• If the last 2 elements are not equal, we will add the difference of the 2 elements to the list.

• After the while loop, if the list is empty, we will return 0 else we will return the last element of the list.

Code:-

JAVA Solution

class Solution {
    public int lastStoneWeight(int[] stones) {
        while (stones.length > 1) {
            Arrays.sort(stones);
            int a = stones[stones.length - 1];
            int b = stones[stones.length - 2];
            stones = Arrays.copyOf(stones, stones.length - 2);
            if (a != b) {
                stones = Arrays.copyOf(stones, stones.length + 1);
                stones[stones.length - 1] = Math.abs(a - b);
            }
        }

        if (stones.length == 0) {
            return 0;
        }

        return stones[0];
    }
}

Python Solution

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        while len(stones)>1:
            stones.sort()
            a = stones[-1]
            b = stones[-2]
            stones.pop()
            stones.pop()
            if a!=b:
                stones.append(max(a,b)-min(a,b))

        if len(stones) == 0:
            return 0
        return stones[0]

Complexity Analysis:-

TIME:-

The time complexity of the code is O(nlogn) where n is the length of the list as we need to sort the list and extract the last 2 elements.

SPACE:-

The space complexity of the code is O(1) as we are not using any extra space.

References:-

• Array

Connect with me:-

• Twitter

• Github

• LinkedIn