Math Cheatsheet for Algorithms

$$d = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2} \qquad d \le r \iff d^2 \le r^2$$

The Euclidean distance d is the straight-line distance between two points. When you only compare distances, compare d * d instead. Squaring keeps the order of non-negative numbers. The squared distance between two points with integer coordinates is an integer, so it has no rounding error. A point is inside or on a circle of radius r exactly when its squared distance to the centre is at most r * r.

LeetCode problems that use it

• K Closest Points to Origin (LC 973): order the points by squared distance to the origin.
• Queries on Number of Points Inside a Circle (LC 1828): count the points with squared distance at most r * r for each query circle.
• Count Lattice Points Inside a Circle (LC 2249): test every lattice point near each circle with the squared-distance check.

$$d_M = |x_1 - x_2| + |y_1 - y_2|$$

The Manhattan distance is the number of steps on a grid when every step moves one cell up, down, left or right. It is the horizontal difference plus the vertical difference. Use it when a problem defines the cost between two points this way.

LeetCode problems that use it

• Min Cost to Connect All Points (LC 1584): the cost of an edge between two points is their Manhattan distance.
• Matrix Cells in Distance Order (LC 1030): sort the cells by Manhattan distance to the given cell.

$$d_C = \max(|x_1 - x_2|,\ |y_1 - y_2|)$$

Suppose one move changes x by at most 1 and y by at most 1, so a move can be diagonal. Then the fewest moves between two points is the larger of the two differences. Each diagonal move reduces both differences by 1, and straight moves cover what remains of the larger one.

LeetCode problems that use it

• Minimum Time Visiting All Points (LC 1266): the time between two consecutive points is their Chebyshev distance.

$$|x_1 - x_2| + |y_1 - y_2| = \max(|u_1 - u_2|,\ |v_1 - v_2|), \quad u = x + y,\ v = x - y$$

The substitution turns every Manhattan distance into a Chebyshev distance between the new points (u, v). So the largest Manhattan distance over all pairs is max(max(u) - min(u), max(v) - min(v)). That takes O(n) time instead of checking all n² pairs. The same idea works with more coordinates. A sum of absolute differences equals the largest signed sum over every choice of + and − signs.

LeetCode problems that use it

• Minimize Manhattan Distances (LC 3102): remove one point and find the smallest possible largest distance, using the sorted u and v values.
• Maximum of Absolute Value Expression (LC 1131): the same identity with three terms, so try each of the sign patterns.

$$\operatorname{cross}(O, A, B) = (A_x - O_x)(B_y - O_y) - (A_y - O_y)(B_x - O_x)$$

The sign of cross(O, A, B) tells which way the path from O to A to B turns. A positive value is a counter-clockwise (left) turn. A negative value is a clockwise (right) turn. Zero means the three points are on one straight line. With integer coordinates the result is exact, because there is no division.

LeetCode problems that use it

• Check If It Is a Straight Line (LC 1232): every point must give a cross product of 0 with the first two points.
• Valid Boomerang (LC 1037): three points form a boomerang when their cross product is not 0.
• Convex Polygon (LC 469): a polygon is convex when all its nonzero turns have the same sign.

Card that teaches this method: Cross Product

$$\text{key}(dx, dy) = \left(\frac{dx}{g}, \frac{dy}{g}\right), \quad g = \gcd(|dx|, |dy|)$$

Two point pairs have the same slope exactly when their reduced direction (dx, dy) is the same. Divide both differences by their gcd. Then fix the sign so that dx > 0, or dx == 0 and dy > 0. The result is a tuple of integers that you can use as a dictionary key, with no floating-point slope.

LeetCode problems that use it

• Max Points on a Line (LC 149): for each anchor point, count the other points by slope key.

Card that teaches this method: Canonical Key

$$A = \frac{1}{2}\left|\sum_{i=0}^{n-1} \left(x_i\, y_{i+1} - x_{i+1}\, y_i\right)\right|, \quad (x_n, y_n) = (x_0, y_0)$$

List the vertices in order around the polygon, either clockwise or counter-clockwise. The sum is twice the signed area. It is positive for counter-clockwise order and negative for clockwise order. For a triangle the formula is half the absolute cross product of its three corners.

LeetCode problems that use it

• Largest Triangle Area (LC 812): try every triple of points and take the largest triangle area.

Card that teaches this method: Cross Product

$$\text{while } \operatorname{cross}(h_{k-1}, h_k, p) < 0: \ \text{remove } h_k$$

Sort the points by (x, y). Build the lower chain from left to right, then the upper chain from right to left. Before adding point p, remove the chain's last point while the chain would turn clockwise at it. The test < 0 keeps points that are on an edge of the hull, which Erect the Fence (LC 587) asks for. The test <= 0 keeps only the corners. Sorting makes the whole method O(n log n).

LeetCode problems that use it

• Erect the Fence (LC 587): return every tree on the fence, including trees in the middle of a straight side.

Card that teaches this method: Cross Product

$$w = \max(0,\ \min(x_2, x_4) - \max(x_1, x_3)), \quad h = \max(0,\ \min(y_2, y_4) - \max(y_1, y_3))$$

The first rectangle has bottom-left corner (x1, y1) and top-right corner (x2, y2). The second has corners (x3, y3) and (x4, y4). On each axis, the overlap is the smaller end minus the larger start, or 0 when that is negative. The overlap area is w * h. The area the two rectangles cover together is the sum of their areas minus w * h.

LeetCode problems that use it

• Rectangle Overlap (LC 836): the rectangles overlap only when w > 0 and h > 0, so sharing an edge does not count.
• Rectangle Area (LC 223): the covered area is the two areas minus the overlap.
• Find the Largest Area of Square Inside Two Rectangles (LC 3047): the largest square inside an overlap has side min(w, h).

$$p_x = \min(\max(x_c, x_1), x_2), \quad p_y = \min(\max(y_c, y_1), y_2), \quad (p_x - x_c)^2 + (p_y - y_c)^2 \le r^2$$

The point of the rectangle nearest to the centre (xc, yc) is the centre clamped into the rectangle on each axis. The circle and the rectangle share at least one point exactly when that nearest point (px, py) is within distance r of the centre.

LeetCode problems that use it

• Circle and Rectangle Overlapping (LC 1401): clamp the centre into the rectangle and compare squared distances.

$$\text{left turn: } (dx, dy) \to (-dy, dx) \qquad \text{right turn: } (dx, dy) \to (dy, -dx)$$

Store the facing direction as a vector (dx, dy). A 90-degree turn swaps the two parts and negates one of them, so no angle arithmetic is needed. Four turns in the same direction give back the original vector.

LeetCode problems that use it

• Robot Bounded In Circle (LC 1041): after one pass the robot stays in a bounded area when it is back at the start or no longer faces north.
• Spiral Matrix III (LC 885): walk the spiral by turning right with (dr, dc) -> (dc, -dr).

$$\theta = \operatorname{atan2}(y - y_0,\ x - x_0) \in [-180^\circ, 180^\circ]$$

math.atan2(dy, dx) returns the direction from (x0, y0) to (x, y) in radians, and it handles every quadrant and dx == 0. Convert it with math.degrees. To count points inside a viewing angle that may cross the 180-degree boundary, sort the angles and append each angle plus 360. Then, for each angle as the start, use bisect_right to count the angles that are at most the viewing angle after it.

LeetCode problems that use it

• Maximum Number of Visible Points (LC 1610): sort the angles, append each plus 360, and count the angles within angle degrees after each start angle.

$$a = |30h - 5.5m| \quad (h \bmod 12), \qquad \text{answer} = \min(a,\ 360 - a)$$

The minute hand moves 6 degrees per minute. The hour hand moves 30 degrees per hour plus 0.5 degrees per minute. Their difference is 30h + 0.5m - 6m = 30h - 5.5m. The smaller angle between the hands is a or 360 - a, whichever is smaller.

LeetCode problems that use it

• Angle Between Hands of a Clock (LC 1344): apply the formula and take the smaller of the two angles.

$$\{d^2(p_i, p_j)\}_{i<j} = \{s, s, s, s, 2s, 2s\}, \quad s > 0$$

Four points have six pairwise distances. They form a square exactly when the six squared distances take only two values, a nonzero side value s that appears four times and a diagonal value 2s that appears twice. Squared distances keep the test in integers.

LeetCode problems that use it

• Valid Square (LC 593): sort or count the six squared distances.

$$A(h) = \sum_i l_i \cdot \min\!\left(l_i,\ \max(0,\ h - y_i)\right)$$

Square i has its bottom edge at yi and side li. The part of the square below the line y = h has height h - yi, clamped to the range 0 to li. The function A(h) never decreases as h grows. So a binary search on real numbers finds the lowest h where A(h) reaches half of the total area.

LeetCode problems that use it

• Separate Squares I (LC 3453): find the lowest h where the area below the line is half of the total area. An area covered by several squares counts once for each of them.

Card that teaches this method: Continuous Bisection

$$\frac{hi - lo}{2^k} \le \varepsilon \iff k \ge \log_2 \frac{hi - lo}{\varepsilon}$$

Each round halves the interval from lo to hi. For hi - lo = 1e9 and a tolerance eps = 1e-5, you need k = 47 rounds, because $\log_2(10^{14}) \approx 46.5$. Prefer a fixed number of rounds to the loop while hi - lo > eps. That loop never ends when eps is smaller than the gap between two neighbouring floats near the answer. In that case mid equals lo or hi, and the interval stops shrinking.

LeetCode problems that use it

• Separate Squares I (LC 3453): the answer must be within 10^-5, so a fixed count of rounds is enough.
• Minimize Max Distance to Gas Station (LC 774): binary-search the smallest possible largest gap D on real numbers.

Card that teaches this method: Continuous Bisection

$$\lfloor \sqrt{n} \rfloor = \max\{x \ge 0 : x^2 \le n\}$$

math.isqrt(n) returns this value exactly, for an integer of any size. int(math.sqrt(n)) first converts n to a float, and that can round up for large n. It also solves quadratic limits. For example, the largest k with k(k + 1)/2 <= n is (isqrt(8n + 1) - 1) // 2.

LeetCode problems that use it

• Sqrt(x) (LC 69): binary-search the largest r with r * r <= x. math.isqrt(x) gives the same value, but the problem expects you to compute it yourself.
• Valid Perfect Square (LC 367): binary-search the largest x with x * x <= num, then check whether x * x == num. The problem does not allow a built-in square root such as math.isqrt.
• Arranging Coins (LC 441): the number of complete rows is the largest k with k(k + 1)/2 <= n.

Card that teaches this method: Upper Bound

$$\gcd(a, b) = \gcd(b,\ a \bmod b), \qquad \gcd(a, 0) = a$$

Every common divisor of a and b also divides a mod b, so the pair (b, a mod b) has the same gcd. The second number shrinks quickly, so the loop runs O(log min(a, b)) times. Python has math.gcd, and since Python 3.9 it accepts any number of arguments.

LeetCode problems that use it

• Find Greatest Common Divisor of Array (LC 1979): the gcd of the smallest and the largest value.
• Greatest Common Divisor of Strings (LC 1071): when str1 + str2 == str2 + str1, the answer is the prefix of length gcd(len(str1), len(str2)).
• X of a Kind in a Deck of Cards (LC 914): a valid split exists when the gcd of all the value counts is at least 2.
• Number of Subarrays With GCD Equal to K (LC 2447): extend each subarray to the right while its running gcd is still a multiple of k.
• Simplified Fractions (LC 1447): a fraction n / d is in lowest terms exactly when gcd(n, d) == 1.

Card that teaches this method: Euclid's GCD

$$\operatorname{lcm}(a, b) = \frac{a}{\gcd(a, b)} \cdot b$$

The lcm is the smallest positive number that both a and b divide. Divide before you multiply, so the intermediate value stays small in languages with fixed-size integers. Python has math.lcm since Python 3.9.

LeetCode problems that use it

• Smallest Even Multiple (LC 2413): the answer is lcm(2, n).
• Nth Magical Number (LC 878): numbers divisible by both a and b are the multiples of lcm(a, b).
• Ugly Number III (LC 1201): the counting formula needs the lcm of every pair and of all three numbers.

$$a x + b y = c \text{ has integer solutions } x, y \iff \gcd(a, b) \text{ divides } c$$

Every integer combination a * x + b * y is a multiple of gcd(a, b). Every multiple of gcd(a, b) can be written that way. For two jugs, the amounts you can measure are the multiples of the gcd that also fit into both jugs together.

LeetCode problems that use it

• Water and Jug Problem (LC 365): the target is reachable when it is at most x + y and a multiple of gcd(x, y).
• Check If It Is a Good Array (LC 1250): some combination of the numbers equals 1 exactly when the gcd of all of them is 1.

$$\text{for each prime } p \le \sqrt{n}: \text{ mark } p^2,\ p^2 + p,\ p^2 + 2p, \ldots \text{ as composite} \qquad O(n \log \log n)$$

A composite number below n has a prime factor at most its square root, so marking stops at p * p >= n. Marking starts at p * p because every smaller multiple of p has a smaller prime factor and is already marked.

LeetCode problems that use it

• Count Primes (LC 204): count the primes strictly less than n.
• Prime Arrangements (LC 1175): with P primes up to n, the answer is P! * (n - P)! modulo 109 + 7.
• Closest Prime Numbers in Range (LC 2523): sieve up to right, then compare neighbouring primes in the range.

Card that teaches this method: Sieve of Eratosthenes

$$\text{spf}[x] = \text{smallest prime dividing } x, \qquad x = \text{spf}[x] \cdot \frac{x}{\text{spf}[x]}$$

One sieve pass stores the smallest prime factor spf[x] of every x up to a limit. To factor x, divide by spf[x] until x is 1. Each division at least halves x, so factoring takes O(log x) steps after the sieve.

LeetCode problems that use it

• Largest Component Size by Common Factor (LC 952): join every number with its prime factors in a union-find.
• GCD Sort of an Array (LC 1998): two values can swap when they share a prime factor, so group them by prime factors.

$$d \mid n \implies \frac{n}{d} \mid n, \qquad \min\!\left(d, \frac{n}{d}\right) \le \sqrt{n}$$

Divisors come in pairs (d, n // d), and the smaller one of each pair is at most √n. So a loop over d while d * d <= n finds every divisor in O(√n) time. For prime factors, divide out each d completely. Whatever is left above 1 at the end is one last prime factor.

LeetCode problems that use it

• The kth Factor of n (LC 1492): list the divisors in increasing order and return the k-th one.
• Four Divisors (LC 1390): stop a number as soon as it has more than four divisors.
• Distinct Prime Factors of Product of Array (LC 2521): collect the distinct prime factors of every number.
• Smallest Value After Replacing With Sum of Prime Factors (LC 2507): replace n by the sum of its prime factors until it stops changing.

$$\#\{d : d \mid n\} \text{ is odd} \iff n = k^2$$

Divisors of n come in pairs (d, n // d). The two members of a pair are different unless d * d == n. So the count is odd exactly when n is a perfect square. Between 1 and n there are isqrt(n) perfect squares.

LeetCode problems that use it

• Bulb Switcher (LC 319): bulb i is toggled once per divisor of i, so it ends on when i is a perfect square.

$$(a + b) \bmod M = ((a \bmod M) + (b \bmod M)) \bmod M, \qquad (a \cdot b) \bmod M = ((a \bmod M)(b \bmod M)) \bmod M$$

When a problem asks for the answer modulo M = 109 + 7, reduce after every addition and multiplication. Python integers never overflow, but a very large integer makes each operation slower. Division does not follow these rules. It needs the modular inverse, described in the entry on dividing modulo a prime. In Python, a % M is always in the range 0 to M - 1 for a positive M, even when a is negative. C++ and Java return a negative remainder for a negative a.

LeetCode problems that use it

• Number of Dice Rolls With Target Sum (LC 1155): reduce every sum of ways modulo 109 + 7.
• Concatenation of Consecutive Binary Numbers (LC 1680): shift the result left by the bit length of each new number, then reduce.
• Count Good Numbers (LC 1922): multiply the powers of 5 and 4 modulo 109 + 7.

$$\sum_{t=i}^{j-1} a_t = P_j - P_i \equiv 0 \pmod{k} \iff P_i \bmod k = P_j \bmod k$$

P[j] is the sum of the first j values, with P[0] = 0. A subarray sum is a difference of two prefix sums. It is divisible by k exactly when the two prefix sums have the same remainder. So count equal remainders in a dictionary while you scan the array.

LeetCode problems that use it

• Subarray Sums Divisible by K (LC 974): count the pairs of equal prefix remainders.
• Continuous Subarray Sum (LC 523): store the first index of each remainder, and require a length of at least 2.

Card that teaches this method: Prefix Sum Map

$$a^n = \begin{cases} \left(a^{n/2}\right)^2 & n \text{ even} \\ a \cdot a^{n-1} & n \text{ odd} \end{cases}$$

Read the bits of n from the lowest. Square the base once per bit, and multiply the result by the base when the bit is 1. That takes O(log n) multiplications instead of n. Python's pow(a, n, m) does the same with a modulus.

LeetCode problems that use it

• Pow(x, n) (LC 50): square the base and halve the exponent, and for a negative n use 1 / x as the base.
• Super Pow (LC 372): the exponent is given as a digit list, so combine a^(10 * e + d) = (a^e)^10 * a^d.
• Count Good Numbers (LC 1922): the answer is 5^ceil(n/2) * 4^floor(n/2) modulo 109 + 7.

Card that teaches this method: Fast Power

$$a^{-1} \equiv a^{M-2} \pmod{M} \quad \text{for prime } M \text{ that does not divide } a, \qquad \binom{n}{k} \equiv n! \cdot (k!)^{-1} \cdot ((n-k)!)^{-1} \quad (n < M)$$

Fermat's little theorem gives a^(M-1) ≡ 1 modulo a prime M, so a^(M-2) is the inverse of a. Multiplying by it replaces division. Since Python 3.8, pow(a, -1, M) computes the inverse directly. Precompute factorials and inverse factorials once, and every binomial coefficient costs O(1).

LeetCode problems that use it

• Number of Ways to Reach a Position After Exactly k Steps (LC 2400): with distance d = |endPos - startPos|, the answer is C(k, (k + d) / 2) when k + d is even and d <= k.
• Count Ways to Build Rooms in an Ant Colony (LC 1916): the count is n! divided by the product of all subtree sizes, so divide with inverses.

$$\operatorname{dr}(n) = \begin{cases} 0 & n = 0 \\ 1 + (n - 1) \bmod 9 & n > 0 \end{cases}$$

A number and its digit sum have the same remainder modulo 9, because 10 ≡ 1 modulo 9. Summing digits until one digit remains therefore gives the remainder modulo 9, with 9 in place of 0 for a positive n.

LeetCode problems that use it

• Add Digits (LC 258): return the digital root in O(1) time.

$$n = \sum_i d_i\, b^i, \qquad (n, d_0) = \left(\left\lfloor n / b \right\rfloor,\ n \bmod b\right) \text{ repeated}$$

Repeated divmod(n, b) produces the digits from the least significant one, so reverse them at the end. For a negative base such as −2, a remainder can come out negative. Then add |b| to the remainder and add 1 to the quotient. For a negative number in hexadecimal as a 32-bit value, first take n & 0xFFFFFFFF, which is its two's complement.

LeetCode problems that use it

• Base 7 (LC 504): repeated divmod by 7, with the sign added back.
• Convert a Number to Hexadecimal (LC 405): convert num & 0xFFFFFFFF so a negative number becomes its two's complement.
• Convert to Base -2 (LC 1017): divide by −2 and fix every negative remainder.

$$n = \sum_i c_i \cdot 26^i, \quad c_i \in \{1, \ldots, 26\} \qquad \text{title: } (n, c) = \operatorname{divmod}(n - 1, 26)$$

Column titles have no zero digit. A is 1 and Z is 26. So subtract 1 before each divmod(n, 26), and read the remainder as 0 for A up to 25 for Z. For the reverse direction, n = n * 26 + (letter value) for each letter from the left.