```class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
stones = [-s for s in stones]
heapq.heapify(stones)

while len(stones) > 1:
first = abs(heapq.heappop(stones)) #linear time for python
second = abs(heapq.heappop(stones))

if first > second:
heapq.heappush(stones, second - first) #remember that since it's a minHeap we need negative numbers so it's second - first

#edge case to account if stones is empty whether originally or after smashing
stones.append(0)

return abs(stones[0])```
```import java.util.*;
import java.io.*;

class Test {

public static class MinHeap
{
int arr[];
int size;
int capacity;

MinHeap(int c){
size = 0;
capacity = c;
arr = new int[c];
}

int left(int i) { return (2*i + 1); }
int right(int i) { return (2*i + 2); }
int parent(int i) { return (i-1)/2; }

public void insert(int x)
{
if (size == capacity)return;
size++;
arr[size-1]=x;

for (int i=size-1;i!=0 && arr[parent(i)]>arr[i];)
{
int temp = arr[i];
arr[i] = arr[parent(i)];
arr[parent(i)] = temp;
i = parent(i);
}
}

public void minHeapify(int i)
{
int lt = left(i);
int rt = right(i);
int smallest = i;
if (lt < size && arr[lt] < arr[i])
smallest = lt;
if (rt < size && arr[rt] < arr[smallest])
smallest = rt;
if (smallest != i)
{
int temp = arr[i];
arr[i] = arr[smallest];
arr[smallest] = temp;
minHeapify(smallest);
}
}

public int extractMin()
{
if (size <= 0)
return Integer.MAX_VALUE;
if (size == 1)
{
size--;
return arr[0];
}
int temp = arr[0];
arr[0] = arr[size-1];
arr[size-1] = temp;
size--;
minHeapify(0);

return arr[size];
}

}

public static void main(String args[])
{
MinHeap h=new MinHeap(11);
h.insert(3);
h.insert(2);
h.insert(15);
h.insert(20);
System.out.print(h.extractMin());     // OUTPUT : 2
}
} ```
star

Tue Aug 16 2022 06:14:12 GMT+0000 (Coordinated Universal Time) https://leetcode.com/problems/last-stone-weight/

#python #neetcode #minheap #maxheap #pop #push #heapify
star

Tue Feb 08 2022 15:25:57 GMT+0000 (Coordinated Universal Time)

#java #gfg #geeksforgeeks #lecture #heap #binaryheap #heapify #extract