03 — Stacks, Queues, Binary Search, Linked Lists#

# Valid Parentheses
def is_valid(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for c in s:
        if c in pairs:
            if not stack or stack.pop() != pairs[c]:
                return False
        else:
            stack.append(c)
    return not stack
 
# Evaluate Reverse Polish Notation
def eval_rpn(tokens):
    stack = []
    for t in tokens:
        if t in "+-*/" and len(t) == 1:
            b, a = stack.pop(), stack.pop()      # order matters for - and /
            if t == '+': stack.append(a + b)
            elif t == '-': stack.append(a - b)
            elif t == '*': stack.append(a * b)
            else: stack.append(int(a / b))       # truncate toward zero,
        else:                                     # NOT a // b (floors)
            stack.append(int(t))
    return stack[0]
 
# Min Stack — O(1) getMin
class MinStack:
    def __init__(self):
        self.stack = []
        self.mins = []                    # mins[i] = min of stack[0..i]
    def push(self, x):
        self.stack.append(x)
        self.mins.append(x if not self.mins else min(x, self.mins[-1]))
    def pop(self):
        self.stack.pop(); self.mins.pop()
    def top(self):
        return self.stack[-1]
    def getMin(self):
        return self.mins[-1]

# Next Greater Element — for each i, the first j > i with nums[j] > nums[i]
def next_greater(nums):
    res = [-1] * len(nums)
    stack = []                            # indices, values DECREASING
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            res[stack.pop()] = x          # x is the answer for that index
        stack.append(i)
    return res

def daily_temperatures(temps):
    res = [0] * len(temps)
    stack = []                          # indices of days awaiting a warmer day
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            res[j] = i - j              # distance, not the value
        stack.append(i)
    return res
# O(n) time, O(n) space

def largest_rectangle_area(heights):
    stack = []          # (start_index, height), heights increasing
    best = 0
    for i, h in enumerate(heights):
        start = i
        while stack and stack[-1][1] > h:
            idx, height = stack.pop()
            best = max(best, height * (i - idx))
            start = idx          # this bar can extend back to idx
        stack.append((start, h))
    # drain: remaining bars extend to the end
    n = len(heights)
    for idx, height in stack:
        best = max(best, height * (n - idx))
    return best
# O(n) time, O(n) space

def binary_search(nums, target):
    lo, hi = 0, len(nums) - 1          # INCLUSIVE bounds
    while lo <= hi:                    # <= because lo==hi is a valid candidate
        mid = lo + (hi - lo) // 2      # avoids overflow in other languages
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            lo = mid + 1               # mid is ruled out
        else:
            hi = mid - 1
    return -1

def first_true(lo, hi, condition):
    """Smallest x in [lo, hi] where condition(x) is True.
       Requires condition to be monotonic: F F F T T T."""
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if condition(mid):
            hi = mid           # mid might be the answer — KEEP it
        else:
            lo = mid + 1       # mid is definitely not — discard
    return lo

# Koko Eating Bananas: minimum speed k to eat all piles within h hours
import math
def min_eating_speed(piles, h):
    def hours_needed(k):
        return sum(math.ceil(p / k) for p in piles)   # or (p + k - 1)//k
 
    lo, hi = 1, max(piles)          # answer is somewhere in this range
    while lo < hi:
        mid = (lo + hi) // 2
        if hours_needed(mid) <= h:  # mid works — try smaller
            hi = mid
        else:
            lo = mid + 1
    return lo
# O(n log(max(piles)))

def search_rotated(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:              # LEFT half is sorted
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1                   # target is in the sorted left
            else:
                lo = mid + 1
        else:                                   # RIGHT half is sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

def find_min(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:      # min is strictly right of mid
            lo = mid + 1
        else:                          # min is at mid or left of it
            hi = mid
    return nums[lo]

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build(head):
    dummy = ListNode(0)
    tail = dummy
    while head:
        tail.next = ListNode(head.val)
        tail = tail.next
        head = head.next
    return dummy.next          # skip the dummy

# Middle of the list
def middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow                # for even length, this is the SECOND middle
 
# Cycle detection — O(1) space
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            return True
    return False
 
# Find where the cycle STARTS (Floyd's phase 2)
def detect_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            slow2 = head
            while slow2 is not slow:      # both move 1 step; they meet at start
                slow2, slow = slow2.next, slow.next
            return slow
    return None

def remove_nth_from_end(head, n):
    dummy = ListNode(0, head)
    slow = fast = dummy
    for _ in range(n):
        fast = fast.next
    while fast.next:
        slow, fast = slow.next, fast.next
    slow.next = slow.next.next     # slow is now just before the target
    return dummy.next

# Iterative — O(n) time, O(1) space. This is the expected answer.
def reverse_list(head):
    prev = None
    curr = head
    while curr:
        nxt = curr.next     # 1. save the next node BEFORE breaking the link
        curr.next = prev    # 2. reverse the pointer
        prev = curr         # 3. advance prev
        curr = nxt          # 4. advance curr
    return prev             # prev is the new head
 
# Recursive — O(n) space (stack)
def reverse_recursive(head):
    if not head or not head.next:
        return head
    new_head = reverse_recursive(head.next)   # leap of faith: rest is reversed
    head.next.next = head                     # point the next node back at us
    head.next = None                          # and cut our forward link
    return new_head

def reorder_list(head):
    if not head or not head.next: return
    # 1. find the middle
    slow, fast = head, head.next
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    # 2. reverse the second half
    second = slow.next
    slow.next = None                  # split
    prev = None
    while second:
        nxt = second.next
        second.next = prev
        prev = second
        second = nxt
    # 3. merge alternately
    first, second = head, prev
    while second:
        n1, n2 = first.next, second.next
        first.next = second
        second.next = n1
        first, second = n1, n2

class Node:
    def __init__(self, key=0, val=0):
        self.key, self.val = key, val
        self.prev = self.next = None
 
class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.map = {}
        self.head = Node()            # sentinel: most recent side
        self.tail = Node()            # sentinel: least recent side
        self.head.next, self.tail.prev = self.tail, self.head
 
    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
 
    def _add_front(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node
 
    def get(self, key):
        if key not in self.map:
            return -1
        node = self.map[key]
        self._remove(node); self._add_front(node)     # mark as most recent
        return node.val
 
    def put(self, key, value):
        if key in self.map:
            self._remove(self.map[key])
        node = Node(key, value)
        self.map[key] = node
        self._add_front(node)
        if len(self.map) > self.cap:
            lru = self.tail.prev
            self._remove(lru)
            del self.map[lru.key]      # need lru.key — that's why nodes store it