Math & Geometry

def convert_to_title(column_number: int) -> str:
    """LC 168. Excel Sheet Column Title.

    Base-26 conversion with no zero digit: the digits run 1..26 (A..Z)
    instead of 0..25, so plain mod/divide breaks on multiples of 26.
    WHY the decrement: subtracting 1 before each mod-and-divide step
    shifts the digit range down to 0..25, so 26 maps cleanly to 'Z'
    and 27 to "AA" instead of rolling over wrong. Letters come out
    least significant first, so reverse at the end. O(log n) time and
    space.
    """
    letters = []
    while column_number:
        column_number -= 1  # 1-offset: shift digits 1..26 down to 0..25
        letters.append(chr(ord("A") + column_number % 26))
        column_number //= 26
    return "".join(reversed(letters))

// LC 168. Excel columns are base 26 with digits 1..26 instead of 0..25, so
// plain mod/divide is off by one. Decrement BEFORE each mod and divide to
// shift the digits down to 0..25, emit letters low digit first, and reverse
// at the end. O(log n) time.
string convertToTitle(int columnNumber) {
    string title;
    while (columnNumber > 0) {
        --columnNumber;  // shift this digit from 1..26 down to 0..25
        title.push_back(static_cast<char>('A' + columnNumber % 26));
        columnNumber /= 26;
    }
    reverse(title.begin(), title.end());
    return title;
}

/// LC 168. Base 26 with digits 1..=26 instead of 0..=25: DECREMENT before
/// each mod and divide so 26 reads as 'Z' rather than rolling into "A0".
/// Letters fall out least significant first, so build then reverse.
pub fn convert_to_title(column_number: i32) -> String {
    let mut n = column_number;
    let mut letters = Vec::new();
    while n > 0 {
        n -= 1; // 1-based digit: shift into 0..=25 before mod/divide
        letters.push(b'A' + (n % 26) as u8);
        n /= 26;
    }
    letters.reverse();
    String::from_utf8(letters).unwrap()
}

/** LC 168. Base 26 with digits 1..26, not 0..25: DECREMENT before each mod/divide, prepend the letter. */
export function convertToTitle(columnNumber: number): string {
  let title = "";
  while (columnNumber > 0) {
    columnNumber--; // shift 1..26 down to 0..25 so Z (26) doesn't roll into the next place
    title = String.fromCharCode(65 + (columnNumber % 26)) + title;
    columnNumber = Math.floor(columnNumber / 26);
  }
  return title;
}

// LC 168. Base 26 with digits 1..26 instead of 0..25: decrement BEFORE each
// mod and divide, then reverse the low-digit-first letters.
func convertToTitle(columnNumber int) string {
	var letters []byte
	for columnNumber > 0 {
		columnNumber-- // shift this digit from 1..26 down to 0..25
		letters = append(letters, byte('A'+columnNumber%26))
		columnNumber /= 26
	}
	for i, j := 0, len(letters)-1; i < j; i, j = i+1, j-1 {
		letters[i], letters[j] = letters[j], letters[i]
	}
	return string(letters)
}

// LC 168. Base 26 with digits 1..26 instead of 0..25: DECREMENT before each
// mod-and-divide, emit letters low digit first, reverse at the end.
func convertToTitle(_ columnNumber: Int) -> String {
    var n = columnNumber
    var letters: [Character] = []
    while n > 0 {
        n -= 1  // shift this digit from 1..26 down to 0..25
        letters.append(Character(UnicodeScalar(UInt8(ascii: "A") + UInt8(n % 26))))
        n /= 26
    }
    return String(letters.reversed())
}

def gcd_of_strings(str1: str, str2: str) -> str:
    """LC 1071. Greatest Common Divisor of Strings.

    A divisor string exists iff str1 + str2 == str2 + str1 -- the
    concatenation test is the whole proof: two strings commute under
    concatenation exactly when both are whole-number repeats of one
    shared unit. Once they commute, the LARGEST divisor is simply the
    prefix of length gcd(len(str1), len(str2)). O(n + m) time and
    space (for the concatenation test).
    """
    if str1 + str2 != str2 + str1:
        return ""  # the strings don't commute: no shared repeating unit
    return str1[: gcd(len(str1), len(str2))]

// LC 1071. The strings share a repeating unit exactly when they commute under
// concatenation, so test s + t == t + s; if it fails return "". When it
// holds, the common unit's largest multiple that divides both is the prefix
// of length gcd(|s|, |t|) -- no further verification needed.
string gcdOfStrings(string str1, string str2) {
    if (str1 + str2 != str2 + str1) return "";
    return str1.substr(0, gcd(str1.size(), str2.size()));
}

/// LC 1071. The concatenation test is the whole proof: s + t == t + s
/// exactly when both strings repeat one common unit. If they commute, the
/// prefix of length gcd(|s|, |t|) is the largest divisor string; if not,
/// no divisor exists and the answer is empty.
pub fn gcd_of_strings(str1: String, str2: String) -> String {
    fn gcd(a: usize, b: usize) -> usize {
        if b == 0 { a } else { gcd(b, a % b) }
    }
    if format!("{}{}", str1, str2) != format!("{}{}", str2, str1) {
        return String::new();
    }
    str1[..gcd(str1.len(), str2.len())].to_string()
}

/** LC 1071. Strings share a repeating unit iff s+t === t+s; then the answer is the gcd-of-lengths prefix. */
export function gcdOfStrings(str1: string, str2: string): string {
  if (str1 + str2 !== str2 + str1) return ""; // commuting under concatenation IS the divisibility proof
  return str1.slice(0, gcd(str1.length, str2.length));
}

// LC 1071. A divisor string exists iff str1+str2 == str2+str1; when the
// strings commute, the largest one is the prefix of length gcd(|s|, |t|).
func gcdOfStrings(str1 string, str2 string) string {
	if str1+str2 != str2+str1 {
		return "" // the strings don't commute: no shared repeating unit
	}
	gcd := func(a, b int) int {
		for b != 0 {
			a, b = b, a%b
		}
		return a
	}
	return str1[:gcd(len(str1), len(str2))]
}

// LC 1071. A divisor string exists iff str1 + str2 == str2 + str1; then the
// largest one is simply the prefix of length gcd(|str1|, |str2|).
func gcdOfStrings(_ str1: String, _ str2: String) -> String {
    func gcd(_ a: Int, _ b: Int) -> Int {
        var (a, b) = (a, b)
        while b != 0 { (a, b) = (b, a % b) }
        return a
    }
    if str1 + str2 != str2 + str1 { return "" }  // no shared repeating unit
    return String(str1.prefix(gcd(str1.count, str2.count)))
}

def insert_greatest_common_divisors(head: "ListNode | None") -> "ListNode | None":
    """LC 2807. Insert Greatest Common Divisors in Linked List.

    Walk with a cur pointer; while a next node exists, splice a fresh
    node holding gcd(cur.val, cur.next.val) between the pair. The only
    real pitfall is the advance step: jump TWO hops to land on the old
    next node, or the loop would process the freshly inserted gcd node
    as if it were original. O(n) time, O(1) space beyond the new nodes.
    """
    cur = head
    while cur and cur.next:
        cur.next = ListNode(gcd(cur.val, cur.next.val), cur.next)
        cur = cur.next.next  # skip the spliced gcd node, land on the old next
    return head

// LC 2807. Walk with a current pointer; for each adjacent pair splice in a
// new node holding gcd of the two values. The one pitfall is the advance:
// jump straight to the OLD next node, skipping the freshly inserted one, or
// the loop would process the insertion again. O(n) time.
ListNode* insertGreatestCommonDivisors(ListNode* head) {
    for (ListNode* cur = head; cur != nullptr && cur->next != nullptr;) {
        ListNode* after = cur->next;
        cur->next = new ListNode(gcd(cur->val, after->val), after);
        cur = after;  // skip over the node just spliced in
    }
    return head;
}

/// LC 2807. Walk a `&mut` cursor over the owned list: `take` the rest off
/// the current node, splice in a gcd node that owns it, then advance the
/// cursor THROUGH the inserted node onto the original successor -- skipping
/// it is what keeps the loop from processing its own insertions.
pub fn insert_greatest_common_divisors(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    fn gcd(a: i32, b: i32) -> i32 {
        if b == 0 { a } else { gcd(b, a % b) }
    }
    let mut cursor = &mut head;
    while let Some(node) = cursor {
        match node.next.take() {
            Some(next) => {
                let spliced = Box::new(ListNode {
                    val: gcd(node.val, next.val),
                    next: Some(next),
                });
                node.next = Some(spliced);
                // Land on the original successor, past the gcd node.
                cursor = &mut node.next.as_mut().unwrap().next;
            }
            None => break,
        }
    }
    head
}

/** LC 2807. Splice gcd(cur, next) between each adjacent pair, then advance PAST the fresh node to the old next. */
export function insertGreatestCommonDivisors(head: ListNode | null): ListNode | null {
  let cur = head;
  while (cur !== null && cur.next !== null) {
    const after = cur.next;
    cur.next = new ListNode(gcd(cur.val, after.val), after);
    cur = after; // skipping the inserted node keeps the loop off its own output
  }
  return head;
}

// LC 2807. Splice gcd(cur, next) between each pair, then hop straight to the
// OLD next node so the loop never reprocesses the fresh insertion.
func insertGreatestCommonDivisors(head *ListNode) *ListNode {
	gcd := func(a, b int) int {
		for b != 0 {
			a, b = b, a%b
		}
		return a
	}
	for cur := head; cur != nil && cur.Next != nil; {
		after := cur.Next
		cur.Next = &ListNode{Val: gcd(cur.Val, after.Val), Next: after}
		cur = after // skip over the node just spliced in
	}
	return head
}

// LC 2807. Splice a fresh gcd node between every adjacent pair, then hop TWO
// nodes so the loop never re-processes the node it just inserted.
func insertGreatestCommonDivisors(_ head: ListNode?) -> ListNode? {
    func gcd(_ a: Int, _ b: Int) -> Int {
        var (a, b) = (a, b)
        while b != 0 { (a, b) = (b, a % b) }
        return a
    }
    var cur = head
    while let node = cur, let after = node.next {
        node.next = ListNode(gcd(node.val, after.val), after)
        cur = after  // skip over the node just spliced in
    }
    return head
}

def transpose(matrix: list[list[int]]) -> list[list[int]]:
    """LC 867. Transpose Matrix.

    Flip over the main diagonal: out[j][i] = matrix[i][j] for every
    cell, via a double loop. The thing to remember: the input can be
    RECTANGULAR, so an in-place triangle swap is impossible in general
    -- a fresh cols-by-rows allocation is required. O(m * n) time and
    space.
    """
    rows, cols = len(matrix), len(matrix[0])
    flipped = [[0] * rows for _ in range(cols)]  # dimensions swap: cols x rows
    for i in range(rows):
        for j in range(cols):
            flipped[j][i] = matrix[i][j]
    return flipped

// LC 867. Allocate a fresh n-by-m matrix and copy out[j][i] = in[i][j] with a
// double loop. The input can be rectangular, so an in-place triangle swap is
// impossible in general; the swapped-dimensions allocation is the answer.
vector<vector<int>> transpose(vector<vector<int>> matrix) {
    int m = static_cast<int>(matrix.size());
    int n = static_cast<int>(matrix[0].size());
    vector<vector<int>> out(n, vector<int>(m));
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j) out[j][i] = matrix[i][j];
    return out;
}

/// LC 867. out[j][i] = in[i][j] into a fresh cols-by-rows allocation. The
/// input can be rectangular, so an in-place triangle swap is impossible in
/// general and the new matrix with swapped dimensions is required.
pub fn transpose(matrix: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    let (rows, cols) = (matrix.len(), matrix[0].len());
    let mut out = vec![vec![0; rows]; cols];
    for (i, row) in matrix.iter().enumerate() {
        for (j, &x) in row.iter().enumerate() {
            out[j][i] = x;
        }
    }
    out
}

/** LC 867. Input can be rectangular, so allocate a fresh cols-by-rows matrix and set out[j][i] = in[i][j]. */
export function transpose(matrix: number[][]): number[][] {
  const rows = matrix.length;
  const cols = matrix[0].length;
  const out: number[][] = Array.from({ length: cols }, () => new Array<number>(rows));
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) out[j][i] = matrix[i][j];
  }
  return out;
}

// LC 867. The input can be rectangular, so allocate a fresh cols-by-rows
// matrix and copy out[j][i] = in[i][j]; an in-place triangle swap can't work.
func transpose(matrix [][]int) [][]int {
	m, n := len(matrix), len(matrix[0])
	out := make([][]int, n)
	for j := range out {
		out[j] = make([]int, m)
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			out[j][i] = matrix[i][j]
		}
	}
	return out
}

// LC 867. The input can be RECTANGULAR, so allocate a fresh cols-by-rows
// matrix and copy out[j][i] = in[i][j]; no in-place triangle swap exists.
func transpose(_ matrix: [[Int]]) -> [[Int]] {
    let m = matrix.count, n = matrix[0].count
    var out = [[Int]](repeating: [Int](repeating: 0, count: m), count: n)
    for i in 0..<m {
        for j in 0..<n { out[j][i] = matrix[i][j] }
    }
    return out
}

def rotate_image(matrix: list[list[int]]) -> None:
    """LC 48. Rotate Image.

    Rotate the n x n matrix 90 degrees clockwise IN PLACE by composing
    two reflections: transpose (swap across the main diagonal), then
    reverse every row. Transpose plus COLUMN reversal would rotate
    counterclockwise instead -- the decomposition is the memorable
    part. The transpose loop must touch only one triangle, or each
    swap's mirror undoes it. O(n^2) time, O(1) space.
    """
    n = len(matrix)
    for i in range(n):
        for j in range(i + 1, n):  # one triangle only, or swaps undo themselves
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    for row in matrix:
        row.reverse()

// LC 48. Clockwise rotation decomposes as transpose then reverse each row
// (column reversal instead would rotate counterclockwise). The transpose loop
// must only touch the triangle above the diagonal -- sweeping all (i, j)
// would swap every pair twice and undo itself. In place, O(n^2) time.
void rotateImage(vector<vector<int>>& matrix) {
    int n = static_cast<int>(matrix.size());
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j) swap(matrix[i][j], matrix[j][i]);  // upper triangle only
    for (auto& row : matrix) reverse(row.begin(), row.end());
}

/// LC 48. Clockwise rotation decomposes as transpose then reverse each row
/// (column reversal instead would rotate counterclockwise). The transpose
/// loop must touch only the upper triangle, j > i, or every swap is undone
/// by its mirror.
pub fn rotate_image(matrix: &mut Vec<Vec<i32>>) {
    let n = matrix.len();
    for i in 0..n {
        for j in i + 1..n {
            let tmp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = tmp;
        }
    }
    for row in matrix.iter_mut() {
        row.reverse();
    }
}

/** LC 48. In place: transpose (swap one triangle only, or it undoes itself), then reverse every row. */
export function rotateImage(matrix: number[][]): void {
  const n = matrix.length;
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      // j > i keeps the swap to the upper triangle; row reversal then completes the clockwise turn
      [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
    }
  }
  for (const row of matrix) row.reverse();
}

// LC 48. Rotate clockwise in place: transpose (upper triangle only, or each
// swap's mirror undoes it), then reverse every row.
func rotateImage(matrix [][]int) {
	n := len(matrix)
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ { // upper triangle only
			matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
		}
	}
	for _, row := range matrix {
		for i, j := 0, n-1; i < j; i, j = i+1, j-1 {
			row[i], row[j] = row[j], row[i]
		}
	}
}

// LC 48. Clockwise rotation in place = transpose then reverse each row; the
// transpose must touch one triangle only, or each swap's mirror undoes it.
func rotateImage(_ matrix: inout [[Int]]) {
    let n = matrix.count
    for i in 0..<n {
        for j in (i + 1)..<n {  // upper triangle only
            let tmp = matrix[i][j]
            matrix[i][j] = matrix[j][i]
            matrix[j][i] = tmp
        }
    }
    for i in 0..<n { matrix[i].reverse() }
}

def spiral_order(matrix: list[list[int]]) -> list[int]:
    """LC 54. Spiral Matrix.

    Maintain four boundaries -- top, bottom, left, right -- and peel
    one ring at a time: walk right along the top row, down the right
    column, left along the bottom row, up the left column, shrinking
    the matching boundary after each side. WHY the mid-ring re-checks:
    after the top and right walks shrink their boundaries, a ring that
    was a single row (or single column) is already fully emitted, and
    without re-testing top <= bottom and left <= right the leftward
    and upward passes would walk those same cells a second time.
    O(m * n) time, O(1) extra space.
    """
    out = []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    while top <= bottom and left <= right:
        for col in range(left, right + 1):  # right along the top row
            out.append(matrix[top][col])
        top += 1
        for row in range(top, bottom + 1):  # down the right column
            out.append(matrix[row][right])
        right -= 1
        if top <= bottom:  # re-check: a lone leftover row was already walked
            for col in range(right, left - 1, -1):  # left along the bottom row
                out.append(matrix[bottom][col])
            bottom -= 1
        if left <= right:  # re-check: a lone leftover column was already walked
            for row in range(bottom, top - 1, -1):  # up the left column
                out.append(matrix[row][left])
            left += 1
    return out

// LC 54. Keep four boundaries -- top, bottom, left, right -- walk one side at
// a time, and shrink that side's boundary after finishing it. The classic
// pitfall is a leftover single row or column: re-check the boundaries before
// the leftward and upward passes, or those cells get emitted twice.
vector<int> spiralOrder(vector<vector<int>> matrix) {
    int top = 0, bottom = static_cast<int>(matrix.size()) - 1;
    int left = 0, right = static_cast<int>(matrix[0].size()) - 1;
    vector<int> out;
    while (top <= bottom && left <= right) {
        for (int j = left; j <= right; ++j) out.push_back(matrix[top][j]);
        ++top;
        for (int i = top; i <= bottom; ++i) out.push_back(matrix[i][right]);
        --right;
        if (top <= bottom) {  // guard: a single leftover row was already emitted
            for (int j = right; j >= left; --j) out.push_back(matrix[bottom][j]);
            --bottom;
        }
        if (left <= right) {  // guard: a single leftover column was already emitted
            for (int i = bottom; i >= top; --i) out.push_back(matrix[i][left]);
            ++left;
        }
    }
    return out;
}

/// LC 54. Four boundaries shrink inward as each side of the current ring
/// is emitted: right along top, down along right, left along bottom, up
/// along left. The leftward and upward passes re-check their boundaries
/// first -- a leftover single row or column would otherwise be emitted
/// twice. Signed boundaries dodge usize underflow on the decrements.
pub fn spiral_order(matrix: Vec<Vec<i32>>) -> Vec<i32> {
    let (mut top, mut bottom) = (0i32, matrix.len() as i32 - 1);
    let (mut left, mut right) = (0i32, matrix[0].len() as i32 - 1);
    let mut out = Vec::new();
    while top <= bottom && left <= right {
        for c in left..=right {
            out.push(matrix[top as usize][c as usize]);
        }
        top += 1;
        for r in top..=bottom {
            out.push(matrix[r as usize][right as usize]);
        }
        right -= 1;
        if top <= bottom {
            for c in (left..=right).rev() {
                out.push(matrix[bottom as usize][c as usize]);
            }
            bottom -= 1;
        }
        if left <= right {
            for r in (top..=bottom).rev() {
                out.push(matrix[r as usize][left as usize]);
            }
            left += 1;
        }
    }
    out
}

/** LC 54. Four shrinking boundaries; re-check top/bottom and left/right before the left and up passes. */
export function spiralOrder(matrix: number[][]): number[] {
  const result: number[] = [];
  let top = 0;
  let bottom = matrix.length - 1;
  let left = 0;
  let right = matrix[0].length - 1;
  while (top <= bottom && left <= right) {
    for (let col = left; col <= right; col++) result.push(matrix[top][col]);
    top++;
    for (let row = top; row <= bottom; row++) result.push(matrix[row][right]);
    right--;
    if (top <= bottom) {
      // without this re-check a single leftover row would be emitted twice
      for (let col = right; col >= left; col--) result.push(matrix[bottom][col]);
      bottom--;
    }
    if (left <= right) {
      // and this one protects a single leftover column
      for (let row = bottom; row >= top; row--) result.push(matrix[row][left]);
      left++;
    }
  }
  return result;
}

// LC 54. Four shrinking boundaries; re-check before the leftward and upward
// walks or a lone leftover row or column gets emitted twice.
func spiralOrder(matrix [][]int) []int {
	top, bottom := 0, len(matrix)-1
	left, right := 0, len(matrix[0])-1
	var out []int
	for top <= bottom && left <= right {
		for j := left; j <= right; j++ { // right along the top row
			out = append(out, matrix[top][j])
		}
		top++
		for i := top; i <= bottom; i++ { // down the right column
			out = append(out, matrix[i][right])
		}
		right--
		if top <= bottom { // guard: a single leftover row was already emitted
			for j := right; j >= left; j-- {
				out = append(out, matrix[bottom][j])
			}
			bottom--
		}
		if left <= right { // guard: a single leftover column was already emitted
			for i := bottom; i >= top; i-- {
				out = append(out, matrix[i][left])
			}
			left++
		}
	}
	return out
}

// LC 54. Four shrinking boundaries, one ring at a time; re-check top/bottom
// and left/right mid-ring or a lone leftover row/column is emitted twice.
func spiralOrder(_ matrix: [[Int]]) -> [Int] {
    var top = 0, bottom = matrix.count - 1
    var left = 0, right = matrix[0].count - 1
    var out: [Int] = []
    while top <= bottom && left <= right {
        for j in left...right { out.append(matrix[top][j]) }  // right along the top
        top += 1
        for i in stride(from: top, through: bottom, by: 1) { out.append(matrix[i][right]) }
        right -= 1
        if top <= bottom {  // guard: a single leftover row was already emitted
            for j in stride(from: right, through: left, by: -1) { out.append(matrix[bottom][j]) }
            bottom -= 1
        }
        if left <= right {  // guard: a single leftover column was already emitted
            for i in stride(from: bottom, through: top, by: -1) { out.append(matrix[i][left]) }
            left += 1
        }
    }
    return out
}

def set_zeroes(matrix: list[list[int]]) -> None:
    """LC 73. Set Matrix Zeroes.

    Use the first row and first column as marker space: a zero at
    (i, j) sets matrix[i][0] and matrix[0][j]. Two plain booleans
    record beforehand whether the first row and column held zeros of
    their own, since their cells now do double duty as markers. WHY
    the order of the final sweeps: zero the INTERIOR from the markers
    first, and only then the first row and column themselves --
    clearing the marker space too early would destroy the instructions
    for every interior cell. O(m * n) time, O(1) extra space.
    """
    rows, cols = len(matrix), len(matrix[0])
    first_row_had_zero = any(matrix[0][j] == 0 for j in range(cols))
    first_col_had_zero = any(matrix[i][0] == 0 for i in range(rows))
    for i in range(1, rows):
        for j in range(1, cols):
            if matrix[i][j] == 0:
                matrix[i][0] = 0  # mark the row in the border space
                matrix[0][j] = 0  # mark the column in the border space
    # interior FIRST: the border must still hold its markers here
    for i in range(1, rows):
        for j in range(1, cols):
            if matrix[i][0] == 0 or matrix[0][j] == 0:
                matrix[i][j] = 0
    # border LAST: only now is destroying the marker space safe
    if first_row_had_zero:
        for j in range(cols):
            matrix[0][j] = 0
    if first_col_had_zero:
        for i in range(rows):
            matrix[i][0] = 0

// LC 73. Use the first row and first column as the marker space for which
// rows/columns must be cleared, remembering separately whether they held
// zeros themselves. Zero the interior from the markers first and handle the
// first row and column LAST -- clearing them early would destroy the markers
// for everything else. O(1) extra space.
void setZeroes(vector<vector<int>>& matrix) {
    int m = static_cast<int>(matrix.size());
    int n = static_cast<int>(matrix[0].size());
    bool firstRowZero = false, firstColZero = false;
    for (int j = 0; j < n; ++j)
        if (matrix[0][j] == 0) firstRowZero = true;
    for (int i = 0; i < m; ++i)
        if (matrix[i][0] == 0) firstColZero = true;
    for (int i = 1; i < m; ++i)
        for (int j = 1; j < n; ++j)
            if (matrix[i][j] == 0) matrix[i][0] = matrix[0][j] = 0;  // mark row i, col j
    for (int i = 1; i < m; ++i)
        for (int j = 1; j < n; ++j)
            if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;
    if (firstRowZero)
        for (int j = 0; j < n; ++j) matrix[0][j] = 0;
    if (firstColZero)
        for (int i = 0; i < m; ++i) matrix[i][0] = 0;
}

/// LC 73. The first row and first column double as marker space: record
/// up front whether each originally held a zero, mark interior zeros into
/// them, zero interior cells from the marks, and only THEN clear the first
/// row and column -- clearing them earlier destroys the markers.
pub fn set_zeroes(matrix: &mut Vec<Vec<i32>>) {
    let (rows, cols) = (matrix.len(), matrix[0].len());
    let first_row_zero = matrix[0].contains(&0);
    let first_col_zero = (0..rows).any(|i| matrix[i][0] == 0);
    for i in 1..rows {
        for j in 1..cols {
            if matrix[i][j] == 0 {
                matrix[i][0] = 0;
                matrix[0][j] = 0;
            }
        }
    }
    for i in 1..rows {
        for j in 1..cols {
            if matrix[i][0] == 0 || matrix[0][j] == 0 {
                matrix[i][j] = 0;
            }
        }
    }
    if first_row_zero {
        matrix[0].iter_mut().for_each(|x| *x = 0);
    }
    if first_col_zero {
        for i in 0..rows {
            matrix[i][0] = 0;
        }
    }
}

/** LC 73. First row/col double as marker space; zero the interior from them, then handle them LAST. */
export function setZeroes(matrix: number[][]): void {
  const rows = matrix.length;
  const cols = matrix[0].length;
  let firstRowHadZero = false;
  let firstColHadZero = false;
  for (let j = 0; j < cols; j++) if (matrix[0][j] === 0) firstRowHadZero = true;
  for (let i = 0; i < rows; i++) if (matrix[i][0] === 0) firstColHadZero = true;
  for (let i = 1; i < rows; i++) {
    for (let j = 1; j < cols; j++) {
      if (matrix[i][j] === 0) {
        matrix[i][0] = 0; // mark the row in column 0
        matrix[0][j] = 0; // mark the column in row 0
      }
    }
  }
  for (let i = 1; i < rows; i++) {
    for (let j = 1; j < cols; j++) {
      if (matrix[i][0] === 0 || matrix[0][j] === 0) matrix[i][j] = 0;
    }
  }
  // clearing these any earlier would destroy the markers for the interior
  if (firstRowHadZero) for (let j = 0; j < cols; j++) matrix[0][j] = 0;
  if (firstColHadZero) for (let i = 0; i < rows; i++) matrix[i][0] = 0;
}

// LC 73. Use the first row and column as marker space; zero the interior from
// the markers FIRST and the border LAST, or the instructions are destroyed.
func setZeroes(matrix [][]int) {
	m, n := len(matrix), len(matrix[0])
	firstRowZero, firstColZero := false, false
	for j := 0; j < n; j++ {
		if matrix[0][j] == 0 {
			firstRowZero = true
		}
	}
	for i := 0; i < m; i++ {
		if matrix[i][0] == 0 {
			firstColZero = true
		}
	}
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			if matrix[i][j] == 0 {
				matrix[i][0] = 0 // mark row i in the border space
				matrix[0][j] = 0 // mark column j in the border space
			}
		}
	}
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			if matrix[i][0] == 0 || matrix[0][j] == 0 {
				matrix[i][j] = 0
			}
		}
	}
	if firstRowZero {
		for j := 0; j < n; j++ {
			matrix[0][j] = 0
		}
	}
	if firstColZero {
		for i := 0; i < m; i++ {
			matrix[i][0] = 0
		}
	}
}

// LC 73. First row and column double as marker space: zero the interior from
// the markers FIRST, the border LAST, or the instructions are destroyed.
func setZeroes(_ matrix: inout [[Int]]) {
    let m = matrix.count, n = matrix[0].count
    var firstRowZero = false, firstColZero = false
    for j in 0..<n where matrix[0][j] == 0 { firstRowZero = true }
    for i in 0..<m where matrix[i][0] == 0 { firstColZero = true }
    for i in 1..<m {
        for j in 1..<n where matrix[i][j] == 0 {
            matrix[i][0] = 0  // mark row i in the border space
            matrix[0][j] = 0  // mark column j in the border space
        }
    }
    for i in 1..<m {  // interior FIRST: the border still holds its markers
        for j in 1..<n where matrix[i][0] == 0 || matrix[0][j] == 0 {
            matrix[i][j] = 0
        }
    }
    if firstRowZero {
        for j in 0..<n { matrix[0][j] = 0 }
    }
    if firstColZero {
        for i in 0..<m { matrix[i][0] = 0 }
    }
}

def is_happy(n: int) -> bool:
    """LC 202. Happy Number.

    The digit-square-sum sequence always falls into a cycle (its values
    are bounded, so some value must repeat), which makes this pure
    cycle detection: reaching 1 means happy, any other cycle means not.
    Run Floyd's fast/slow pointers over the sequence -- 1 is a fixed
    point, so a happy number parks fast at 1 while an unhappy one
    forces the pointers to meet inside the doom loop. O(log n) work
    per step, O(1) space.
    """

    def digit_square_sum(num: int) -> int:
        total = 0
        while num:
            num, digit = divmod(num, 10)
            total += digit * digit
        return total

    slow, fast = n, digit_square_sum(n)
    while fast != 1 and slow != fast:
        slow = digit_square_sum(slow)
        fast = digit_square_sum(digit_square_sum(fast))
    return fast == 1

// LC 202. The digit-square-sum sequence always falls into a cycle, so this is
// pure cycle detection: run Floyd's fast and slow pointers through the
// sequence and check which cycle was entered. Reaching 1 (a self-loop) means
// happy; meeting anywhere else means the unhappy 4-cycle. O(1) space.
bool isHappy(int n) {
    auto digitSquareSum = [](int x) -> int {
        int sum = 0;
        while (x > 0) {
            int d = x % 10;
            sum += d * d;
            x /= 10;
        }
        return sum;
    };
    int slow = n, fast = digitSquareSum(n);
    while (fast != 1 && slow != fast) {
        slow = digitSquareSum(slow);
        fast = digitSquareSum(digitSquareSum(fast));
    }
    return fast == 1;
}

/// LC 202. The digit-square sequence always falls into a cycle, so this is
/// pure cycle detection: Floyd's fast and slow pointers step through the
/// sequence in O(1) space, and the cycle containing 1 (a fixed point) means
/// happy while any other cycle means not.
pub fn is_happy(n: i32) -> bool {
    fn digit_squares(mut n: i32) -> i32 {
        let mut sum = 0;
        while n > 0 {
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
        sum
    }
    let (mut slow, mut fast) = (n, digit_squares(n));
    while fast != 1 && slow != fast {
        slow = digit_squares(slow);
        fast = digit_squares(digit_squares(fast));
    }
    fast == 1
}

/** LC 202. The digit-square sequence always enters a cycle: Floyd's fast/slow, happy iff fast reaches 1. */
export function isHappy(n: number): boolean {
  function digitSquareSum(num: number): number {
    let sum = 0;
    while (num > 0) {
      const digit = num % 10;
      sum += digit * digit;
      num = Math.floor(num / 10);
    }
    return sum;
  }
  let slow = n;
  let fast = digitSquareSum(n);
  while (fast !== 1 && slow !== fast) {
    slow = digitSquareSum(slow);
    fast = digitSquareSum(digitSquareSum(fast)); // meeting anywhere but 1 means an unhappy cycle
  }
  return fast === 1;
}

// LC 202. Floyd's fast/slow pointers over digit-square sums: 1 is a fixed
// point, so meeting anywhere else means the unhappy doom cycle.
func isHappy(n int) bool {
	digitSquareSum := func(x int) int {
		sum := 0
		for x > 0 {
			d := x % 10
			sum += d * d
			x /= 10
		}
		return sum
	}
	slow, fast := n, digitSquareSum(n)
	for fast != 1 && slow != fast {
		slow = digitSquareSum(slow)
		fast = digitSquareSum(digitSquareSum(fast))
	}
	return fast == 1
}

// LC 202. Floyd fast/slow over digit-square sums: 1 is a fixed point, so a
// happy number parks fast at 1 while an unhappy one meets inside the loop.
func isHappy(_ n: Int) -> Bool {
    func digitSquareSum(_ x: Int) -> Int {
        var x = x, sum = 0
        while x > 0 {
            let d = x % 10
            sum += d * d
            x /= 10
        }
        return sum
    }
    var slow = n, fast = digitSquareSum(n)
    while fast != 1 && slow != fast {
        slow = digitSquareSum(slow)
        fast = digitSquareSum(digitSquareSum(fast))
    }
    return fast == 1
}

def plus_one(digits: list[int]) -> list[int]:
    """LC 66. Plus One.

    Carry from the back: walk right to left turning each 9 into 0 and
    continuing; the first non-9 digit absorbs the carry and the walk
    stops immediately. The only special case is a carry surviving past
    the front, as in 999, where a new leading 1 must be prepended to
    the now all-zero array. O(n) time, O(1) extra space.
    """
    for i in range(len(digits) - 1, -1, -1):
        if digits[i] < 9:
            digits[i] += 1
            return digits  # carry absorbed; nothing to the left changes
        digits[i] = 0  # a 9 rolls over and pushes the carry leftward
    return [1] + digits  # carry survived past the front: 999 -> 1000

// LC 66. Walk from the last digit toward the front: a 9 becomes 0 and the
// carry continues; anything else is incremented and the answer returns
// immediately. The only special case is a carry surviving past the front
// (999), where a leading 1 is prepended to the now all-zero array.
vector<int> plusOne(vector<int> digits) {
    for (int i = static_cast<int>(digits.size()) - 1; i >= 0; --i) {
        if (digits[i] < 9) {
            ++digits[i];
            return digits;
        }
        digits[i] = 0;  // 9 rolls over, carry continues left
    }
    digits.insert(digits.begin(), 1);  // carry survived past the front
    return digits;
}

/// LC 66. Walk from the last digit toward the front: a 9 becomes 0 and the
/// carry continues, anything else increments and returns immediately. Only
/// an all-9s number survives the loop, and it needs a new leading 1
/// prepended to the now all-zero array.
pub fn plus_one(mut digits: Vec<i32>) -> Vec<i32> {
    for i in (0..digits.len()).rev() {
        if digits[i] < 9 {
            digits[i] += 1;
            return digits;
        }
        digits[i] = 0;
    }
    digits.insert(0, 1);
    digits
}

/** LC 66. Up to 100 digits, so stay on the array: 9s roll to 0 right-to-left; a surviving carry prepends 1. */
export function plusOne(digits: number[]): number[] {
  for (let i = digits.length - 1; i >= 0; i--) {
    if (digits[i] < 9) {
      digits[i]++; // no carry past here, done immediately
      return digits;
    }
    digits[i] = 0; // a 9 becomes 0 and the carry keeps moving left
  }
  return [1, ...digits]; // carry survived the front: 999 -> 1000
}

// LC 66. Carry from the back: 9s roll to 0, the first non-9 absorbs the carry
// and stops; a carry surviving past the front prepends a leading 1.
func plusOne(digits []int) []int {
	for i := len(digits) - 1; i >= 0; i-- {
		if digits[i] < 9 {
			digits[i]++
			return digits // carry absorbed; nothing to the left changes
		}
		digits[i] = 0 // a 9 rolls over and pushes the carry leftward
	}
	return append([]int{1}, digits...) // carry survived past the front: 999 -> 1000
}

// LC 66. Carry from the back: each 9 rolls to 0, the first non-9 absorbs the
// carry and stops; a carry surviving past the front (999) prepends a 1.
func plusOne(_ digits: [Int]) -> [Int] {
    var digits = digits
    for i in stride(from: digits.count - 1, through: 0, by: -1) {
        if digits[i] < 9 {
            digits[i] += 1
            return digits  // carry absorbed; nothing to the left changes
        }
        digits[i] = 0  // a 9 rolls over and pushes the carry leftward
    }
    return [1] + digits  // carry survived past the front: 999 -> 1000
}

def roman_to_int(s: str) -> int:
    """LC 13. Roman to Integer.

    Map each symbol to its value and scan, adding each value but
    SUBTRACTING it whenever the symbol to its right is strictly larger.
    That one rule covers all six subtractive pairs (IV, IX, XL, XC,
    CD, CM) with no special casing, and the final symbol is always
    added since nothing follows it. O(n) time, O(1) space.
    """
    values = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
    total = 0
    for i, symbol in enumerate(s):
        if i + 1 < len(s) and values[symbol] < values[s[i + 1]]:
            total -= values[symbol]  # smaller before larger: subtractive pair
        else:
            total += values[symbol]
    return total

// LC 13. Scan left to right, adding each symbol's value but SUBTRACTING it
// whenever the symbol to its right is strictly larger. That one rule covers
// all six subtractive pairs (IV, IX, XL, XC, CD, CM) with no special casing;
// the final symbol is always added since nothing follows it.
int romanToInt(string s) {
    auto value = [](char c) -> int {
        switch (c) {
            case 'I': return 1;
            case 'V': return 5;
            case 'X': return 10;
            case 'L': return 50;
            case 'C': return 100;
            case 'D': return 500;
            default: return 1000;  // 'M'
        }
    };
    int n = static_cast<int>(s.size());
    int total = 0;
    for (int i = 0; i < n; ++i) {
        int v = value(s[i]);
        if (i + 1 < n && value(s[i + 1]) > v)
            total -= v;  // subtractive pair: smaller symbol before larger
        else
            total += v;
    }
    return total;
}

/// LC 13. Add each symbol's value, but SUBTRACT it when the symbol to its
/// right is strictly larger -- that one rule covers all six subtractive
/// pairs (IV, IX, XL, XC, CD, CM) with no special casing, and the final
/// symbol always adds since nothing follows it.
pub fn roman_to_int(s: String) -> i32 {
    fn value(symbol: u8) -> i32 {
        match symbol {
            b'I' => 1,
            b'V' => 5,
            b'X' => 10,
            b'L' => 50,
            b'C' => 100,
            b'D' => 500,
            _ => 1000,
        }
    }
    let b = s.as_bytes();
    let mut total = 0;
    for i in 0..b.len() {
        let v = value(b[i]);
        if i + 1 < b.len() && v < value(b[i + 1]) {
            total -= v;
        } else {
            total += v;
        }
    }
    total
}

/** LC 13. Add each symbol's value, but SUBTRACT it when the next symbol is strictly larger (IV, CM, ...). */
export function romanToInt(s: string): number {
  const valueOf: Record<string, number> = { I: 1, V: 5, X: 10, L: 50, C: 100, D: 500, M: 1000 };
  let total = 0;
  for (let i = 0; i < s.length; i++) {
    // the final symbol always adds, since nothing follows it
    if (i + 1 < s.length && valueOf[s[i]] < valueOf[s[i + 1]]) total -= valueOf[s[i]];
    else total += valueOf[s[i]];
  }
  return total;
}

// LC 13. Add each symbol's value, SUBTRACTING it when a strictly larger
// symbol follows -- one rule covers all six subtractive pairs.
func romanToInt(s string) int {
	value := func(c byte) int {
		switch c {
		case 'I':
			return 1
		case 'V':
			return 5
		case 'X':
			return 10
		case 'L':
			return 50
		case 'C':
			return 100
		case 'D':
			return 500
		}
		return 1000 // 'M'
	}
	total := 0
	for i := 0; i < len(s); i++ {
		v := value(s[i])
		if i+1 < len(s) && value(s[i+1]) > v {
			total -= v // subtractive pair: smaller symbol before larger
		} else {
			total += v
		}
	}
	return total
}

// LC 13. Add each symbol's value but SUBTRACT it when the next symbol is
// strictly larger -- one rule covers all six subtractive pairs.
func romanToInt(_ s: String) -> Int {
    func value(_ c: Character) -> Int {
        switch c {
        case "I": return 1
        case "V": return 5
        case "X": return 10
        case "L": return 50
        case "C": return 100
        case "D": return 500
        default: return 1000  // 'M'
        }
    }
    let chars = Array(s)
    var total = 0
    for i in 0..<chars.count {
        let v = value(chars[i])
        if i + 1 < chars.count && value(chars[i + 1]) > v {
            total -= v  // subtractive pair: smaller symbol before larger
        } else {
            total += v
        }
    }
    return total
}

def my_pow(x: float, n: int) -> float:
    """LC 50. Pow(x, n).

    Exponentiation by squaring: square the base while halving the
    exponent, folding the current square into the result whenever the
    low exponent bit is odd. Handle negative n by inverting x and
    negating n -- trivial with Python's unbounded ints, though in
    fixed-width languages negating INT_MIN overflows unless done in a
    wider type. O(log n) time, O(1) space.
    """
    if n < 0:
        x, n = 1 / x, -n  # x^-n == (1/x)^n
    result = 1.0
    while n:
        if n & 1:  # this exponent bit is set: fold the current square in
            result *= x
        x *= x
        n >>= 1
    return result

// LC 50. Exponentiation by squaring: square the base while halving the
// exponent, multiplying into the result whenever the current bit is odd, for
// O(log n) time. Negative n inverts x and negates the exponent -- in a
// long long, because negating INT_MIN in 32 bits overflows.
double myPow(double x, int n) {
    long long e = n;  // widen BEFORE negating: -INT_MIN overflows int
    if (e < 0) {
        x = 1.0 / x;
        e = -e;
    }
    double result = 1.0;
    while (e > 0) {
        if (e & 1) result *= x;
        x *= x;
        e >>= 1;
    }
    return result;
}

/// LC 50. Exponentiation by squaring: square the base while halving the
/// exponent, multiplying into the result whenever the current bit is odd,
/// for O(log n). A negative n inverts x and negates the exponent -- in i64,
/// because negating i32::MIN overflows in 32 bits.
pub fn my_pow(x: f64, n: i32) -> f64 {
    let mut exp = n as i64; // i64 so -i32::MIN does not overflow
    let mut base = x;
    if exp < 0 {
        base = 1.0 / base;
        exp = -exp;
    }
    let mut result = 1.0;
    while exp > 0 {
        if exp & 1 == 1 {
            result *= base;
        }
        base *= base;
        exp >>= 1;
    }
    result
}

/** LC 50. Exponentiation by squaring: square the base, halve n, multiply in on odd bits; negative n inverts x. */
export function myPow(x: number, n: number): number {
  let base = n < 0 ? 1 / x : x;
  let exp = Math.abs(n); // JS doubles negate -2^31 safely, no 32-bit overflow trap
  let result = 1;
  while (exp > 0) {
    if (exp % 2 === 1) result *= base;
    base *= base;
    exp = Math.floor(exp / 2);
  }
  return result;
}

// LC 50. Square the base while halving the exponent; widen n to int64 BEFORE
// negating, because -math.MinInt32 overflows a 32-bit int.
func myPow(x float64, n int) float64 {
	e := int64(n) // widen before negating
	if e < 0 {
		x = 1 / x // x^-n == (1/x)^n
		e = -e
	}
	result := 1.0
	for e > 0 {
		if e&1 == 1 { // this exponent bit is set: fold the current square in
			result *= x
		}
		x *= x
		e >>= 1
	}
	return result
}

// LC 50. Square the base while halving the exponent, folding in on odd bits;
// negative n inverts x (Swift's 64-bit Int negates 32-bit INT_MIN safely).
func myPow(_ x: Double, _ n: Int) -> Double {
    var base = x, e = n
    if e < 0 {
        base = 1.0 / base  // x^-n == (1/x)^n
        e = -e
    }
    var result = 1.0
    while e > 0 {
        if e & 1 == 1 { result *= base }  // this exponent bit is set
        base *= base
        e >>= 1
    }
    return result
}

def multiply_strings(num1: str, num2: str) -> str:
    """LC 43. Multiply Strings.

    Grade-school multiplication into a digit grid, never calling int()
    on the whole strings. The position fact is the whole solution:
    digit i of num1 times digit j of num2 ALWAYS lands in result slots
    i + j and i + j + 1 (carry and low digit), so accumulate every
    pairwise product into an array of length m + n and strip leading
    zeros at the end. O(m * n) time, O(m + n) space.
    """
    if num1 == "0" or num2 == "0":
        return "0"  # otherwise the lstrip below would eat the whole answer
    m, n = len(num1), len(num2)
    slots = [0] * (m + n)
    for i in range(m - 1, -1, -1):
        for j in range(n - 1, -1, -1):
            product = int(num1[i]) * int(num2[j]) + slots[i + j + 1]
            slots[i + j + 1] = product % 10  # low digit stays in the far slot
            slots[i + j] += product // 10  # carry rolls into the near slot
    return "".join(map(str, slots)).lstrip("0")

// LC 43. Digit grid: the product of digit i of num1 and digit j of num2
// always lands in result slots i+j and i+j+1, so accumulate each pairwise
// product into a length m+n array with carry handling, then strip the
// possible leading zero. That position fact is the whole solution. O(mn).
string multiplyStrings(string num1, string num2) {
    if (num1 == "0" || num2 == "0") return "0";
    int m = static_cast<int>(num1.size());
    int n = static_cast<int>(num2.size());
    vector<int> grid(m + n, 0);
    for (int i = m - 1; i >= 0; --i)
        for (int j = n - 1; j >= 0; --j) {
            int prod = (num1[i] - '0') * (num2[j] - '0') + grid[i + j + 1];
            grid[i + j + 1] = prod % 10;  // low digit stays in slot i+j+1
            grid[i + j] += prod / 10;     // carry feeds slot i+j
        }
    string out;
    for (int d : grid)
        if (!(out.empty() && d == 0)) out.push_back(static_cast<char>('0' + d));
    return out;
}

/// LC 43. Schoolbook multiplication over a digit grid of length m + n: the
/// position fact is the whole solution -- digit i times digit j always
/// lands in slots i + j and i + j + 1, so add each product into i + j + 1,
/// keep the low digit there, and push the carry into i + j. Strip the
/// leading zeros at the end (a "0" times anything would otherwise strip to
/// nothing, hence the early return).
pub fn multiply_strings(num1: String, num2: String) -> String {
    if num1 == "0" || num2 == "0" {
        return "0".to_string();
    }
    let (a, b) = (num1.as_bytes(), num2.as_bytes());
    let mut grid = vec![0u32; a.len() + b.len()];
    for i in (0..a.len()).rev() {
        for j in (0..b.len()).rev() {
            let product = (a[i] - b'0') as u32 * (b[j] - b'0') as u32;
            let sum = product + grid[i + j + 1];
            grid[i + j + 1] = sum % 10;
            grid[i + j] += sum / 10;
        }
    }
    let start = grid.iter().position(|&d| d != 0).unwrap();
    grid[start..].iter().map(|&d| (b'0' + d as u8) as char).collect()
}

/** LC 43. Digit grid: digit i times digit j always lands in slots i+j and i+j+1; strip the leading zero. */
export function multiplyStrings(num1: string, num2: string): string {
  if (num1 === "0" || num2 === "0") return "0";
  const m = num1.length;
  const n = num2.length;
  const grid = new Array<number>(m + n).fill(0);
  for (let i = m - 1; i >= 0; i--) {
    for (let j = n - 1; j >= 0; j--) {
      const product = Number(num1[i]) * Number(num2[j]) + grid[i + j + 1];
      grid[i + j + 1] = product % 10;
      grid[i + j] += Math.floor(product / 10); // the high digit accumulates; later passes re-carry it
    }
  }
  // nonzero factors leave at most one leading zero slot (m+n vs m+n-1 digit products)
  const start = grid[0] === 0 ? 1 : 0;
  return grid.slice(start).join("");
}

// LC 43. Grade-school grid: digit i times digit j ALWAYS lands in slots i+j
// and i+j+1, so accumulate into a length m+n array and strip leading zeros.
func multiplyStrings(num1 string, num2 string) string {
	if num1 == "0" || num2 == "0" {
		return "0" // otherwise the zero-strip below would eat the whole answer
	}
	m, n := len(num1), len(num2)
	grid := make([]int, m+n)
	for i := m - 1; i >= 0; i-- {
		for j := n - 1; j >= 0; j-- {
			prod := int(num1[i]-'0')*int(num2[j]-'0') + grid[i+j+1]
			grid[i+j+1] = prod % 10 // low digit stays in slot i+j+1
			grid[i+j] += prod / 10  // carry feeds slot i+j
		}
	}
	var out []byte
	for _, d := range grid {
		if len(out) == 0 && d == 0 {
			continue // strip leading zeros
		}
		out = append(out, byte('0'+d))
	}
	return string(out)
}

// LC 43. The product of digit i and digit j ALWAYS lands in slots i+j and
// i+j+1, so accumulate into a length m+n grid and strip leading zeros.
func multiplyStrings(_ num1: String, _ num2: String) -> String {
    if num1 == "0" || num2 == "0" { return "0" }  // or the strip eats everything
    let a = num1.utf8.map { Int($0) - 48 }
    let b = num2.utf8.map { Int($0) - 48 }
    let m = a.count, n = b.count
    var grid = [Int](repeating: 0, count: m + n)
    for i in stride(from: m - 1, through: 0, by: -1) {
        for j in stride(from: n - 1, through: 0, by: -1) {
            let prod = a[i] * b[j] + grid[i + j + 1]
            grid[i + j + 1] = prod % 10  // low digit stays in slot i+j+1
            grid[i + j] += prod / 10  // carry feeds slot i+j
        }
    }
    var out = ""
    for d in grid where !(out.isEmpty && d == 0) {
        out.append(Character(UnicodeScalar(UInt8(48 + d))))
    }
    return out
}

class DetectSquares:
    """LC 2013. Detect Squares.

    Store point counts in a hash map keyed by coordinate, so duplicates
    stack as multiplicities. WHY diagonal-first: the query corner plus
    ONE diagonal partner -- a stored point differing by the same
    NONZERO amount in x and in y -- pins down both remaining corners of
    an axis-aligned square, so each partner contributes the product of
    the three stored counts. Iterating diagonal partners beats trying
    side neighbors, which would leave a whole edge undetermined.
    add is O(1); count is O(p) over distinct stored points.
    """

    def __init__(self) -> None:
        self.point_count: Counter = Counter()

    def add(self, point: list[int]) -> None:
        self.point_count[(point[0], point[1])] += 1

    def count(self, point: list[int]) -> int:
        qx, qy = point
        squares = 0
        for (px, py), diagonal_count in self.point_count.items():
            # need equal NONZERO offsets in x and y to sit on a diagonal
            if px == qx or abs(px - qx) != abs(py - qy):
                continue
            # the diagonal fixes the other two corners: (qx, py) and (px, qy)
            squares += (
                diagonal_count
                * self.point_count[(qx, py)]
                * self.point_count[(px, qy)]
            )
        return squares

// LC 2013. Store point multiplicities in a hash map. For a query corner,
// scan stored points as DIAGONAL partners: a valid partner differs by the
// same nonzero amount in x and y, which pins down the other two corners, so
// the square count contributed is the product of the three counts.
// Coordinates are 0..1000, so x * 1001 + y packs a point into one key.
class DetectSquares {
public:
    void add(vector<int> point) { ++counts[key(point[0], point[1])]; }

    int count(vector<int> point) {
        int px = point[0], py = point[1];
        int total = 0;
        for (const auto& entry : counts) {
            int x = static_cast<int>(entry.first / kBase);
            int y = static_cast<int>(entry.first % kBase);
            if (x == px || abs(x - px) != abs(y - py)) continue;  // need nonzero equal offsets
            auto corner1 = counts.find(key(x, py));
            auto corner2 = counts.find(key(px, y));
            if (corner1 != counts.end() && corner2 != counts.end())
                total += entry.second * corner1->second * corner2->second;
        }
        return total;
    }

private:
    static constexpr long long kBase = 1001;  // coordinates fit in 0..1000
    static long long key(int x, int y) { return x * kBase + y; }
    unordered_map<long long, int> counts;
};

/// LC 2013. Point counts in a hash map; count scans every stored point as
/// a DIAGONAL partner of the query corner -- valid when it differs by the
/// same nonzero amount in x and y. The diagonal fixes the two remaining
/// corners, so the partner's count multiplies with theirs; duplicates are
/// handled for free because counts multiply rather than points enumerate.
pub struct DetectSquares {
    counts: HashMap<(i32, i32), i32>,
}

impl DetectSquares {
    pub fn new() -> Self {
        DetectSquares { counts: HashMap::new() }
    }

    pub fn add(&mut self, point: Vec<i32>) {
        *self.counts.entry((point[0], point[1])).or_insert(0) += 1;
    }

    pub fn count(&self, point: Vec<i32>) -> i32 {
        let (x, y) = (point[0], point[1]);
        let mut total = 0;
        for (&(px, py), &partners) in &self.counts {
            // Diagonal partner: equal nonzero offset in both axes.
            if px == x || (px - x).abs() != (py - y).abs() {
                continue;
            }
            let corner_a = self.counts.get(&(x, py)).copied().unwrap_or(0);
            let corner_b = self.counts.get(&(px, y)).copied().unwrap_or(0);
            total += partners * corner_a * corner_b;
        }
        total
    }
}

/** LC 2013. Map "x,y" -> count; for each query scan stored points as DIAGONAL partners (|dx| === |dy| !== 0) and multiply the two remaining corners' counts. */
export class DetectSquares {
  private countOf = new Map<string, number>();

  add(point: number[]): void {
    const key = `${point[0]},${point[1]}`;
    this.countOf.set(key, (this.countOf.get(key) ?? 0) + 1); // duplicates just raise the multiplicity
  }

  count(point: number[]): number {
    const [qx, qy] = point;
    let total = 0;
    for (const [key, diagCount] of this.countOf) {
      const [x, y] = key.split(",").map(Number);
      // a diagonal partner differs by the same NONZERO amount in x and y (positive area)
      if (x === qx || Math.abs(x - qx) !== Math.abs(y - qy)) continue;
      // the diagonal fixes the other two corners: (qx, y) and (x, qy); counts multiply
      total += diagCount * (this.countOf.get(`${qx},${y}`) ?? 0) * (this.countOf.get(`${x},${qy}`) ?? 0);
    }
    return total;
  }
}

// LC 2013. Count points by coordinate so duplicates stack; each query corner
// pairs with stored DIAGONAL partners (equal nonzero offsets in x and y),
// which pin down the other two corners, contributing the product of counts.
type DetectSquares struct {
	counts map[[2]int]int
}

func newDetectSquares() *DetectSquares {
	return &DetectSquares{counts: make(map[[2]int]int)}
}

func (ds *DetectSquares) add(point []int) {
	ds.counts[[2]int{point[0], point[1]}]++
}

func (ds *DetectSquares) count(point []int) int {
	px, py := point[0], point[1]
	total := 0
	for p, diagonalCount := range ds.counts {
		x, y := p[0], p[1]
		dx, dy := x-px, y-py
		if dx < 0 {
			dx = -dx
		}
		if dy < 0 {
			dy = -dy
		}
		if x == px || dx != dy {
			continue // need equal NONZERO offsets in x and y
		}
		// the diagonal fixes the other two corners: (x, py) and (px, y)
		total += diagonalCount * ds.counts[[2]int{x, py}] * ds.counts[[2]int{px, y}]
	}
	return total
}

// LC 2013. Count points by packed coordinate; for a query corner, each stored
// DIAGONAL partner (equal nonzero offsets in x and y) pins the other two
// corners, contributing the product of the three stored counts.
class DetectSquares {
    var counts: [Int: Int] = [:]

    func key(_ x: Int, _ y: Int) -> Int { x * 1001 + y }  // coordinates fit 0..1000

    func add(_ point: [Int]) {
        counts[key(point[0], point[1]), default: 0] += 1
    }

    func count(_ point: [Int]) -> Int {
        let qx = point[0], qy = point[1]
        var total = 0
        for (packed, diagonalCount) in counts {
            let x = packed / 1001, y = packed % 1001
            if x == qx || abs(x - qx) != abs(y - qy) { continue }  // need nonzero equal offsets
            // the diagonal fixes the other two corners: (qx, y) and (x, qy)
            total += diagonalCount * (counts[key(qx, y)] ?? 0) * (counts[key(x, qy)] ?? 0)
        }
        return total
    }
}