Snippets Collections
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

Save snippets that work with our extensions

Available in the Chrome Web Store Get Firefox Add-on Get VS Code extension