🐧 Phase 2 — Core Data Structures (Days 16–35)

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
# Reverse a linked list
def reverseList(head):
    prev = None
    while head:
        nxt = head.next
        head.next = prev
        prev = head
        head = nxt
    return prev
 
# Find middle node (slow/fast)
def middleNode(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow
 
# Detect cycle (Floyd's algorithm)
def hasCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False
 
# Find cycle start
def detectCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            ptr = head
            while ptr != slow:
                ptr = ptr.next
                slow = slow.next
            return ptr
    return None
 
# Merge two sorted lists
def mergeTwoLists(l1, l2):
    dummy = ListNode()
    cur = dummy
    while l1 and l2:
        if l1.val <= l2.val:
            cur.next = l1; l1 = l1.next
        else:
            cur.next = l2; l2 = l2.next
        cur = cur.next
    cur.next = l1 or l2
    return dummy.next

# Valid parentheses
def isValid(s):
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}
    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
 
# Daily Temperatures (next greater element)
def dailyTemperatures(temps):
    res = [0] * len(temps)
    stack = []  # indices, decreasing temps
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            res[j] = i - j
        stack.append(i)
    return res
 
# Largest Rectangle in Histogram
def largestRectangleArea(heights):
    stack = []  # indices, increasing heights
    max_area = 0
    for i, h in enumerate(heights + [0]):
        while stack and heights[stack[-1]] >= h:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)
    return max_area
 
# Min stack (O(1) getMin)
class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []
    def push(self, val):
        self.stack.append(val)
        m = min(val, self.min_stack[-1] if self.min_stack else val)
        self.min_stack.append(m)
    def pop(self):
        self.stack.pop(); self.min_stack.pop()
    def top(self): return self.stack[-1]
    def getMin(self): return self.min_stack[-1]

# Group Anagrams
def groupAnagrams(strs):
    groups = {}
    for s in strs:
        key = ''.join(sorted(s))
        groups.setdefault(key, []).append(s)
    return list(groups.values())
 
# Longest Consecutive Sequence (O(n) using a set)
def longestConsecutive(nums):
    num_set = set(nums)
    longest = 0
    for n in num_set:
        if n - 1 not in num_set:  # only start counting from sequence start
            length = 1
            while n + length in num_set:
                length += 1
            longest = max(longest, length)
    return longest
 
# Design a HashMap from scratch (understand the internals)
class MyHashMap:
    def __init__(self):
        self.size = 1000
        self.buckets = [[] for _ in range(self.size)]
    def _hash(self, key):
        return key % self.size
    def put(self, key, value):
        bucket = self.buckets[self._hash(key)]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value); return
        bucket.append((key, value))
    def get(self, key):
        bucket = self.buckets[self._hash(key)]
        for k, v in bucket:
            if k == key: return v
        return -1

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val; self.left = left; self.right = right
 
# DFS traversals
def inorder(root):
    return inorder(root.left) + [root.val] + inorder(root.right) if root else []
 
# Maximum depth
def maxDepth(root):
    if not root: return 0
    return 1 + max(maxDepth(root.left), maxDepth(root.right))
 
# Validate BST (pass down valid range)
def isValidBST(root, low=float('-inf'), high=float('inf')):
    if not root: return True
    if not (low < root.val < high): return False
    return isValidBST(root.left, low, root.val) and isValidBST(root.right, root.val, high)
 
# Lowest Common Ancestor (BST)
def lowestCommonAncestor(root, p, q):
    while root:
        if p.val < root.val and q.val < root.val: root = root.left
        elif p.val > root.val and q.val > root.val: root = root.right
        else: return root
 
# Level order traversal (BFS)
from collections import deque
def levelOrder(root):
    if not root: return []
    result, queue = [], deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        result.append(level)
    return result
 
# Serialize/Deserialize binary tree
def serialize(root):
    vals = []
    def dfs(node):
        if not node: vals.append('#'); return
        vals.append(str(node.val))
        dfs(node.left); dfs(node.right)
    dfs(root)
    return ','.join(vals)
 
def deserialize(data):
    vals = iter(data.split(','))
    def build():
        val = next(vals)
        if val == '#': return None
        node = TreeNode(int(val))
        node.left = build(); node.right = build()
        return node
    return build()

from collections import deque
 
# Sliding window maximum (monotonic deque)
def maxSlidingWindow(nums, k):
    dq = deque()  # indices, decreasing values
    result = []
    for i, n in enumerate(nums):
        while dq and nums[dq[-1]] < n: dq.pop()
        dq.append(i)
        if dq[0] <= i - k: dq.popleft()
        if i >= k - 1: result.append(nums[dq[0]])
    return result
 
# Design Circular Queue
class MyCircularQueue:
    def __init__(self, k):
        self.queue = [0] * k
        self.head = self.count = 0
        self.capacity = k
    def enqueue(self, value):
        if self.count == self.capacity: return False
        self.queue[(self.head + self.count) % self.capacity] = value
        self.count += 1
        return True
    def dequeue(self):
        if self.count == 0: return False
        self.head = (self.head + 1) % self.capacity
        self.count -= 1
        return True