11 — Advanced Algorithms & The Gaps#

def merge_sort(nums):
    if len(nums) <= 1:
        return nums
    mid = len(nums) // 2
    left = merge_sort(nums[:mid])
    right = merge_sort(nums[mid:])
    return merge(left, right)
 
def merge(a, b):
    out = []
    i = j = 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:        # <= (not <) is what makes it STABLE
            out.append(a[i]); i += 1
        else:
            out.append(b[j]); j += 1
    out.extend(a[i:])
    out.extend(b[j:])
    return out

def count_inversions(nums):
    def sort_count(a):
        if len(a) <= 1: return a, 0
        mid = len(a) // 2
        left, x = sort_count(a[:mid])
        right, y = sort_count(a[mid:])
        merged, z = merge_count(left, right)
        return merged, x + y + z
 
    def merge_count(a, b):
        out, inv, i, j = [], 0, 0, 0
        while i < len(a) and j < len(b):
            if a[i] <= b[j]:
                out.append(a[i]); i += 1
            else:
                out.append(b[j]); j += 1
                inv += len(a) - i      # a[i:] are ALL greater than b[j]
        out.extend(a[i:]); out.extend(b[j:])
        return out, inv
 
    return sort_count(nums)[1]
# O(n log n) — the brute force is O(n²)

import random
 
def quicksort(nums, lo=0, hi=None):
    if hi is None: hi = len(nums) - 1
    if lo >= hi: return
    p = partition(nums, lo, hi)
    quicksort(nums, lo, p - 1)
    quicksort(nums, p + 1, hi)
 
def partition(nums, lo, hi):
    # random pivot avoids the O(n²) worst case on sorted input
    r = random.randint(lo, hi)
    nums[r], nums[hi] = nums[hi], nums[r]
    pivot = nums[hi]
    i = lo                                  # boundary: everything < i is <= pivot
    for j in range(lo, hi):
        if nums[j] <= pivot:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
    nums[i], nums[hi] = nums[hi], nums[i]   # put the pivot in its final place
    return i

def heapsort(nums):
    def sift_down(a, start, end):
        root = start
        while 2 * root + 1 <= end:
            child = 2 * root + 1
            if child + 1 <= end and a[child] < a[child + 1]:
                child += 1
            if a[root] < a[child]:
                a[root], a[child] = a[child], a[root]
                root = child
            else:
                return
    n = len(nums)
    for start in range(n // 2 - 1, -1, -1):    # build a max-heap, O(n)
        sift_down(nums, start, n - 1)
    for end in range(n - 1, 0, -1):
        nums[0], nums[end] = nums[end], nums[0]  # move max to the end
        sift_down(nums, 0, end - 1)
    return nums

import random
 
def quickselect(nums, k):
    """k-th SMALLEST (1-indexed). For k-th largest: quickselect(nums, len(nums)-k+1)"""
    lo, hi = 0, len(nums) - 1
    target = k - 1                       # convert to 0-indexed
    while True:
        if lo == hi:
            return nums[lo]
        p = partition(nums, lo, hi)      # same partition as quicksort
        if p == target:
            return nums[p]
        elif p < target:
            lo = p + 1                   # answer is in the right half only
        else:
            hi = p - 1

# Counting sort — O(n + k) for integers in a small known range [0, k]
def counting_sort(nums, k):
    count = [0] * (k + 1)
    for x in nums:
        count[x] += 1
    out = []
    for v, c in enumerate(count):
        out.extend([v] * c)
    return out
 
# Bucket sort — distribute into buckets by value, sort each
# Used in Top K Frequent Elements: bucket index = frequency → O(n) overall
def top_k_frequent(nums, k):
    from collections import Counter
    freq = Counter(nums)
    buckets = [[] for _ in range(len(nums) + 1)]
    for num, count in freq.items():
        buckets[count].append(num)          # index BY frequency
    out = []
    for count in range(len(buckets) - 1, 0, -1):
        for num in buckets[count]:
            out.append(num)
            if len(out) == k: return out

def rabin_karp(text, pattern):
    n, m = len(text), len(pattern)
    if m > n: return -1
    BASE, MOD = 256, 10**9 + 7
 
    pattern_hash = 0
    window_hash = 0
    high = pow(BASE, m - 1, MOD)          # BASE^(m-1), for removing the front char
 
    for i in range(m):
        pattern_hash = (pattern_hash * BASE + ord(pattern[i])) % MOD
        window_hash  = (window_hash  * BASE + ord(text[i]))    % MOD
 
    for i in range(n - m + 1):
        if window_hash == pattern_hash:
            if text[i:i+m] == pattern:     # verify — hashes can collide
                return i
        if i < n - m:
            # roll: drop text[i], add text[i+m]
            window_hash = ((window_hash - ord(text[i]) * high) * BASE
                           + ord(text[i+m])) % MOD
    return -1
# O(n + m) average, O(n*m) worst (all collisions)

def build_lps(pattern):
    """lps[i] = length of the longest proper prefix of pattern[:i+1]
       that is also a suffix of it."""
    lps = [0] * len(pattern)
    length = 0
    i = 1
    while i < len(pattern):
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        elif length:
            length = lps[length - 1]    # fall back — don't restart at 0
        else:
            lps[i] = 0
            i += 1
    return lps
 
def kmp_search(text, pattern):
    if not pattern: return 0
    lps = build_lps(pattern)
    i = j = 0
    while i < len(text):
        if text[i] == pattern[j]:
            i += 1; j += 1
            if j == len(pattern):
                return i - j
        elif j:
            j = lps[j - 1]              # skip ahead using the prefix table
        else:
            i += 1
    return -1

# Partition to K Equal Sum Subsets
def can_partition_k_subsets(nums, k):
    total = sum(nums)
    if total % k: return False
    target = total // k
    nums.sort(reverse=True)              # big items first prunes hard
    if nums[0] > target: return False
    n = len(nums)
 
    from functools import cache
    @cache
    def dfs(mask, current_sum):
        if mask == (1 << n) - 1:         # every item used
            return True
        for i in range(n):
            if mask & (1 << i):          # already used
                continue
            if current_sum + nums[i] > target:
                continue                  # prune
            new_sum = (current_sum + nums[i]) % target   # roll over to next bucket
            if dfs(mask | (1 << i), new_sum):
                return True
        return False
    return dfs(0, 0)
# O(2^n * n) states

# Traveling Salesman (held-karp) — the canonical bitmask DP
def tsp(dist):
    n = len(dist)
    from functools import cache
    @cache
    def dp(mask, city):
        """min cost to have visited `mask`, currently standing at `city`"""
        if mask == (1 << n) - 1:
            return dist[city][0]                  # return home
        best = float('inf')
        for nxt in range(n):
            if mask & (1 << nxt): continue
            best = min(best, dist[city][nxt] + dp(mask | (1 << nxt), nxt))
        return best
    return dp(1, 0)
# O(2^n * n²) — feasible to about n = 20

def bellman_ford(n, edges, src):
    dist = [float('inf')] * n
    dist[src] = 0
    for _ in range(n - 1):              # n-1 relaxation rounds suffice
        changed = False
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True
        if not changed: break            # early exit
    # one more pass: if anything still improves, a negative cycle exists
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return None                  # negative cycle
    return dist
# O(V * E)

def find_cheapest_price(n, flights, src, dst, k):
    dist = [float('inf')] * n
    dist[src] = 0
    for _ in range(k + 1):
        tmp = dist[:]                    # snapshot — this line is the whole trick
        for u, v, w in flights:
            if dist[u] + w < tmp[v]:
                tmp[v] = dist[u] + w
        dist = tmp
    return dist[dst] if dist[dst] != float('inf') else -1

def floyd_warshall(n, edges):
    dist = [[float('inf')] * n for _ in range(n)]
    for i in range(n): dist[i][i] = 0
    for u, v, w in edges: dist[u][v] = w
    for k in range(n):                   # k = intermediate node, OUTERMOST loop
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist
# O(V³) — fine for V ≤ 400 or so

def find_itinerary(tickets):
    from collections import defaultdict
    graph = defaultdict(list)
    for src, dst in sorted(tickets, reverse=True):
        graph[src].append(dst)            # reverse sort so pop() gives smallest
 
    route = []
    stack = ["JFK"]
    while stack:
        while graph[stack[-1]]:
            stack.append(graph[stack[-1]].pop())
        route.append(stack.pop())         # dead end → add to route
    return route[::-1]

def critical_connections(n, connections):
    from collections import defaultdict
    graph = defaultdict(list)
    for u, v in connections:
        graph[u].append(v); graph[v].append(u)
 
    disc = [-1] * n          # discovery time
    low  = [0] * n           # lowest discovery time reachable
    bridges = []
    timer = [0]
 
    def dfs(node, parent):
        disc[node] = low[node] = timer[0]
        timer[0] += 1
        for nei in graph[node]:
            if nei == parent: continue
            if disc[nei] == -1:
                dfs(nei, node)
                low[node] = min(low[node], low[nei])
                if low[nei] > disc[node]:
                    bridges.append([node, nei])   # no back edge around it
            else:
                low[node] = min(low[node], disc[nei])
    dfs(0, -1)
    return bridges
# O(V + E)

from collections import deque
def is_bipartite(graph):
    color = {}
    for start in range(len(graph)):
        if start in color: continue
        color[start] = 0
        q = deque([start])
        while q:
            node = q.popleft()
            for nei in graph[node]:
                if nei not in color:
                    color[nei] = 1 - color[node]
                    q.append(nei)
                elif color[nei] == color[node]:
                    return False           # odd cycle → not bipartite
    return True

class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)         # 1-indexed
 
    def update(self, i, delta):           # add delta at index i (0-indexed input)
        i += 1
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)                 # move to the next responsible node
 
    def query(self, i):                   # prefix sum of [0..i]
        i += 1
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)                 # strip the lowest set bit
        return s
 
    def range_query(self, l, r):
        return self.query(r) - (self.query(l - 1) if l else 0)
# update and query both O(log n)

class SegmentTree:
    def __init__(self, nums):
        self.n = len(nums)
        self.tree = [0] * (2 * self.n)
        for i, x in enumerate(nums):
            self.tree[self.n + i] = x           # leaves
        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.tree[2*i] + self.tree[2*i + 1]   # internal nodes
 
    def update(self, i, val):
        i += self.n
        self.tree[i] = val
        while i > 1:
            i //= 2
            self.tree[i] = self.tree[2*i] + self.tree[2*i + 1]
 
    def query(self, l, r):                       # sum of [l, r)
        l += self.n; r += self.n
        s = 0
        while l < r:
            if l & 1: s += self.tree[l]; l += 1
            if r & 1: r -= 1; s += self.tree[r]
            l //= 2; r //= 2
        return s

def mat_mult(A, B, mod):
    n = len(A)
    return [[sum(A[i][k] * B[k][j] for k in range(n)) % mod
             for j in range(n)] for i in range(n)]
 
def mat_pow(M, p, mod):
    n = len(M)
    result = [[int(i == j) for j in range(n)] for i in range(n)]   # identity
    while p:
        if p & 1: result = mat_mult(result, M, mod)
        M = mat_mult(M, M, mod)
        p >>= 1
    return result

# Predict the Winner / Stone Game
def predict_the_winner(nums):
    from functools import cache
    @cache
    def dp(i, j):
        """max score difference (current player minus opponent) for nums[i..j]"""
        if i == j: return nums[i]
        take_left  = nums[i] - dp(i + 1, j)      # opponent then plays optimally
        take_right = nums[j] - dp(i, j - 1)
        return max(take_left, take_right)
    return dp(0, len(nums) - 1) >= 0

# Nim Game — sometimes the answer is pure math
def can_win_nim(n):
    return n % 4 != 0        # you lose iff n is a multiple of 4

# Reservoir sampling — pick k uniformly at random from a stream of unknown length
import random
def reservoir_sample(stream, k):
    reservoir = []
    for i, x in enumerate(stream):
        if i < k:
            reservoir.append(x)
        else:
            j = random.randint(0, i)      # replace with probability k/(i+1)
            if j < k:
                reservoir[j] = x
    return reservoir

# Fisher-Yates shuffle — uniform random permutation in O(n)
def shuffle(nums):
    for i in range(len(nums) - 1, 0, -1):
        j = random.randint(0, i)          # must include i
        nums[i], nums[j] = nums[j], nums[i]
    return nums

# Weighted random pick — prefix sums + binary search
import bisect
class WeightedRandom:
    def __init__(self, w):
        self.prefix = []
        total = 0
        for x in w:
            total += x
            self.prefix.append(total)
        self.total = total
    def pick(self):
        target = random.uniform(0, self.total)
        return bisect.bisect_left(self.prefix, target)

# Distance — avoid sqrt when only comparing
def dist_sq(a, b): return (a[0]-b[0])**2 + (a[1]-b[1])**2
 
# Cross product — sign gives orientation.
# > 0 counter-clockwise, < 0 clockwise, == 0 collinear
def cross(o, a, b):
    return (a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0])
 
# Convex hull (Andrew's monotone chain) — O(n log n)
def convex_hull(points):
    points = sorted(set(points))
    if len(points) <= 2: return points
    def build(pts):
        hull = []
        for p in pts:
            while len(hull) >= 2 and cross(hull[-2], hull[-1], p) <= 0:
                hull.pop()
            hull.append(p)
        return hull
    lower = build(points)
    upper = build(reversed(points))
    return lower[:-1] + upper[:-1]
 
# Rectangle overlap
def overlaps(r1, r2):
    return not (r1[2] <= r2[0] or r2[2] <= r1[0] or
                r1[3] <= r2[1] or r2[3] <= r1[1])

# Insert Delete GetRandom O(1) — array + index map
import random
class RandomizedSet:
    def __init__(self):
        self.vals = []
        self.idx = {}                     # value -> position in vals
 
    def insert(self, val):
        if val in self.idx: return False
        self.idx[val] = len(self.vals)
        self.vals.append(val)
        return True
 
    def remove(self, val):
        if val not in self.idx: return False
        i = self.idx[val]
        last = self.vals[-1]
        self.vals[i] = last               # move the last element into the hole
        self.idx[last] = i
        self.vals.pop()
        del self.idx[val]
        return True
 
    def getRandom(self):
        return random.choice(self.vals)