Data Structures Visualizer Suite

• 📌 "Reverse a linked list." → Three pointers: prev, curr, next. Iterate and reassign. O(n) time, O(1) space.
• 📌 "Detect a cycle in a linked list." → Floyd's tortoise-and-hare: fast (2 steps) and slow (1 step) meet inside cycle.
• 📌 "Find the middle of a linked list." → Two pointers: slow moves 1, fast moves 2. When fast reaches end, slow is at middle.

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

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, val):
        node = ListNode(val)
        if not self.head: self.head = node; return
        curr = self.head
        while curr.next: curr = curr.next
        curr.next = node

    def reverse(self):
        prev, curr = None, self.head
        while curr:
            nxt = curr.next
            curr.next = prev
            prev = curr; curr = nxt
        self.head = prev

    def has_cycle(self):
        slow = fast = self.head
        while fast and fast.next:
            slow = slow.next; fast = fast.next.next
            if slow == fast: return True
        return False

• 📌 "Valid Parentheses." → Push open brackets; pop and match when close bracket seen. Return stack.isEmpty() at end.
• 📌 "Next Greater Element." → Monotonic decreasing stack. Pop when you find a larger element — that larger element is the answer.
• 📌 "Min Stack — support getMin() in O(1)." → Maintain a second stack tracking minimums. Push current min alongside each value.

class Stack:
    def __init__(self): self._data = []
    def push(self, val): self._data.append(val)   # O(1)
    def pop(self):
        if not self._data: raise IndexError("Empty stack")
        return self._data.pop()   # O(1)
    def peek(self):
        if not self._data: raise IndexError("Empty stack")
        return self._data[-1]   # O(1)
    def is_empty(self): return len(self._data) == 0

# Classic: Valid Parentheses
def is_valid(s):
    stack, match = [], {')':'(', ']':'[', '}':'{'}
    for c in s:
        if c in "([{": stack.append(c)
        elif not stack or stack[-1] != match[c]: return False
        else: stack.pop()
    return not stack

• 📌 "Level order traversal of a binary tree." → Use a queue. Process each node and enqueue its children. Each level is one BFS iteration.
• 📌 "Implement a queue using two stacks." → Stack1 for enqueue. For dequeue, if Stack2 empty, pop everything from Stack1 into Stack2, then pop Stack2.
• 📌 "Sliding window maximum." → Use a deque (monotonic decreasing). Remove smaller elements as window slides right.

from collections import deque

class Queue:
    def __init__(self): self._q = deque()
    def enqueue(self, val): self._q.append(val)      # O(1)
    def dequeue(self):
        if not self._q: raise IndexError("Empty queue")
        return self._q.popleft()   # O(1)
    def peek(self): return self._q[0] if self._q else None

# BFS skeleton
def bfs(graph, start):
    visited, q = {start}, deque([start])
    while q:
        node = q.popleft()
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor); q.append(neighbor)

• 📌 "Validate a BST." → Pass min/max bounds down recursively: left subtree values must be < node, right must be > node.
• 📌 "Find Lowest Common Ancestor of two nodes in a BST." → If both values < node go left; if both > go right; otherwise current node is LCA.
• 📌 "Convert sorted array to BST." → Recursively pick midpoint as root, left half as left subtree, right half as right subtree. O(n).

class BST:
    class Node:
        def __init__(self,v): self.v=v; self.l=self.r=None

    def __init__(self): self.root=None

    def insert(self, v):
        def _ins(n,v):
            if not n: return self.Node(v)
            if v < n.v: n.l = _ins(n.l,v)
            elif v > n.v: n.r = _ins(n.r,v)
            return n
        self.root = _ins(self.root, v)

    def inorder(self):
        result=[]
        def _io(n):
            if not n: return
            _io(n.l); result.append(n.v); _io(n.r)
        _io(self.root); return result

• 📌 "Find the K largest elements." → Min-heap of size K. For each element, if larger than heap min, replace and heapify down. O(n log k).
• 📌 "Merge K sorted lists." → Push first element of each list into min-heap. Extract min, push next from that list. O(n log k).
• 📌 "Find the median from a data stream." → Two heaps: max-heap for lower half, min-heap for upper half. Balance sizes after each insert.

import heapq

# Min-heap (Python default)
h = []
heapq.heappush(h, 5)   # O(log n)
heapq.heappush(h, 2)
heapq.heappush(h, 8)
minimum = heapq.heappop(h)  # O(log n) → returns 2

# Max-heap: negate values
maxh = []
heapq.heappush(maxh, -5)
heapq.heappush(maxh, -2)
maximum = -heapq.heappop(maxh)  # → 5

# Build heap from list O(n)
nums = [3,1,4,1,5,9,2,6]
heapq.heapify(nums)

# K largest elements
def k_largest(nums, k):
    return heapq.nlargest(k, nums)  # O(n log k)

• 📌 "Two Sum." → Hash map from value → index. For each num, check if target-num is in map. O(n).
• 📌 "Group Anagrams." → Hash map from sorted string → list of originals. O(n·k log k) where k = max word length.
• 📌 "Longest Consecutive Sequence." → Put all nums in a set. For each num that has no num-1 in set, expand right. O(n).

# Python dict is a hash map
ht = {}
ht["name"] = "Alice"   # Insert O(1)
val = ht.get("name")  # Get O(1)
del ht["name"]        # Delete O(1)

# Two Sum — classic hash map problem
def two_sum(nums, target):
    seen = {}
    for i, n in enumerate(nums):
        complement = target - n
        if complement in seen:
            return [seen[complement], i]
        seen[n] = i
    return []   # O(n) time, O(n) space

# Collision handling (chaining concept)
def hash_fn(key, size):
    return sum(ord(c) for c in str(key)) % size

• 📌 "Implement autocomplete." → Insert all words into Trie. For prefix, find the prefix node, then DFS to collect all complete words below it.
• 📌 "Word Search II (find all words in a board)." → Build trie of target words, then DFS on board following trie edges. Prune branches not in trie.
• 📌 "Replace words with root in a sentence." → Build trie of root words. For each sentence word, find shortest prefix in trie and replace.

class TrieNode:
    def __init__(self):
        self.children = {}  # char → TrieNode
        self.is_end = False

class Trie:
    def __init__(self): self.root = TrieNode()

    def insert(self, word):  # O(L)
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_end = True

    def search(self, word):  # O(L)
        node = self.root
        for ch in word:
            if ch not in node.children: return False
            node = node.children[ch]
        return node.is_end

    def starts_with(self, prefix):  # O(P)
        node = self.root
        for ch in prefix:
            if ch not in node.children: return False
            node = node.children[ch]
        return True