Math & Miscellaneous

Implement pow(x, n), which calculates x raised to the power n (\(x^n\)), where n is an integer that may be negative.

Multiplying x by itself n times is \(O(n)\) and too slow. Use exponentiation by squaring, which is based on the binary representation of n. Squaring the base each step gives \(x, x^2, x^4, x^8, \dots\), and the result only multiplies in the powers that correspond to a 1 bit of n. For example, \(x^{13} = x^8 \cdot x^4 \cdot x^1\) since \(13 = 1101_2\). The loop runs once per bit, so it takes \(O(\log |n|)\) steps. A negative exponent is handled with \(x^{-n} = (1/x)^n\), by inverting x and negating n first. The iterative version avoids recursion depth entirely.

def myPow(x: float, n: int) -> float:
    if n < 0:
        x = 1 / x
        n = -n

    result = 1.0
    while n:
        if n & 1:      # current bit is set: multiply this power in
            result *= x
        x *= x         # x, x^2, x^4, x^8, ...
        n >>= 1
    return result
    

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string. You must not use any built-in big integer library or convert the inputs to integers directly.

Simulate grade-school multiplication. A number with \(M\) digits times a number with \(N\) digits has at most \(M + N\) digits, so allocate a result array of that length. The product of num1[i] and num2[j] contributes to positions i + j (the carry) and i + j + 1 (the digit). For each pair, add the product to whatever is already stored at res[i + j + 1], keep the last digit there, and add the carry to res[i + j]. Iterating from the right (least significant digits) lets the carry be absorbed by the next iteration. At the end, strip leading zeros. If either input is "0", return "0" immediately.

def multiply(num1: str, num2: str) -> str:
    if num1 == "0" or num2 == "0":
        return "0"

    m, n = len(num1), len(num2)
    res = [0] * (m + n)

    for i in range(m - 1, -1, -1):
        for j in range(n - 1, -1, -1):
            total = int(num1[i]) * int(num2[j]) + res[i + j + 1]
            res[i + j + 1] = total % 10   # digit stays at this position
            res[i + j] += total // 10     # carry goes to the next position

    return "".join(map(str, res)).lstrip("0")
    

You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees clockwise. You must rotate the image in-place, which means you have to modify the input matrix directly without allocating another matrix.

A 90 degree clockwise rotation is the combination of two simple in-place operations: transpose the matrix (swap matrix[i][j] with matrix[j][i]), then reverse each row. The transpose turns rows into columns, and reversing each row puts those columns in the correct clockwise order. For a counter-clockwise rotation, reverse each row first or reverse the order of the rows after transposing instead. Every element is touched a constant number of times, which is optimal since every cell must be read.

def rotate(matrix: list[list[int]]) -> None:
    n = len(matrix)

    # Transpose: swap across the main diagonal
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

    # Reverse each row
    for row in matrix:
        row.reverse()
    

Given an m x n matrix, return all elements of the matrix in spiral order, starting at the top-left corner and moving clockwise.

Keep four boundaries: top, bottom, left and right. Each loop iteration peels off one layer in four moves: left to right along the top row, top to bottom along the right column, right to left along the bottom row, and bottom to top along the left column. After each move, shrink the matching boundary. The bottom row and left column moves need a check (top <= bottom and left <= right), because after the first two moves a single remaining row or column would otherwise be traversed twice. Every cell is visited exactly once, and no visited matrix is needed.

def spiralOrder(matrix: list[list[int]]) -> list[int]:
    res = []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1

    while top <= bottom and left <= right:
        # Left to right along the top row
        for c in range(left, right + 1):
            res.append(matrix[top][c])
        top += 1

        # Top to bottom along the right column
        for r in range(top, bottom + 1):
            res.append(matrix[r][right])
        right -= 1

        # Right to left along the bottom row (if a row remains)
        if top <= bottom:
            for c in range(right, left - 1, -1):
                res.append(matrix[bottom][c])
            bottom -= 1

        # Bottom to top along the left column (if a column remains)
        if left <= right:
            for r in range(bottom, top - 1, -1):
                res.append(matrix[r][left])
            left += 1

    return res