Problem patterns

type Pair = [number, number];
 
// opposite ends: indexes of a pair summing to t
function pairSum(xs: number[], t: number): Pair | null {
  let lo = 0;
  let hi = xs.length - 1;
  while (lo < hi) {
    const s = xs[lo] + xs[hi];
    if (s === t) return [lo, hi];
    if (s < t) lo++; // too small: raise the low side
    else hi--; // too big: lower the high side
  }
  return null;
}
 
// same direction: fast reads, slow is the write index
function dedupe(xs: number[]): number {
  let slow = 0;
  for (let fast = 0; fast < xs.length; fast++) {
    if (fast === 0 || xs[fast] !== xs[fast - 1]) {
      xs[slow++] = xs[fast];
    }
  }
  return slow; // xs[0..slow) holds the unique values
}

// opposite ends: indexes of a pair summing to t
function pairSum(xs, t) {
  let lo = 0;
  let hi = xs.length - 1;
  while (lo < hi) {
    const s = xs[lo] + xs[hi];
    if (s === t) return [lo, hi];
    if (s < t)
      lo++; // too small: raise the low side
    else hi--; // too big: lower the high side
  }
  return null;
}
 
// same direction: fast reads, slow is the write index
function dedupe(xs) {
  let slow = 0;
  for (let fast = 0; fast < xs.length; fast++) {
    if (fast === 0 || xs[fast] !== xs[fast - 1]) {
      xs[slow++] = xs[fast];
    }
  }
  return slow; // xs[0..slow) holds the unique values
}

Pair = tuple[int, int]
 
def pair_sum(xs: list[int], t: int) -> Pair | None:
    lo, hi = 0, len(xs) - 1
    while lo < hi:
        s = xs[lo] + xs[hi]
        if s == t:
            return lo, hi
        if s < t:
            lo += 1  # too small: raise the low side
        else:
            hi -= 1  # too big: lower the high side
    return None
 
def dedupe(xs: list[int]) -> int:
    slow = 0
    for fast in range(len(xs)):
        if fast == 0 or xs[fast] != xs[fast - 1]:
            xs[slow] = xs[fast]
            slow += 1
    return slow  # xs[:slow] holds the unique values

// fixed size k (k ≤ n): add the new item, drop the old
function maxSumK(xs: number[], k: number): number {
  let sum = 0;
  for (let i = 0; i < k; i++) sum += xs[i];
  let best = sum;
  for (let r = k; r < xs.length; r++) {
    sum += xs[r] - xs[r - k];
    best = Math.max(best, sum);
  }
  return best;
}
 
// variable: longest substring without repeats
function longestUnique(s: string): number {
  const count = new Map<string, number>();
  let best = 0;
  let l = 0;
  for (let r = 0; r < s.length; r++) {
    const c = s[r];
    count.set(c, (count.get(c) ?? 0) + 1);
    while (count.get(c)! > 1) { // invalid: shrink
      const d = s[l++];
      count.set(d, count.get(d)! - 1);
    }
    best = Math.max(best, r - l + 1); // valid here
  }
  return best;
}

// fixed size k (k ≤ n): add the new item, drop the old
function maxSumK(xs, k) {
  let sum = 0;
  for (let i = 0; i < k; i++) sum += xs[i];
  let best = sum;
  for (let r = k; r < xs.length; r++) {
    sum += xs[r] - xs[r - k];
    best = Math.max(best, sum);
  }
  return best;
}
 
// variable: longest substring without repeats
function longestUnique(s) {
  const count = new Map();
  let best = 0;
  let l = 0;
  for (let r = 0; r < s.length; r++) {
    const c = s[r];
    count.set(c, (count.get(c) ?? 0) + 1);
    while (count.get(c) > 1) {
      // invalid: shrink
      const d = s[l++];
      count.set(d, count.get(d) - 1);
    }
    best = Math.max(best, r - l + 1); // valid here
  }
  return best;
}

from collections import Counter
 
def max_sum_k(xs: list[int], k: int) -> int:
    total = best = sum(xs[:k])
    for r in range(k, len(xs)):
        total += xs[r] - xs[r - k]
        best = max(best, total)
    return best
 
def longest_unique(s: str) -> int:
    count: Counter[str] = Counter()
    best = l = 0
    for r, c in enumerate(s):
        count[c] += 1
        while count[c] > 1:  # invalid: shrink
            count[s[l]] -= 1
            l += 1
        best = max(best, r - l + 1)  # valid here
    return best

// pre[i] = sum of xs[0..i)
function prefix(xs: number[]): number[] {
  const pre = [0];
  for (const x of xs) pre.push(pre.at(-1)! + x);
  return pre;
}
 
// Subarray Sum Equals K: count, negatives allowed
function subarraySum(xs: number[], k: number): number {
  const seen = new Map<number, number>([[0, 1]]);
  let sum = 0;
  let count = 0;
  for (const x of xs) {
    sum += x;
    count += seen.get(sum - k) ?? 0;
    seen.set(sum, (seen.get(sum) ?? 0) + 1);
  }
  return count;
}

// pre[i] = sum of xs[0..i)
function prefix(xs) {
  const pre = [0];
  for (const x of xs) pre.push(pre.at(-1) + x);
  return pre;
}
 
// Subarray Sum Equals K: count, negatives allowed
function subarraySum(xs, k) {
  const seen = new Map([[0, 1]]);
  let sum = 0;
  let count = 0;
  for (const x of xs) {
    sum += x;
    count += seen.get(sum - k) ?? 0;
    seen.set(sum, (seen.get(sum) ?? 0) + 1);
  }
  return count;
}

from collections import Counter
from itertools import accumulate
 
def prefix(xs: list[int]) -> list[int]:
    return list(accumulate(xs, initial=0))
 
def subarray_sum(xs: list[int], k: int) -> int:
    seen = Counter({0: 1})  # the empty prefix
    total = count = 0
    for x in xs:
        total += x
        count += seen[total - k]
        seen[total] += 1
    return count

// Daily Temperatures: days until a warmer day
function dailyTemps(ts: number[]): number[] {
  const ans = new Array<number>(ts.length).fill(0);
  const stack: number[] = []; // indexes, temps falling
  ts.forEach((t, i) => {
    while (stack.length && ts[stack.at(-1)!] < t) {
      const j = stack.pop()!;
      ans[j] = i - j; // i is j's next warmer day
    }
    stack.push(i);
  });
  return ans;
}
 
// Sliding Window Maximum. JS has no deque: an array
// plus a head index gives O(1) pops at both ends
function windowMax(xs: number[], k: number): number[] {
  const dq: number[] = []; // indexes, values falling
  let head = 0; // dq[head..] is the live deque
  const out: number[] = [];
  for (let i = 0; i < xs.length; i++) {
    while (dq.length > head && xs[dq.at(-1)!] <= xs[i]) {
      dq.pop();
    }
    dq.push(i);
    if (dq[head] <= i - k) head++; // left the window
    if (i >= k - 1) out.push(xs[dq[head]]);
  }
  return out;
}

// Daily Temperatures: days until a warmer day
function dailyTemps(ts) {
  const ans = new Array(ts.length).fill(0);
  const stack = []; // indexes, temps falling
  ts.forEach((t, i) => {
    while (stack.length && ts[stack.at(-1)] < t) {
      const j = stack.pop();
      ans[j] = i - j; // i is j's next warmer day
    }
    stack.push(i);
  });
  return ans;
}
 
// Sliding Window Maximum. JS has no deque: an array
// plus a head index gives O(1) pops at both ends
function windowMax(xs, k) {
  const dq = []; // indexes, values falling
  let head = 0; // dq[head..] is the live deque
  const out = [];
  for (let i = 0; i < xs.length; i++) {
    while (dq.length > head && xs[dq.at(-1)] <= xs[i]) {
      dq.pop();
    }
    dq.push(i);
    if (dq[head] <= i - k) head++; // left the window
    if (i >= k - 1) out.push(xs[dq[head]]);
  }
  return out;
}

from collections import deque
 
def daily_temps(ts: list[int]) -> list[int]:
    ans = [0] * len(ts)
    stack: list[int] = []  # indexes, temps falling
    for i, t in enumerate(ts):
        while stack and ts[stack[-1]] < t:
            j = stack.pop()
            ans[j] = i - j  # i is j's next warmer day
        stack.append(i)
    return ans
 
def window_max(xs: list[int], k: int) -> list[int]:
    dq: deque[int] = deque()  # indexes, values falling
    out: list[int] = []
    for i, x in enumerate(xs):
        while dq and xs[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()  # left the window
        if i >= k - 1:
            out.append(xs[dq[0]])
    return out

type ListNode = { val: number; next: Link };
type Link = ListNode | null;
 
function hasCycle(head: Link): boolean {
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}
 
// Floyd: after they meet, restart one at the head;
// stepping both by one, they meet at the cycle start
function cycleStart(head: Link): Link {
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next.next;
    if (slow === fast) {
      let p = head;
      while (p !== slow) {
        p = p!.next;
        slow = slow!.next;
      }
      return p;
    }
  }
  return null;
}
 
// middle node (the second one for even lengths)
function middle(head: ListNode): ListNode {
  let slow = head;
  let fast: Link = head;
  while (fast && fast.next) {
    slow = slow.next!;
    fast = fast.next.next;
  }
  return slow;
}

function hasCycle(head) {
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}
 
// Floyd: after they meet, restart one at the head;
// stepping both by one, they meet at the cycle start
function cycleStart(head) {
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      let p = head;
      while (p !== slow) {
        p = p.next;
        slow = slow.next;
      }
      return p;
    }
  }
  return null;
}
 
// middle node (the second one for even lengths)
function middle(head) {
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
}

from dataclasses import dataclass
 
@dataclass(eq=False)  # compare nodes by identity
class ListNode:
    val: int
    next: "ListNode | None" = None
 
Link = ListNode | None
 
def has_cycle(head: Link) -> bool:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False
 
def cycle_start(head: Link) -> Link:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            p = head
            while p is not slow:
                p, slow = p.next, slow.next
            return p
    return None
 
def middle(head: ListNode) -> ListNode:
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

type Interval = [number, number];
 
function merge(xs: Interval[]): Interval[] {
  const sorted = [...xs].sort((a, b) => a[0] - b[0]);
  const out: Interval[] = [];
  for (const [s, e] of sorted) {
    const last = out.at(-1);
    if (last && s <= last[1]) {
      last[1] = Math.max(last[1], e); // overlap: extend
    } else {
      out.push([s, e]);
    }
  }
  return out;
}
 
// Insert Interval: xs is sorted and non-overlapping
function insert(xs: Interval[], add: Interval): Interval[] {
  const out: Interval[] = [];
  let [s, e] = add;
  let i = 0;
  while (i < xs.length && xs[i][1] < s) out.push(xs[i++]);
  while (i < xs.length && xs[i][0] <= e) { // overlaps
    s = Math.min(s, xs[i][0]);
    e = Math.max(e, xs[i][1]);
    i++;
  }
  return [...out, [s, e], ...xs.slice(i)];
}
 
// Meeting Rooms II: the most meetings at once
function minRooms(xs: Interval[]): number {
  const sorted = [...xs].sort((a, b) => a[0] - b[0]);
  const ends = new MinHeap<number>((a, b) => a - b);
  for (const [s, e] of sorted) {
    // earliest-ending meeting is over: reuse its room
    if (ends.size > 0 && ends.peek()! <= s) ends.pop();
    ends.push(e);
  }
  return ends.size;
}

function merge(xs) {
  const sorted = [...xs].sort((a, b) => a[0] - b[0]);
  const out = [];
  for (const [s, e] of sorted) {
    const last = out.at(-1);
    if (last && s <= last[1]) {
      last[1] = Math.max(last[1], e); // overlap: extend
    } else {
      out.push([s, e]);
    }
  }
  return out;
}
 
// Insert Interval: xs is sorted and non-overlapping
function insert(xs, add) {
  const out = [];
  let [s, e] = add;
  let i = 0;
  while (i < xs.length && xs[i][1] < s) out.push(xs[i++]);
  while (i < xs.length && xs[i][0] <= e) {
    // overlaps
    s = Math.min(s, xs[i][0]);
    e = Math.max(e, xs[i][1]);
    i++;
  }
  return [...out, [s, e], ...xs.slice(i)];
}
 
// Meeting Rooms II: the most meetings at once
function minRooms(xs) {
  const sorted = [...xs].sort((a, b) => a[0] - b[0]);
  const ends = new MinHeap((a, b) => a - b);
  for (const [s, e] of sorted) {
    // earliest-ending meeting is over: reuse its room
    if (ends.size > 0 && ends.peek() <= s) ends.pop();
    ends.push(e);
  }
  return ends.size;
}

import heapq
 
Interval = tuple[int, int]
 
def merge(xs: list[Interval]) -> list[Interval]:
    out: list[Interval] = []
    for s, e in sorted(xs):
        if out and s <= out[-1][1]:  # overlap: extend
            out[-1] = (out[-1][0], max(out[-1][1], e))
        else:
            out.append((s, e))
    return out
 
Intervals = list[Interval]
 
def insert(xs: Intervals, add: Interval) -> Intervals:
    s, e = add
    out: list[Interval] = []
    i = 0
    while i < len(xs) and xs[i][1] < s:
        out.append(xs[i])
        i += 1
    while i < len(xs) and xs[i][0] <= e:  # overlaps
        s, e = min(s, xs[i][0]), max(e, xs[i][1])
        i += 1
    return out + [(s, e)] + xs[i:]
 
def min_rooms(xs: list[Interval]) -> int:
    ends: list[int] = []  # min-heap of end times
    for s, e in sorted(xs):
        # earliest-ending meeting is over: reuse its room
        if ends and ends[0] <= s:
            heapq.heappop(ends)
        heapq.heappush(ends, e)
    return len(ends)

// k largest, largest first
function topK(xs: number[], k: number): number[] {
  const heap = new MinHeap<number>((a, b) => a - b);
  for (const x of xs) {
    heap.push(x);
    if (heap.size > k) heap.pop(); // drop the smallest
  }
  const out: number[] = [];
  while (heap.size > 0) out.push(heap.pop()!);
  return out.reverse();
}
 
// merge k sorted arrays; entry = [value, list, index]
type Entry = [number, number, number];
 
function mergeK(lists: number[][]): number[] {
  const heap = new MinHeap<Entry>((a, b) => a[0] - b[0]);
  lists.forEach((xs, i) => {
    if (xs.length) heap.push([xs[0], i, 0]);
  });
  const out: number[] = [];
  while (heap.size > 0) {
    const [v, i, j] = heap.pop()!;
    out.push(v);
    if (j + 1 < lists[i].length) {
      heap.push([lists[i][j + 1], i, j + 1]);
    }
  }
  return out;
}

// k largest, largest first
function topK(xs, k) {
  const heap = new MinHeap((a, b) => a - b);
  for (const x of xs) {
    heap.push(x);
    if (heap.size > k) heap.pop(); // drop the smallest
  }
  const out = [];
  while (heap.size > 0) out.push(heap.pop());
  return out.reverse();
}
 
// merge k sorted arrays; entry = [value, list, index]
 
function mergeK(lists) {
  const heap = new MinHeap((a, b) => a[0] - b[0]);
  lists.forEach((xs, i) => {
    if (xs.length) heap.push([xs[0], i, 0]);
  });
  const out = [];
  while (heap.size > 0) {
    const [v, i, j] = heap.pop();
    out.push(v);
    if (j + 1 < lists[i].length) {
      heap.push([lists[i][j + 1], i, j + 1]);
    }
  }
  return out;
}

import heapq
 
def top_k(xs: list[int], k: int) -> list[int]:
    heap: list[int] = []
    for x in xs:
        heapq.heappush(heap, x)
        if len(heap) > k:
            heapq.heappop(heap)  # drop the smallest
    return sorted(heap, reverse=True)
    # built in: heapq.nlargest(k, xs)
 
def merge_k(lists: list[list[int]]) -> list[int]:
    heap = [(xs[0], i, 0)
            for i, xs in enumerate(lists) if xs]
    heapq.heapify(heap)
    out: list[int] = []
    while heap:
        v, i, j = heapq.heappop(heap)
        out.append(v)
        if j + 1 < len(lists[i]):
            item = (lists[i][j + 1], i, j + 1)
            heapq.heappush(heap, item)
    return out
    # built in: list(heapq.merge(*lists))

// First Missing Positive (reorders xs in place)
function firstMissingPositive(xs: number[]): number {
  const n = xs.length;
  for (let i = 0; i < n; i++) {
    // swap xs[i] home until it's home or out of range
    while (xs[i] >= 1 && xs[i] <= n
        && xs[xs[i] - 1] !== xs[i]) {
      const j = xs[i] - 1;
      [xs[i], xs[j]] = [xs[j], xs[i]];
    }
  }
  for (let i = 0; i < n; i++) {
    if (xs[i] !== i + 1) return i + 1;
  }
  return n + 1;
}

// First Missing Positive (reorders xs in place)
function firstMissingPositive(xs) {
  const n = xs.length;
  for (let i = 0; i < n; i++) {
    // swap xs[i] home until it's home or out of range
    while (
      xs[i] >= 1 &&
      xs[i] <= n &&
      xs[xs[i] - 1] !== xs[i]
    ) {
      const j = xs[i] - 1;
      [xs[i], xs[j]] = [xs[j], xs[i]];
    }
  }
  for (let i = 0; i < n; i++) {
    if (xs[i] !== i + 1) return i + 1;
  }
  return n + 1;
}

def first_missing_positive(xs: list[int]) -> int:
    n = len(xs)
    for i in range(n):
        # swap xs[i] home until it's home or out of range
        while 1 <= xs[i] <= n and xs[xs[i] - 1] != xs[i]:
            j = xs[i] - 1  # not xs[i], xs[xs[i]-1] = …
            xs[i], xs[j] = xs[j], xs[i]
    for i in range(n):
        if xs[i] != i + 1:
            return i + 1
    return n + 1

// Single Number: every other value appears twice
function single(xs: number[]): number {
  return xs.reduce((acc, x) => acc ^ x, 0);
}
 
// Kernighan: one iteration per set bit; works on the
// 32-bit pattern, so negatives count 32-bit style
function popcount(x: number): number {
  let n = 0;
  for (let v = x; v !== 0; v &= v - 1) n++;
  return n;
}
 
// all subsets via masks 0 .. 2^n - 1 (n ≤ 30 in JS)
function subsets<T>(items: T[]): T[][] {
  const out: T[][] = [];
  for (let m = 0; m < 1 << items.length; m++) {
    out.push(items.filter((_, i) => (m >> i) & 1));
  }
  return out;
}

// Single Number: every other value appears twice
function single(xs) {
  return xs.reduce((acc, x) => acc ^ x, 0);
}
 
// Kernighan: one iteration per set bit; works on the
// 32-bit pattern, so negatives count 32-bit style
function popcount(x) {
  let n = 0;
  for (let v = x; v !== 0; v &= v - 1) n++;
  return n;
}
 
// all subsets via masks 0 .. 2^n - 1 (n ≤ 30 in JS)
function subsets(items) {
  const out = [];
  for (let m = 0; m < 1 << items.length; m++) {
    out.push(items.filter((_, i) => (m >> i) & 1));
  }
  return out;
}

from functools import reduce
from operator import xor
 
def single(xs: list[int]) -> int:
    return reduce(xor, xs, 0)
 
def popcount(x: int) -> int:
    v, n = x & 0xFFFFFFFF, 0  # 32-bit view, like JS
    while v:  # a raw negative int would never hit 0
        v &= v - 1
        n += 1
    return n
    # built in: (x & 0xFFFFFFFF).bit_count()
 
def subsets[T](items: list[T]) -> list[list[T]]:
    n = len(items)
    return [
        [items[i] for i in range(n) if m >> i & 1]
        for m in range(1 << n)
    ]

function minWindow(s: string, t: string): string {
  const need = new Map<string, number>();
  for (const c of t) need.set(c, (need.get(c) ?? 0) + 1);
  let missing = t.length; // chars of t still uncovered
  let bestL = 0;
  let bestLen = s.length + 1;
  let l = 0;
  for (let r = 0; r < s.length; r++) {
    const n = need.get(s[r]) ?? 0;
    if (n > 0) missing--;
    need.set(s[r], n - 1); // negative = surplus
    while (missing === 0) { // valid: record, shrink
      if (r - l + 1 < bestLen) {
        bestL = l;
        bestLen = r - l + 1;
      }
      const m = need.get(s[l])! + 1;
      need.set(s[l++], m);
      if (m > 0) missing++;
    }
  }
  return bestLen > s.length
    ? ""
    : s.slice(bestL, bestL + bestLen);
}

function minWindow(s, t) {
  const need = new Map();
  for (const c of t) need.set(c, (need.get(c) ?? 0) + 1);
  let missing = t.length; // chars of t still uncovered
  let bestL = 0;
  let bestLen = s.length + 1;
  let l = 0;
  for (let r = 0; r < s.length; r++) {
    const n = need.get(s[r]) ?? 0;
    if (n > 0) missing--;
    need.set(s[r], n - 1); // negative = surplus
    while (missing === 0) {
      // valid: record, shrink
      if (r - l + 1 < bestLen) {
        bestL = l;
        bestLen = r - l + 1;
      }
      const m = need.get(s[l]) + 1;
      need.set(s[l++], m);
      if (m > 0) missing++;
    }
  }
  return bestLen > s.length
    ? ""
    : s.slice(bestL, bestL + bestLen);
}

from collections import Counter
 
def min_window(s: str, t: str) -> str:
    need = Counter(t)
    missing = len(t)  # chars of t still uncovered
    best_l, best_len = 0, len(s) + 1
    l = 0
    for r, c in enumerate(s):
        if need[c] > 0:
            missing -= 1
        need[c] -= 1  # negative = surplus
        while missing == 0:  # valid: record, shrink
            if r - l + 1 < best_len:
                best_l, best_len = l, r - l + 1
            need[s[l]] += 1
            if need[s[l]] > 0:
                missing += 1
            l += 1
    if best_len > len(s):
        return ""
    return s[best_l : best_l + best_len]

function charReplacement(s: string, k: number): number {
  const count = new Map<string, number>();
  let maxFreq = 0; // top count seen in any window
  let best = 0;
  let l = 0;
  for (let r = 0; r < s.length; r++) {
    const n = (count.get(s[r]) ?? 0) + 1;
    count.set(s[r], n);
    maxFreq = Math.max(maxFreq, n);
    while (r - l + 1 - maxFreq > k) { // invalid
      count.set(s[l], count.get(s[l])! - 1);
      l++;
    }
    best = Math.max(best, r - l + 1);
  }
  return best;
}

function charReplacement(s, k) {
  const count = new Map();
  let maxFreq = 0; // top count seen in any window
  let best = 0;
  let l = 0;
  for (let r = 0; r < s.length; r++) {
    const n = (count.get(s[r]) ?? 0) + 1;
    count.set(s[r], n);
    maxFreq = Math.max(maxFreq, n);
    while (r - l + 1 - maxFreq > k) {
      // invalid
      count.set(s[l], count.get(s[l]) - 1);
      l++;
    }
    best = Math.max(best, r - l + 1);
  }
  return best;
}

from collections import Counter
 
def char_replacement(s: str, k: int) -> int:
    count: Counter[str] = Counter()
    max_freq = best = l = 0
    for r, c in enumerate(s):
        count[c] += 1
        max_freq = max(max_freq, count[c])
        while r - l + 1 - max_freq > k:  # invalid
            count[s[l]] -= 1
            l += 1
        best = max(best, r - l + 1)
    return best

function threeSum(xs: number[]): number[][] {
  const a = [...xs].sort((x, y) => x - y);
  const out: number[][] = [];
  for (let i = 0; i < a.length - 2; i++) {
    if (a[i] > 0) break; // three positives can't sum to 0
    if (i > 0 && a[i] === a[i - 1]) continue; // dup
    let lo = i + 1;
    let hi = a.length - 1;
    while (lo < hi) {
      const s = a[i] + a[lo] + a[hi];
      if (s < 0) lo++;
      else if (s > 0) hi--;
      else {
        out.push([a[i], a[lo++], a[hi--]]);
        while (lo < hi && a[lo] === a[lo - 1]) lo++;
      }
    }
  }
  return out;
}

function threeSum(xs) {
  const a = [...xs].sort((x, y) => x - y);
  const out = [];
  for (let i = 0; i < a.length - 2; i++) {
    if (a[i] > 0) break; // three positives can't sum to 0
    if (i > 0 && a[i] === a[i - 1]) continue; // dup
    let lo = i + 1;
    let hi = a.length - 1;
    while (lo < hi) {
      const s = a[i] + a[lo] + a[hi];
      if (s < 0) lo++;
      else if (s > 0) hi--;
      else {
        out.push([a[i], a[lo++], a[hi--]]);
        while (lo < hi && a[lo] === a[lo - 1]) lo++;
      }
    }
  }
  return out;
}

def three_sum(xs: list[int]) -> list[list[int]]:
    a = sorted(xs)
    out: list[list[int]] = []
    for i in range(len(a) - 2):
        if a[i] > 0:
            break  # three positives can't sum to 0
        if i > 0 and a[i] == a[i - 1]:
            continue  # dup
        lo, hi = i + 1, len(a) - 1
        while lo < hi:
            s = a[i] + a[lo] + a[hi]
            if s < 0:
                lo += 1
            elif s > 0:
                hi -= 1
            else:
                out.append([a[i], a[lo], a[hi]])
                lo, hi = lo + 1, hi - 1
                while lo < hi and a[lo] == a[lo - 1]:
                    lo += 1
    return out

function productExceptSelf(xs: number[]): number[] {
  const n = xs.length;
  const out = new Array<number>(n).fill(1);
  let pre = 1;
  for (let i = 0; i < n; i++) {
    out[i] = pre; // product of everything left of i
    pre *= xs[i];
  }
  let suf = 1;
  for (let i = n - 1; i >= 0; i--) {
    out[i] *= suf; // times everything right of i
    suf *= xs[i];
  }
  return out;
}

function productExceptSelf(xs) {
  const n = xs.length;
  const out = new Array(n).fill(1);
  let pre = 1;
  for (let i = 0; i < n; i++) {
    out[i] = pre; // product of everything left of i
    pre *= xs[i];
  }
  let suf = 1;
  for (let i = n - 1; i >= 0; i--) {
    out[i] *= suf; // times everything right of i
    suf *= xs[i];
  }
  return out;
}

def product_except_self(xs: list[int]) -> list[int]:
    n = len(xs)
    out = [1] * n
    pre = 1
    for i in range(n):
        out[i] = pre  # product of everything left of i
        pre *= xs[i]
    suf = 1
    for i in range(n - 1, -1, -1):
        out[i] *= suf  # times everything right of i
        suf *= xs[i]
    return out

function topKFrequent(xs: number[], k: number): number[] {
  const freq = new Map<number, number>();
  for (const x of xs) freq.set(x, (freq.get(x) ?? 0) + 1);
  // buckets[f] = values seen exactly f times
  const buckets: number[][] = Array.from(
    { length: xs.length + 1 },
    () => [],
  );
  for (const [x, f] of freq) buckets[f].push(x);
  const out: number[] = [];
  for (let f = xs.length; f > 0 && out.length < k; f--) {
    out.push(...buckets[f]);
  }
  return out.slice(0, k);
}

function topKFrequent(xs, k) {
  const freq = new Map();
  for (const x of xs) freq.set(x, (freq.get(x) ?? 0) + 1);
  // buckets[f] = values seen exactly f times
  const buckets = Array.from(
    { length: xs.length + 1 },
    () => [],
  );
  for (const [x, f] of freq) buckets[f].push(x);
  const out = [];
  for (let f = xs.length; f > 0 && out.length < k; f--) {
    out.push(...buckets[f]);
  }
  return out.slice(0, k);
}

from collections import Counter
 
def top_k_frequent(xs: list[int], k: int) -> list[int]:
    freq = Counter(xs)
    buckets: list[list[int]] = [
        [] for _ in range(len(xs) + 1)
    ]
    for x, f in freq.items():
        buckets[f].append(x)
    out: list[int] = []
    for f in range(len(xs), 0, -1):
        out.extend(buckets[f])
        if len(out) >= k:
            break
    return out[:k]
    # heap version: [x for x, _ in freq.most_common(k)]