```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])```
```//Useful for background tasks, uploading resources, print/task

//Can be impleneted with array (use push/shift or unshift/pop) or queue class
//Again any time you use shift/unshift, you have O(N)
//FIFO

class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next

class Queue:
def __init__(self, first=None, last=None, size=0):
self.first = first
self.last = last
self.size = size

#add to end of queue (similar to append or push) and returns size
def enqueue(self, value):
new_node = Node(value)

if self.first == None:
self.first = new_node
self.last = new_node
else:
self.last.next = new_node
self.last = new_node

self.size += 1
return self.size

#remove from beginning of queue
def dequeue(self):
if self.first == None:
return None

temp = self.first
if self.first == self.last:
self.last = None
#set 1st property to be original first's next
self.first = self.first.next
self.size -= 1

return temp.value

#useful to visualize any other function works
def print_queue_to_list(self):
result = []
current = self.first
while current:
result.append(current.value)
current = current.next
print(result)

s = Queue()
s.enqueue(1)
s.enqueue(2)
s.enqueue(3)
s.print_queue_to_list() >> [1, 2, 3]
s.dequeue()
s.print_queue_to_list() >> [2, 3]

// Big O:
// Insertion and Removal: O(1) **this is mainly what stacks are good for
// Access and Search: O(N)
//Recall with array implenetation, insertion and removal is not constant ```
```# //Used in call stack, undo/redo, routing

# //Array implenentation (just use pop/push or shift/unshift)
# //Recall that pop/push is more efficient than shift/unshift
# //Indexes take up memory so linked list implenetation will be better

# //Single linked implenetation of stack:

class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next

class Stack:
def __init__(self, first=None, last=None, size=0):
self.first = first
self.last = last
self.size = size

#Similar to shift or insert(0, value). Adds to stack and returns size. Recall stack is LIFO
def push(self, value):
new_node = Node(value)
if self.first == None:
self.first = new_node
self.last = new_node
else:
#stores current 1st property on stack
temp = self.first
#reset 1st property to be newly created one
self.first = new_node
#set new next property
self.first.next = temp
#increment stack
self.size += 1
return self.size

#in python, this would be pop(0). Similar to unshift. Removes first element on stack
def pop(self):
#special case if stakc is empty
if self.first == None:
return None

temp = self.first
#if there is only 1 node, set 1st node and last property to be None
if self.first == self.last:
self.last = None
#self.first = None will be set in next line

#for all scenarios except empty stack
self.first = self.first.next
self.size -= 1
return temp.value

#useful to visualize reverse() or any other function works
def print_stack_to_list(self):
result = []
current = self.first
while current:
result.append(current.value)
current = current.next
print(result)

s = Stack()
s.push(1)
s.push(2)
s.push(3)
s.print_stack_to_list() # [3, 2, 1]
s.pop()
s.print_stack_to_list() #[2, 1]

# //these methods deal with 1st node bc thats what stacks do (LIFO)
# // Big O:
# // Insertion and Removal: O(1) **this is mainly what stacks are good for
# // Access and Search: O(N)
```
star

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

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

Sun Jul 31 2022 19:07:23 GMT+0000 (UTC) Udemy

#python #methods #udemy #push #pop #unshift #shift #fifo