Arrays, hashing, lists, stacks & queues

// Two pointers: O(n) time, O(1) extra space
function reverseInPlace<T>(xs: T[]): void {
  for (let i = 0, j = xs.length - 1; i < j; i++, j--)
    [xs[i], xs[j]] = [xs[j], xs[i]];
}
 
// Prefix sums: O(n) to build, then O(1) per range sum
function prefixSums(xs: number[]): number[] {
  const pre = [0];
  for (const x of xs) pre.push(pre[pre.length - 1] + x);
  return pre; // sum of xs[i..j) = pre[j] - pre[i]
}
 
// r × c grid: a new row array for every row
function grid(r: number, c: number): number[][] {
  return Array.from({ length: r }, () =>
    new Array<number>(c).fill(0));
}

// Two pointers: O(n) time, O(1) extra space
function reverseInPlace(xs) {
  for (let i = 0, j = xs.length - 1; i < j; i++, j--)
    [xs[i], xs[j]] = [xs[j], xs[i]];
}
 
// Prefix sums: O(n) to build, then O(1) per range sum
function prefixSums(xs) {
  const pre = [0];
  for (const x of xs) pre.push(pre[pre.length - 1] + x);
  return pre; // sum of xs[i..j) = pre[j] - pre[i]
}
 
// r × c grid: a new row array for every row
function grid(r, c) {
  return Array.from({ length: r }, () =>
    new Array(c).fill(0),
  );
}

# Two pointers: O(n) time, O(1) extra space
def reverse_in_place[T](xs: list[T]) -> None:
    i, j = 0, len(xs) - 1
    while i < j:
        xs[i], xs[j] = xs[j], xs[i]
        i, j = i + 1, j - 1
 
# Prefix sums: O(n) to build, then O(1) per range sum
def prefix_sums(xs: list[int]) -> list[int]:
    pre = [0]
    for x in xs:
        pre.append(pre[-1] + x)
    return pre  # sum of xs[i:j] = pre[j] - pre[i]
 
# r × c grid: a new row list for every row
def grid(r: int, c: int) -> list[list[int]]:
    return [[0] * c for _ in range(r)]

// 26-slot counts: lighter than a Map for a–z input
function letterCounts(s: string): number[] {
  const counts = new Array<number>(26).fill(0);
  for (let i = 0; i < s.length; i++)
    counts[s.charCodeAt(i) - 97]++;
  return counts;
}
 
// Build pieces in an array, join once: O(n)
function runLength(s: string): string {
  const parts: string[] = [];
  for (let i = 0; i < s.length; ) {
    let j = i;
    while (j < s.length && s[j] === s[i]) j++;
    parts.push(`${s[i]}${j - i}`);
    i = j;
  }
  return parts.join("");
}
 
function reverseWords(s: string): string {
  return s.trim().split(/\s+/).reverse().join(" ");
}

// 26-slot counts: lighter than a Map for a–z input
function letterCounts(s) {
  const counts = new Array(26).fill(0);
  for (let i = 0; i < s.length; i++)
    counts[s.charCodeAt(i) - 97]++;
  return counts;
}
 
// Build pieces in an array, join once: O(n)
function runLength(s) {
  const parts = [];
  for (let i = 0; i < s.length;) {
    let j = i;
    while (j < s.length && s[j] === s[i]) j++;
    parts.push(`${s[i]}${j - i}`);
    i = j;
  }
  return parts.join("");
}
 
function reverseWords(s) {
  return s.trim().split(/\s+/).reverse().join(" ");
}

# 26-slot counts: lighter than a dict for a–z input
def letter_counts(s: str) -> list[int]:
    counts = [0] * 26
    for ch in s:
        counts[ord(ch) - ord("a")] += 1
    return counts
 
# Build pieces in a list, join once: O(n)
def run_length(s: str) -> str:
    parts: list[str] = []
    i = 0
    while i < len(s):
        j = i
        while j < len(s) and s[j] == s[i]:
            j += 1
        parts.append(f"{s[i]}{j - i}")
        i = j
    return "".join(parts)
 
def reverse_words(s: str) -> str:
    return " ".join(reversed(s.split()))

// Composite key: encode to a string (or a number)
const key = (r: number, c: number): string => `${r},${c}`;
const seen = new Set<string>();
seen.add(key(1, 2));
const hasCell = seen.has(key(1, 2)); // true
 
// Objects are keys by identity, not by value
const a = [1, 2];
const byRef = new Map<number[], string>([[a, "x"]]);
const same = byRef.get(a);      // "x"
const other = byRef.get([1, 2]); // undefined

// Composite key: encode to a string (or a number)
const key = (r, c) => `${r},${c}`;
const seen = new Set();
seen.add(key(1, 2));
const hasCell = seen.has(key(1, 2)); // true
 
// Objects are keys by identity, not by value
const a = [1, 2];
const byRef = new Map([[a, "x"]]);
const same = byRef.get(a); // "x"
const other = byRef.get([1, 2]); // undefined

from dataclasses import dataclass
 
# Composite key: a tuple hashes by value
seen: set[tuple[int, int]] = set()
seen.add((1, 2))
has_cell = (1, 2) in seen  # True
 
# Mutable containers can't be keys
try:
    bad = {[1, 2]: "x"}
except TypeError as e:
    err = str(e)  # ...unhashable type: 'list'
 
@dataclass(frozen=True)  # adds __eq__ and __hash__
class Cell:
    r: int
    c: int
 
found = {Cell(1, 2): "x"}[Cell(1, 2)]  # "x"

// Counter
function counts<T>(xs: Iterable<T>): Map<T, number> {
  const m = new Map<T, number>();
  for (const x of xs) m.set(x, (m.get(x) ?? 0) + 1);
  return m;
}
 
// defaultdict(list)
function groupBy<T, K>(
  xs: Iterable<T>,
  key: (x: T) => K,
): Map<K, T[]> {
  const m = new Map<K, T[]>();
  for (const x of xs) {
    const k = key(x);
    const group = m.get(k);
    if (group) group.push(x);
    else m.set(k, [x]);
  }
  return m;
}
 
const c = counts("banana"); // a→3, b→1, n→2
const top2 = [...c].sort((p, q) => q[1] - p[1]).slice(0, 2);
const byLen = groupBy(["hi", "yo", "hey"], (w) => w.length);

// Counter
function counts(xs) {
  const m = new Map();
  for (const x of xs) m.set(x, (m.get(x) ?? 0) + 1);
  return m;
}
 
// defaultdict(list)
function groupBy(xs, key) {
  const m = new Map();
  for (const x of xs) {
    const k = key(x);
    const group = m.get(k);
    if (group) group.push(x);
    else m.set(k, [x]);
  }
  return m;
}
 
const c = counts("banana"); // a→3, b→1, n→2
const top2 = [...c].sort((p, q) => q[1] - p[1]).slice(0, 2);
const byLen = groupBy(["hi", "yo", "hey"], (w) => w.length);

from collections import Counter, defaultdict
 
c = Counter("banana")   # a→3, b→1, n→2
top2 = c.most_common(2)  # [("a", 3), ("n", 2)]
missing = c["z"]         # 0, no KeyError
 
by_len: defaultdict[int, list[str]] = defaultdict(list)
for w in ["hi", "yo", "hey"]:
    by_len[len(w)].append(w)

type Link<T> = ListNode<T> | null;
 
class ListNode<T> {
  val: T;
  next: Link<T>;
  constructor(val: T, next: Link<T> = null) {
    this.val = val;
    this.next = next;
  }
}
 
function fromArray<T>(xs: T[]): Link<T> {
  let head: Link<T> = null;
  for (let i = xs.length - 1; i >= 0; i--)
    head = new ListNode(xs[i], head);
  return head;
}
 
function toArray<T>(head: Link<T>): T[] {
  const out: T[] = [];
  for (let n = head; n; n = n.next) out.push(n.val);
  return out;
}
 
// O(n) time, O(1) space: flip every next pointer
function reverse<T>(head: Link<T>): Link<T> {
  let prev: Link<T> = null;
  let cur = head;
  while (cur) {
    const next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
  }
  return prev;
}

class ListNode {
  val;
  next;
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}
 
function fromArray(xs) {
  let head = null;
  for (let i = xs.length - 1; i >= 0; i--)
    head = new ListNode(xs[i], head);
  return head;
}
 
function toArray(head) {
  const out = [];
  for (let n = head; n; n = n.next) out.push(n.val);
  return out;
}
 
// O(n) time, O(1) space: flip every next pointer
function reverse(head) {
  let prev = null;
  let cur = head;
  while (cur) {
    const next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
  }
  return prev;
}

from __future__ import annotations
from dataclasses import dataclass
 
@dataclass
class ListNode[T]:
    val: T
    next: ListNode[T] | None = None
 
type Link[T] = ListNode[T] | None
 
def from_array[T](xs: list[T]) -> Link[T]:
    head: Link[T] = None
    for x in reversed(xs):
        head = ListNode(x, head)
    return head
 
def to_array[T](head: Link[T]) -> list[T]:
    out: list[T] = []
    while head:
        out.append(head.val)
        head = head.next
    return out
 
# O(n) time, O(1) space: flip every next pointer
def reverse[T](head: Link[T]) -> Link[T]:
    prev: Link[T] = None
    cur = head
    while cur:
        nxt = cur.next
        cur.next = prev
        prev, cur = cur, nxt
    return prev

// Merge two sorted lists: O(n + m) time, O(1) space
function merge(
  a: Link<number>,
  b: Link<number>,
): Link<number> {
  const dummy = new ListNode(0);
  let tail = dummy;
  while (a && b) {
    if (a.val <= b.val) {
      tail.next = a;
      a = a.next;
    } else {
      tail.next = b;
      b = b.next;
    }
    tail = tail.next;
  }
  tail.next = a ?? b;
  return dummy.next;
}
 
// Middle node (the second one if the length is even)
function middle<T>(head: ListNode<T>): ListNode<T> {
  let slow = head;
  let fast: Link<T> = head;
  while (fast && fast.next) {
    slow = slow.next!;
    fast = fast.next.next;
  }
  return slow;
}
 
// Floyd's cycle check
function hasCycle<T>(head: Link<T>): 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;
}

// Merge two sorted lists: O(n + m) time, O(1) space
function merge(a, b) {
  const dummy = new ListNode(0);
  let tail = dummy;
  while (a && b) {
    if (a.val <= b.val) {
      tail.next = a;
      a = a.next;
    } else {
      tail.next = b;
      b = b.next;
    }
    tail = tail.next;
  }
  tail.next = a ?? b;
  return dummy.next;
}
 
// Middle node (the second one if the length is even)
function middle(head) {
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
}
 
// Floyd's cycle check
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;
}

# Merge two sorted lists: O(n + m) time, O(1) space
def merge(a: Link[int], b: Link[int]) -> Link[int]:
    dummy = ListNode(0)
    tail = dummy
    while a and b:
        if a.val <= b.val:
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
    tail.next = a or b
    return dummy.next
 
# Middle node (the second one if the length is even)
def middle[T](head: ListNode[T]) -> ListNode[T]:
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow
 
# Floyd's cycle check
def has_cycle[T](head: Link[T]) -> bool:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next if slow else None
        fast = fast.next.next
        if slow is fast:
            return True
    return False

// Stack with O(1) min: store the running minimum too
class MinStack {
  private items: number[] = [];
  private mins: number[] = []; // mins[i] = min(items[..i])
 
  push(x: number): void {
    this.items.push(x);
    const m = this.mins.at(-1);
    this.mins.push(m === undefined ? x : Math.min(m, x));
  }
 
  pop(): number | undefined {
    this.mins.pop();
    return this.items.pop();
  }
 
  top(): number | undefined {
    return this.items.at(-1);
  }
 
  min(): number | undefined {
    return this.mins.at(-1);
  }
}

// Stack with O(1) min: store the running minimum too
class MinStack {
  #items = [];
  #mins = []; // mins[i] = min(items[..i])
 
  push(x) {
    this.#items.push(x);
    const m = this.#mins.at(-1);
    this.#mins.push(m === undefined ? x : Math.min(m, x));
  }
 
  pop() {
    this.#mins.pop();
    return this.#items.pop();
  }
 
  top() {
    return this.#items.at(-1);
  }
 
  min() {
    return this.#mins.at(-1);
  }
}

# Stack with O(1) min: store the running minimum too
class MinStack:
    def __init__(self) -> None:
        self.items: list[int] = []
        self.mins: list[int] = []  # running minimums
 
    def push(self, x: int) -> None:
        self.items.append(x)
        m = self.mins[-1] if self.mins else x
        self.mins.append(min(m, x))
 
    def pop(self) -> int | None:
        if not self.items:
            return None
        self.mins.pop()
        return self.items.pop()
 
    def top(self) -> int | None:
        return self.items[-1] if self.items else None
 
    def min(self) -> int | None:
        return self.mins[-1] if self.mins else None

export class Deque<T> {
  private buf: (T | undefined)[];
  private head = 0; // index of the front item
  private size = 0;
 
  constructor(capacity = 16) {
    this.buf = new Array<T | undefined>(capacity);
  }
 
  get length(): number {
    return this.size;
  }
 
  // physical slot of logical index i
  private slot(i: number): number {
    return (this.head + i) % this.buf.length;
  }
 
  get(i: number): T | undefined {
    return i >= 0 && i < this.size
      ? this.buf[this.slot(i)]
      : undefined;
  }
 
  pushBack(x: T): void {
    if (this.size === this.buf.length) this.grow();
    this.buf[this.slot(this.size)] = x;
    this.size++;
  }
 
  pushFront(x: T): void {
    if (this.size === this.buf.length) this.grow();
    this.head = this.slot(this.buf.length - 1);
    this.buf[this.head] = x;
    this.size++;
  }
 
  popFront(): T | undefined {
    if (this.size === 0) return undefined;
    const x = this.buf[this.head];
    this.buf[this.head] = undefined; // allow GC
    this.head = this.slot(1);
    this.size--;
    return x;
  }
 
  popBack(): T | undefined {
    if (this.size === 0) return undefined;
    const i = this.slot(this.size - 1);
    const x = this.buf[i];
    this.buf[i] = undefined;
    this.size--;
    return x;
  }
 
  peekFront(): T | undefined {
    return this.get(0);
  }
 
  peekBack(): T | undefined {
    return this.get(this.size - 1);
  }
 
  private grow(): void {
    const next = new Array<T | undefined>(
      Math.max(1, this.buf.length * 2));
    for (let i = 0; i < this.size; i++)
      next[i] = this.buf[this.slot(i)];
    this.buf = next;
    this.head = 0;
  }
}

export class Deque {
  #buf;
  #head = 0; // index of the front item
  #size = 0;
 
  constructor(capacity = 16) {
    this.#buf = new Array(capacity);
  }
 
  get length() {
    return this.#size;
  }
 
  // physical slot of logical index i
  #slot(i) {
    return (this.#head + i) % this.#buf.length;
  }
 
  get(i) {
    return i >= 0 && i < this.#size
      ? this.#buf[this.#slot(i)]
      : undefined;
  }
 
  pushBack(x) {
    if (this.#size === this.#buf.length) this.#grow();
    this.#buf[this.#slot(this.#size)] = x;
    this.#size++;
  }
 
  pushFront(x) {
    if (this.#size === this.#buf.length) this.#grow();
    this.#head = this.#slot(this.#buf.length - 1);
    this.#buf[this.#head] = x;
    this.#size++;
  }
 
  popFront() {
    if (this.#size === 0) return undefined;
    const x = this.#buf[this.#head];
    this.#buf[this.#head] = undefined; // allow GC
    this.#head = this.#slot(1);
    this.#size--;
    return x;
  }
 
  popBack() {
    if (this.#size === 0) return undefined;
    const i = this.#slot(this.#size - 1);
    const x = this.#buf[i];
    this.#buf[i] = undefined;
    this.#size--;
    return x;
  }
 
  peekFront() {
    return this.get(0);
  }
 
  peekBack() {
    return this.get(this.#size - 1);
  }
 
  #grow() {
    const next = new Array(
      Math.max(1, this.#buf.length * 2),
    );
    for (let i = 0; i < this.#size; i++)
      next[i] = this.#buf[this.#slot(i)];
    this.#buf = next;
    this.#head = 0;
  }
}

from collections import deque
 
# Built in: same operations, all O(1) at the ends
d: deque[int] = deque()
d.append(1)       # pushBack
d.appendleft(0)   # pushFront
d.append(2)       # d = deque([0, 1, 2])
front = d[0]      # peekFront → 0
back = d[-1]      # peekBack → 2
first = d.popleft()  # popFront → 0
last = d.pop()       # popBack → 2
 
# Bounded: old items fall off the other end
recent: deque[int] = deque(maxlen=3)
for x in range(5):
    recent.append(x)  # ends as deque([2, 3, 4])

class LRUCache<K, V> {
  private readonly map = new Map<K, V>();
  private readonly capacity: number;
 
  constructor(capacity: number) {
    this.capacity = capacity;
  }
 
  get(key: K): V | undefined {
    if (!this.map.has(key)) return undefined;
    const v = this.map.get(key)!;
    this.map.delete(key); // re-insert as most recent
    this.map.set(key, v);
    return v;
  }
 
  put(key: K, value: V): void {
    this.map.delete(key);
    this.map.set(key, value);
    if (this.map.size > this.capacity) {
      // first key in iteration order = least recent
      const oldest = this.map.keys().next().value!;
      this.map.delete(oldest);
    }
  }
}

class LRUCache {
  #map = new Map();
  #capacity;
 
  constructor(capacity) {
    this.#capacity = capacity;
  }
 
  get(key) {
    if (!this.#map.has(key)) return undefined;
    const v = this.#map.get(key);
    this.#map.delete(key); // re-insert as most recent
    this.#map.set(key, v);
    return v;
  }
 
  put(key, value) {
    this.#map.delete(key);
    this.#map.set(key, value);
    if (this.#map.size > this.#capacity) {
      // first key in iteration order = least recent
      const oldest = this.#map.keys().next().value;
      this.#map.delete(oldest);
    }
  }
}

from collections import OrderedDict
 
class LRUCache[K, V]:
    def __init__(self, capacity: int) -> None:
        self.capacity = capacity
        self.map: OrderedDict[K, V] = OrderedDict()
 
    def get(self, key: K) -> V | None:
        if key not in self.map:
            return None
        self.map.move_to_end(key)  # most recent
        return self.map[key]
 
    def put(self, key: K, value: V) -> None:
        self.map[key] = value
        self.map.move_to_end(key)
        if len(self.map) > self.capacity:
            self.map.popitem(last=False)  # least recent

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

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

from collections import Counter
 
def top_k_frequent(xs: list[int], k: int) -> list[int]:
    count = Counter(xs)
    # bucket[f] = values seen exactly f times
    n = len(xs)
    bucket: list[list[int]] = [[] for _ in range(n + 1)]
    for x, f in count.items():
        bucket[f].append(x)
    out: list[int] = []
    for f in range(n, 0, -1):
        out.extend(bucket[f])
        if len(out) >= k:
            break
    return out[:k]
    # O(n log k): [x for x, _ in count.most_common(k)]

const OPEN = new Map([
  [")", "("],
  ["]", "["],
  ["}", "{"],
]);
 
function isBalanced(s: string): boolean {
  const stack: string[] = [];
  for (const ch of s) {
    if ("([{".includes(ch)) stack.push(ch);
    else if (OPEN.has(ch) && stack.pop() !== OPEN.get(ch))
      return false;
  }
  return stack.length === 0;
}

const OPEN = new Map([
  [")", "("],
  ["]", "["],
  ["}", "{"],
]);
 
function isBalanced(s) {
  const stack = [];
  for (const ch of s) {
    if ("([{".includes(ch)) stack.push(ch);
    else if (OPEN.has(ch) && stack.pop() !== OPEN.get(ch))
      return false;
  }
  return stack.length === 0;
}

OPEN = {")": "(", "]": "[", "}": "{"}
 
def is_balanced(s: str) -> bool:
    stack: list[str] = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        elif ch in OPEN:
            if not stack or stack.pop() != OPEN[ch]:
                return False
    return not stack

function groupAnagrams(words: string[]): string[][] {
  const groups = new Map<string, string[]>();
  for (const w of words) {
    const key = [...w].sort().join(""); // canonical form
    const g = groups.get(key);
    if (g) g.push(w);
    else groups.set(key, [w]);
  }
  return [...groups.values()];
}

function groupAnagrams(words) {
  const groups = new Map();
  for (const w of words) {
    const key = [...w].sort().join(""); // canonical form
    const g = groups.get(key);
    if (g) g.push(w);
    else groups.set(key, [w]);
  }
  return [...groups.values()];
}

from collections import defaultdict
 
def group_anagrams(words: list[str]) -> list[list[str]]:
    groups: defaultdict[str, list[str]] = defaultdict(list)
    for w in words:
        groups["".join(sorted(w))].append(w)  # canonical
    return list(groups.values())

class TwoStackQueue<T> {
  private inbox: T[] = [];
  private outbox: T[] = [];
 
  push(x: T): void {
    this.inbox.push(x);
  }
 
  pop(): T | undefined {
    if (this.outbox.length === 0) {
      while (this.inbox.length > 0)
        this.outbox.push(this.inbox.pop()!);
    }
    return this.outbox.pop();
  }
 
  get length(): number {
    return this.inbox.length + this.outbox.length;
  }
}

class TwoStackQueue {
  #inbox = [];
  #outbox = [];
 
  push(x) {
    this.#inbox.push(x);
  }
 
  pop() {
    if (this.#outbox.length === 0) {
      while (this.#inbox.length > 0)
        this.#outbox.push(this.#inbox.pop());
    }
    return this.#outbox.pop();
  }
 
  get length() {
    return this.#inbox.length + this.#outbox.length;
  }
}

class TwoStackQueue[T]:
    def __init__(self) -> None:
        self.inbox: list[T] = []
        self.outbox: list[T] = []
 
    def push(self, x: T) -> None:
        self.inbox.append(x)
 
    def pop(self) -> T | None:
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())
        return self.outbox.pop() if self.outbox else None
 
    def __len__(self) -> int:
        return len(self.inbox) + len(self.outbox)