Streaming Algorithms

// LC 382 - Linked List Random Node
class Solution {
    private ListNode head;
    private Random random;

    public Solution(ListNode head) {
        this.head = head;
        this.random = new Random();
    }

    /**
     * time = O(N)
     * space = O(1)
     */
    public int getRandom() {
        ListNode cur = head;
        int result = cur.val;
        int count = 1;

        // Process stream: for each element i, include with prob 1/i
        while (cur != null) {
            // Generate random in [0, count-1], replace if 0
            if (random.nextInt(count) == 0) {
                result = cur.val;
            }
            count++;
            cur = cur.next;
        }
        return result;
    }
}

# Python implementation
import random

class Solution:
    def __init__(self, head: ListNode):
        self.head = head

    def getRandom(self) -> int:
        cur = self.head
        result = cur.val
        count = 1

        cur = cur.next
        while cur:
            count += 1
            # Include current element with probability 1/count
            if random.randint(1, count) == count:
                result = cur.val
            cur = cur.next

        return result

// LC 398 - Random Pick Index (variant: pick from array with duplicates)
class Solution {
    private int[] nums;
    private Random random;

    public Solution(int[] nums) {
        this.nums = nums;
        this.random = new Random();
    }

    /**
     * time = O(N)
     * space = O(1)
     */
    public int pick(int target) {
        int result = -1;
        int count = 0;

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                count++;
                // Replace with probability 1/count
                if (random.nextInt(count) == 0) {
                    result = i;
                }
            }
        }
        return result;
    }
}

class ReservoirSampling {
    private int k;
    private int[] reservoir;
    private Random random;
    private int count; // Elements seen so far

    public ReservoirSampling(int k) {
        this.k = k;
        this.reservoir = new int[k];
        this.random = new Random();
        this.count = 0;
    }

    /**
     * time = O(1) per element
     * space = O(k)
     */
    public void add(int val) {
        if (count < k) {
            // Fill reservoir first
            reservoir[count] = val;
        } else {
            // Generate random index in [0, count]
            int j = random.nextInt(count + 1);
            if (j < k) {
                // Replace element in reservoir
                reservoir[j] = val;
            }
        }
        count++;
    }

    public int[] getSample() {
        return Arrays.copyOf(reservoir, Math.min(k, count));
    }
}

# Python k-reservoir sampling
import random

class ReservoirSampling:
    def __init__(self, k: int):
        self.k = k
        self.reservoir = []
        self.count = 0

    def add(self, val: int) -> None:
        """Time: O(1), Space: O(k)"""
        if self.count < self.k:
            self.reservoir.append(val)
        else:
            # Random index in [0, count]
            j = random.randint(0, self.count)
            if j < self.k:
                self.reservoir[j] = val
        self.count += 1

    def get_sample(self) -> list:
        return self.reservoir[:]

// LC 169 - Majority Element
class Solution {
    /**
     * time = O(N)
     * space = O(1)
     */
    public int majorityElement(int[] nums) {
        int candidate = nums[0];
        int count = 1;

        // Phase 1: Find candidate
        for (int i = 1; i < nums.length; i++) {
            if (count == 0) {
                candidate = nums[i];
                count = 1;
            } else if (nums[i] == candidate) {
                count++;
            } else {
                count--; // Cancel out different element
            }
        }

        // Phase 2: Verify (not needed if majority guaranteed)
        // If not guaranteed, count candidate appearances
        return candidate;
    }
}

# Python implementation
def majorityElement(nums: list[int]) -> int:
    """Time: O(n), Space: O(1)"""
    candidate = None
    count = 0

    # Phase 1: Find candidate
    for num in nums:
        if count == 0:
            candidate = num
            count = 1
        elif num == candidate:
            count += 1
        else:
            count -= 1

    return candidate

// LC 229 - Majority Element II (> n/3)
class Solution {
    /**
     * time = O(N)
     * space = O(1)
     */
    public List<Integer> majorityElement(int[] nums) {
        // At most 2 elements can appear > n/3 times
        int candidate1 = 0, candidate2 = 0;
        int count1 = 0, count2 = 0;

        // Phase 1: Find candidates (at most k-1 candidates for n/k)
        for (int num : nums) {
            if (num == candidate1) {
                count1++;
            } else if (num == candidate2) {
                count2++;
            } else if (count1 == 0) {
                candidate1 = num;
                count1 = 1;
            } else if (count2 == 0) {
                candidate2 = num;
                count2 = 1;
            } else {
                // Different from both: cancel out
                count1--;
                count2--;
            }
        }

        // Phase 2: Verify candidates
        count1 = 0;
        count2 = 0;
        for (int num : nums) {
            if (num == candidate1) count1++;
            else if (num == candidate2) count2++;
        }

        List<Integer> result = new ArrayList<>();
        if (count1 > nums.length / 3) result.add(candidate1);
        if (count2 > nums.length / 3) result.add(candidate2);

        return result;
    }
}

# Python - Majority Element II
def majorityElement(nums: list[int]) -> list[int]:
    """Time: O(n), Space: O(1)"""
    # Phase 1: Find up to 2 candidates
    candidate1, candidate2 = None, None
    count1, count2 = 0, 0

    for num in nums:
        if num == candidate1:
            count1 += 1
        elif num == candidate2:
            count2 += 1
        elif count1 == 0:
            candidate1, count1 = num, 1
        elif count2 == 0:
            candidate2, count2 = num, 1
        else:
            count1 -= 1
            count2 -= 1

    # Phase 2: Verify
    result = []
    for candidate in [candidate1, candidate2]:
        if nums.count(candidate) > len(nums) // 3:
            result.append(candidate)

    return result

class BoyerMooreGeneralized {
    /**
     * Find elements appearing > n/k times
     * time = O(N * k)
     * space = O(k)
     */
    public List<Integer> majorityElement(int[] nums, int k) {
        // Can have at most k-1 elements appearing > n/k times
        Map<Integer, Integer> candidates = new HashMap<>();

        // Phase 1: Find candidates
        for (int num : nums) {
            if (candidates.containsKey(num)) {
                candidates.put(num, candidates.get(num) + 1);
            } else if (candidates.size() < k - 1) {
                candidates.put(num, 1);
            } else {
                // Decrement all counts (cancellation)
                List<Integer> toRemove = new ArrayList<>();
                for (Map.Entry<Integer, Integer> entry : candidates.entrySet()) {
                    int count = entry.getValue() - 1;
                    if (count == 0) {
                        toRemove.add(entry.getKey());
                    } else {
                        candidates.put(entry.getKey(), count);
                    }
                }
                for (int key : toRemove) {
                    candidates.remove(key);
                }
            }
        }

        // Phase 2: Verify candidates
        Map<Integer, Integer> counts = new HashMap<>();
        for (int num : nums) {
            if (candidates.containsKey(num)) {
                counts.put(num, counts.getOrDefault(num, 0) + 1);
            }
        }

        List<Integer> result = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            if (entry.getValue() > nums.length / k) {
                result.add(entry.getKey());
            }
        }

        return result;
    }
}

class CountMinSketch {
    private int[][] count; // d × w matrix
    private int d; // Number of hash functions
    private int w; // Width of each row
    private long[] hashA, hashB; // Hash parameters
    private static final long PRIME = 2147483647L; // Large prime

    /**
     * Constructor
     * epsilon: error tolerance (e.g., 0.01 for 1% error)
     * delta: failure probability (e.g., 0.01 for 99% confidence)
     */
    public CountMinSketch(double epsilon, double delta) {
        this.w = (int) Math.ceil(Math.E / epsilon);
        this.d = (int) Math.ceil(Math.log(1.0 / delta));
        this.count = new int[d][w];

        // Initialize hash functions: h(x) = ((a*x + b) % p) % w
        Random random = new Random();
        hashA = new long[d];
        hashB = new long[d];
        for (int i = 0; i < d; i++) {
            hashA[i] = random.nextInt(Integer.MAX_VALUE);
            hashB[i] = random.nextInt(Integer.MAX_VALUE);
        }
    }

    private int hash(int item, int i) {
        // Hash function i
        long hash = ((hashA[i] * item + hashB[i]) % PRIME) % w;
        return (int) hash;
    }

    /**
     * Add item to sketch
     * time = O(d)
     * space = O(1)
     */
    public void add(int item) {
        for (int i = 0; i < d; i++) {
            int index = hash(item, i);
            count[i][index]++;
        }
    }

    /**
     * Estimate frequency of item
     * time = O(d)
     * space = O(1)
     * Returns: estimated count (may overestimate, never underestimate)
     */
    public int estimateCount(int item) {
        int minCount = Integer.MAX_VALUE;
        for (int i = 0; i < d; i++) {
            int index = hash(item, i);
            minCount = Math.min(minCount, count[i][index]);
        }
        return minCount;
    }

    /**
     * Get space usage
     */
    public int getSpace() {
        return d * w; // Number of counters
    }
}

# Python Count-Min Sketch
import math
import random

class CountMinSketch:
    def __init__(self, epsilon: float, delta: float):
        """
        epsilon: error tolerance
        delta: failure probability
        """
        self.w = math.ceil(math.e / epsilon)
        self.d = math.ceil(math.log(1.0 / delta))
        self.count = [[0] * self.w for _ in range(self.d)]

        # Initialize hash parameters
        PRIME = 2147483647
        self.hash_a = [random.randint(1, PRIME-1) for _ in range(self.d)]
        self.hash_b = [random.randint(0, PRIME-1) for _ in range(self.d)]
        self.PRIME = PRIME

    def _hash(self, item: int, i: int) -> int:
        """Hash function i"""
        return ((self.hash_a[i] * item + self.hash_b[i]) % self.PRIME) % self.w

    def add(self, item: int) -> None:
        """Time: O(d), Space: O(1)"""
        for i in range(self.d):
            index = self._hash(item, i)
            self.count[i][index] += 1

    def estimate_count(self, item: int) -> int:
        """Time: O(d), Returns estimated frequency"""
        return min(self.count[i][self._hash(item, i)] for i in range(self.d))

// Track top-k frequent elements in stream
CountMinSketch cms = new CountMinSketch(0.01, 0.01); // 1% error, 99% confidence

// Process stream
for (int item : stream) {
    cms.add(item);
}

// Query frequencies
int freq = cms.estimateCount(42); // Estimated frequency of item 42

class BloomFilter {
    private BitSet bitSet;
    private int m; // Bit array size
    private int k; // Number of hash functions
    private long[] hashSeeds;

    /**
     * Constructor
     * expectedElements: expected number of elements
     * falsePositiveRate: desired false positive probability (e.g., 0.01)
     */
    public BloomFilter(int expectedElements, double falsePositiveRate) {
        // Optimal m: -(n * ln(p)) / (ln(2)^2)
        this.m = (int) Math.ceil(
            -(expectedElements * Math.log(falsePositiveRate)) / Math.pow(Math.log(2), 2)
        );

        // Optimal k: (m/n) * ln(2)
        this.k = (int) Math.ceil((m / (double) expectedElements) * Math.log(2));

        this.bitSet = new BitSet(m);

        // Initialize hash seeds
        Random random = new Random();
        hashSeeds = new long[k];
        for (int i = 0; i < k; i++) {
            hashSeeds[i] = random.nextLong();
        }
    }

    private int hash(String item, int i) {
        long hash = hashSeeds[i];
        for (char c : item.toCharArray()) {
            hash = hash * 31 + c;
        }
        return Math.abs((int) (hash % m));
    }

    /**
     * Add item to filter
     * time = O(k)
     * space = O(1)
     */
    public void add(String item) {
        for (int i = 0; i < k; i++) {
            int index = hash(item, i);
            bitSet.set(index);
        }
    }

    /**
     * Check if item might be in set
     * time = O(k)
     * space = O(1)
     * Returns: true if might exist (possible false positive)
     *          false if definitely not in set (no false negative)
     */
    public boolean mightContain(String item) {
        for (int i = 0; i < k; i++) {
            int index = hash(item, i);
            if (!bitSet.get(index)) {
                return false; // Definitely not in set
            }
        }
        return true; // Might be in set
    }

    /**
     * Get expected false positive rate
     */
    public double getFalsePositiveRate(int insertedElements) {
        return Math.pow(1 - Math.exp(-k * insertedElements / (double) m), k);
    }
}

# Python Bloom Filter
import math
import mmh3  # MurmurHash3 (install: pip install mmh3)
from bitarray import bitarray  # (install: pip install bitarray)

class BloomFilter:
    def __init__(self, expected_elements: int, false_positive_rate: float):
        """
        expected_elements: expected number of items
        false_positive_rate: desired false positive probability
        """
        # Optimal m
        self.m = math.ceil(
            -(expected_elements * math.log(false_positive_rate)) / (math.log(2) ** 2)
        )

        # Optimal k
        self.k = math.ceil((self.m / expected_elements) * math.log(2))

        self.bit_array = bitarray(self.m)
        self.bit_array.setall(0)

    def add(self, item: str) -> None:
        """Time: O(k)"""
        for i in range(self.k):
            index = mmh3.hash(item, i) % self.m
            self.bit_array[index] = 1

    def might_contain(self, item: str) -> bool:
        """Time: O(k), False positives possible, no false negatives"""
        for i in range(self.k):
            index = mmh3.hash(item, i) % self.m
            if not self.bit_array[index]:
                return False  # Definitely not in set
        return True  # Might be in set

// Check if URL has been visited
BloomFilter bf = new BloomFilter(10000, 0.01); // 10k URLs, 1% false positive

// Add URLs
bf.add("https://example.com");
bf.add("https://google.com");

// Query
if (bf.mightContain("https://example.com")) {
    // Might be visited (99% confident)
}

if (!bf.mightContain("https://new-site.com")) {
    // Definitely NOT visited (100% sure)
}

// java
// LC 692 - Top K Frequent Words
// IDEA: count in a map, then stream keys through a size-k "worst-on-top" heap.
//       Comparator inverted vs the ranking so poll() always drops the loser.
class TopKFrequentWords {

    private final Map<String, Integer> freq = new HashMap<>();

    /**
     * time = O(1) amortized per element
     * space = O(D) distinct words
     */
    public void offer(String word) {
        freq.put(word, freq.getOrDefault(word, 0) + 1);
    }

    /**
     * time = O(D log K)
     * space = O(K)
     */
    public List<String> topK(int k) {
        // Worst on top: lower count first; on tie, lexicographically LARGER first
        PriorityQueue<String> pq = new PriorityQueue<>(
            (a, b) -> freq.get(a).equals(freq.get(b))
                    ? b.compareTo(a)
                    : freq.get(a) - freq.get(b));

        for (String w : freq.keySet()) {
            pq.offer(w);
            if (pq.size() > k) {
                pq.poll(); // evict the worst -> heap never exceeds k
            }
        }

        // Heap pops worst-first, so build the answer back to front
        LinkedList<String> res = new LinkedList<>();
        while (!pq.isEmpty()) {
            res.addFirst(pq.poll());
        }
        return res;
    }
}

# python
# LC 692 - Top K Frequent Words
# IDEA: heapq.nsmallest IS a bounded size-k heap internally; the key encodes
#       the mixed sort direction (count descending, word ascending).
import heapq
from collections import Counter

class TopKFrequentWords:
    def __init__(self):
        self.freq = Counter()

    def offer(self, word: str) -> None:
        """time = O(1) amortized, space = O(D) distinct words"""
        self.freq[word] += 1

    def top_k(self, k: int) -> list:
        """time = O(D log K), space = O(K)"""
        return [w for w, c in heapq.nsmallest(
            k, self.freq.items(), key=lambda x: (-x[1], x[0]))]

// java
// LC 703 - Kth Largest Element in a Stream
// IDEA: min-heap capped at k -> root is always the k-th largest so far.
class KthLargest {

    private final PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    private final int k;

    public KthLargest(int k, int[] nums) {
        this.k = k;
        for (int n : nums) add(n);
    }

    /**
     * time = O(log K) per arrival
     * space = O(K)  <- NOT O(N): the stream can be infinite
     */
    public int add(int val) {
        minHeap.offer(val);
        if (minHeap.size() > k) {
            minHeap.poll(); // drop the smallest; only the top k survive
        }
        return minHeap.peek();
    }
}

# python
# LC 703 - Kth Largest Element in a Stream
import heapq

class KthLargest:
    def __init__(self, k: int, nums: list):
        self.k = k
        self.heap = []
        for n in nums:
            self.add(n)

    def add(self, val: int) -> int:
        """time = O(log K) per arrival, space = O(K)"""
        heapq.heappush(self.heap, val)
        if len(self.heap) > self.k:
            heapq.heappop(self.heap)
        return self.heap[0]

nums = [1,3,-1,-3,5,3,6,7], k = 3     (deque holds values, front = max)

i=0 v=1  : [1]                        window not full
i=1 v=3  : 3 dominates 1 -> [3]       window not full
i=2 v=-1 : [3,-1]                     -> max 3
i=3 v=-3 : [3,-1,-3]                  -> max 3
i=4 v=5  : 5 dominates all -> [5]     -> max 5
i=5 v=3  : [5,3]                      -> max 5
i=6 v=6  : 6 dominates -> [6]         -> max 6
i=7 v=7  : 7 dominates -> [7]         -> max 7

// java
// LC 239 - Sliding Window Maximum
// IDEA: deque of INDICES with decreasing values; front = window max.
class Solution {
    /**
     * time = O(N) amortized (each index enters/leaves once)
     * space = O(K)
     */
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] res = new int[n - k + 1];
        Deque<Integer> dq = new ArrayDeque<>(); // indices, values decreasing

        for (int i = 0; i < n; i++) {
            // 1) expire: front index slid out of the window
            if (!dq.isEmpty() && dq.peekFirst() <= i - k) {
                dq.pollFirst();
            }
            // 2) dominate: back values <= nums[i] can never win again
            while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) {
                dq.pollLast();
            }
            dq.offerLast(i);

            // 3) front is the max of the current window
            if (i >= k - 1) {
                res[i - k + 1] = nums[dq.peekFirst()];
            }
        }
        return res;
    }
}

# python
# LC 239 - Sliding Window Maximum
# IDEA: monotonic decreasing deque of indices; dq[0] is the window max.
from collections import deque

def maxSlidingWindow(nums: list, k: int) -> list:
    """time = O(N) amortized, space = O(K)"""
    res, dq = [], deque()  # indices, values decreasing

    for i, v in enumerate(nums):
        if dq and dq[0] <= i - k:          # expire from front
            dq.popleft()
        while dq and nums[dq[-1]] <= v:    # dominate from back
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            res.append(nums[dq[0]])

    return res

// java
// LC 1438 - Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit
// IDEA: two monotonic deques track window max & min; shrink left while max-min > limit.
class Solution {
    /**
     * time = O(N) amortized
     * space = O(N) worst case for the two deques
     */
    public int longestSubarray(int[] nums, int limit) {
        Deque<Integer> maxD = new ArrayDeque<>(); // decreasing
        Deque<Integer> minD = new ArrayDeque<>(); // increasing
        int left = 0, best = 0;

        for (int right = 0; right < nums.length; right++) {
            while (!maxD.isEmpty() && nums[maxD.peekLast()] <= nums[right]) maxD.pollLast();
            maxD.offerLast(right);
            while (!minD.isEmpty() && nums[minD.peekLast()] >= nums[right]) minD.pollLast();
            minD.offerLast(right);

            // constraint broken -> advance left, evicting whichever deque head leaves
            while (nums[maxD.peekFirst()] - nums[minD.peekFirst()] > limit) {
                if (maxD.peekFirst() == left) maxD.pollFirst();
                if (minD.peekFirst() == left) minD.pollFirst();
                left++;
            }
            best = Math.max(best, right - left + 1);
        }
        return best;
    }
}

# python
# LC 1438 - Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit
from collections import deque

def longestSubarray(nums: list, limit: int) -> int:
    """time = O(N) amortized, space = O(N)"""
    max_d, min_d = deque(), deque()
    left = best = 0

    for right, v in enumerate(nums):
        while max_d and nums[max_d[-1]] <= v:
            max_d.pop()
        max_d.append(right)
        while min_d and nums[min_d[-1]] >= v:
            min_d.pop()
        min_d.append(right)

        while nums[max_d[0]] - nums[min_d[0]] > limit:
            if max_d[0] == left:
                max_d.popleft()
            if min_d[0] == left:
                min_d.popleft()
            left += 1

        best = max(best, right - left + 1)

    return best

prices  : 100  80  60  70  60  75  85
stack   :(100,1)
              (80,1)
                  (60,1)
                  ->70 swallows (60,1)   => (70,2)
                        (60,1)
                  ->75 swallows (60,1),(70,2) => (75,4)
             ->85 swallows (75,4),(80,1) => (85,6)
spans   :  1   1   1   2   1   4   6

// java
// LC 901 - Online Stock Span
// IDEA: monotonic decreasing stack of (price, span); a new price absorbs the
//       spans of every entry it dominates -> amortized O(1) per query.
class StockSpanner {

    private final Deque<int[]> stack = new ArrayDeque<>(); // {price, span}

    public StockSpanner() {}

    /**
     * time = O(1) amortized (each price pushed once, popped once)
     * space = O(N) worst case (strictly decreasing stream), O(1) if increasing
     */
    public int next(int price) {
        int span = 1;
        while (!stack.isEmpty() && stack.peek()[0] <= price) {
            span += stack.pop()[1]; // absorb the swallowed entry's span
        }
        stack.push(new int[]{price, span});
        return span;
    }
}

# python
# LC 901 - Online Stock Span
# IDEA: stack of (price, span), decreasing; absorb spans of dominated entries.
class StockSpanner:
    def __init__(self):
        self.stack = []  # (price, span)

    def next(self, price: int) -> int:
        """time = O(1) amortized, space = O(N) worst case"""
        span = 1
        while self.stack and self.stack[-1][0] <= price:
            span += self.stack.pop()[1]
        self.stack.append((price, span))
        return span

// java
// LC 1032 - Stream of Characters
// IDEA: trie of REVERSED words + deque capped at maxLen; walk newest -> oldest.
class StreamChecker {

    static class Node {
        Node[] next = new Node[26];
        boolean isWord = false;
    }

    private final Node root = new Node();
    private final Deque<Character> buf = new ArrayDeque<>();
    private int maxLen = 0;

    /**
     * time = O(total chars in words)
     * space = O(total chars in words)
     */
    public StreamChecker(String[] words) {
        for (String w : words) {
            maxLen = Math.max(maxLen, w.length());
            Node cur = root;
            for (int i = w.length() - 1; i >= 0; i--) { // insert REVERSED
                int c = w.charAt(i) - 'a';
                if (cur.next[c] == null) cur.next[c] = new Node();
                cur = cur.next[c];
            }
            cur.isWord = true;
        }
    }

    /**
     * time = O(maxLen) per char, with early bail-out
     * space = O(maxLen) buffer  <- independent of stream length
     */
    public boolean query(char letter) {
        buf.addFirst(letter);
        if (buf.size() > maxLen) {
            buf.removeLast(); // too old to ever complete a word
        }

        Node cur = root;
        for (char c : buf) { // newest -> oldest
            cur = cur.next[c - 'a'];
            if (cur == null) return false; // no word can match: stop early
            if (cur.isWord) return true;
        }
        return false;
    }
}

# python
# LC 1032 - Stream of Characters
# IDEA: dict-based trie of reversed words + deque capped at max word length.
from collections import deque

class StreamChecker:
    def __init__(self, words: list):
        """time = O(total chars), space = O(total chars)"""
        self.root = {}
        self.max_len = 0
        for w in words:
            self.max_len = max(self.max_len, len(w))
            node = self.root
            for ch in reversed(w):          # insert REVERSED
                node = node.setdefault(ch, {})
            node["$"] = True                # word-end marker
        self.buf = deque()

    def query(self, letter: str) -> bool:
        """time = O(maxLen) per char, space = O(maxLen)"""
        self.buf.appendleft(letter)
        if len(self.buf) > self.max_len:
            self.buf.pop()

        node = self.root
        for ch in self.buf:                 # newest -> oldest
            if ch not in node:
                return False
            node = node[ch]
            if "$" in node:
                return True
        return False

1. Identify constraint: Memory vs Accuracy
   ├─ Exact answer needed? → Reservoir Sampling or Boyer-Moore
   └─ Approximate OK? → Count-Min Sketch or Bloom Filter

2. Determine stream characteristics:
   ├─ Need random samples? → Reservoir Sampling
   ├─ Need heavy hitters? → Boyer-Moore
   ├─ Need frequency estimates? → Count-Min Sketch
   └─ Need membership tests? → Bloom Filter

3. Consider space-time tradeoff:
   ├─ More space → Better accuracy
   └─ Less space → More approximation error

// LC 528 - Random Pick with Weight
class Solution {
    private int[] prefixSum;
    private Random random;

    /**
     * time = O(N) for constructor
     * space = O(N)
     */
    public Solution(int[] w) {
        prefixSum = new int[w.length];
        prefixSum[0] = w[0];
        for (int i = 1; i < w.length; i++) {
            prefixSum[i] = prefixSum[i - 1] + w[i];
        }
        random = new Random();
    }

    /**
     * time = O(log N) using binary search
     * space = O(1)
     */
    public int pickIndex() {
        int target = random.nextInt(prefixSum[prefixSum.length - 1]) + 1;
        // Binary search for target in prefixSum
        int left = 0, right = prefixSum.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (prefixSum[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

// LC 295 - Find Median from Data Stream
class MedianFinder {
    private PriorityQueue<Integer> maxHeap; // Lower half
    private PriorityQueue<Integer> minHeap; // Upper half

    public MedianFinder() {
        maxHeap = new PriorityQueue<>((a, b) -> b - a);
        minHeap = new PriorityQueue<>();
    }

    /**
     * time = O(log N)
     * space = O(N)
     */
    public void addNum(int num) {
        // Add to max heap first
        maxHeap.offer(num);

        // Balance: move largest from max to min
        minHeap.offer(maxHeap.poll());

        // Maintain size property: maxHeap.size >= minHeap.size
        if (maxHeap.size() < minHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }

    /**
     * time = O(1)
     * space = O(1)
     */
    public double findMedian() {
        if (maxHeap.size() > minHeap.size()) {
            return maxHeap.peek();
        }
        return (maxHeap.peek() + minHeap.peek()) / 2.0;
    }
}