Dashboard/Coding patterns/28. Math and Geometry

CODING PATTERNS · LESSON 28 OF 28 · 129 MIN VIDEO · 43 PROBLEMS

Math and Geometry

Module Progress (0 / 43 Problems Solved)0%
Coding patterns Track (0 / 28 Modules) · Overall 0/80 (0%)0%
⌁

Narrated HD Video Lesson (129 min) · Pro

Pattern Guide + Problem #01 + Checkpoint Quiz #1 are unlocked free below (no login required). Unlock all 80 HD video lessons and all 540 Python problems — or watch our two free sample video lessons first.

PATTERN STUDY GUIDE

Math and Geometry — How the Pattern Works

Math and Geometry patterns replace imprecise floating-point operations, overflow-prone type conversions, and exhaustive step-by-step simulations with exact integer invariants, coordinate projections, and closed-form number-theoretic identities. Maintaining exactness—by cross-multiplying slopes, comparing squared Euclidean distances, projecting axis-aligned shapes onto independent 1D intervals, and propagating carries across base-k digit streams—eliminates precision and boundary bugs. Combined with structural reductions such as GCD/LCM inclusion-exclusion, modular invariants, 45-degree Manhattan rotation, and binary exponentiation, these techniques routinely collapse O(n^3) or O(n^2) geometric searches to O(n log n) or O(n) and reduce O(n) or O(2^n) simulations to O(log n) or O(1).

WHEN TO USE THIS PATTERN
  • 2D point sets asking for collinearity, turn orientation, convex hulls, or circle/polygon containment where floating-point division or square roots risk rounding errors or division-by-zero exceptions.
  • Axis-aligned rectangles, Manhattan distances (|x1 - x2| + |y1 - y2|), or king-move Chebyshev distances (max(|dx|, |dy|)) that decouple into independent 1D intervals or rotated (x + y, x - y) coordinates.
  • Arbitrarily long integers represented as strings, arrays, or linked lists—or signed 32-bit integers with overflow constraints—requiring right-to-left column addition or mod/div digit extraction.
  • Divisibility, repeating patterns, base conversions, prime counting, large exponents, or deterministic game states governed by GCD/LCM, Bézout's identity, sieves, or exponentiation by squaring.
  • Monotonic counting formulas (e.g., multiples up to x) suitable for binary search on the answer, or tiny point sets (n <= 10) where O(n^3) enumeration or O(2^n * n^2) bitmask DP is optimal.
COMMON INTERVIEW PITFALLS
  • Using floating-point division or square roots for exact geometry: dy / dx crashes on vertical lines (dx == 0) and rounds repeating decimals, while math.sqrt(n) loses integer precision on large inputs; prefer cross-multiplication, GCD-normalized integer pairs, dx*dx + dy*dy, and math.isqrt(n).
  • Confusing strict interior vs. boundary inequalities: edge-touching rectangles have zero overlap area (require left < right), whereas points on a circle's boundary count as inside (dx^2 + dy^2 <= r^2) and collinear fence vertices require popping only on cross < 0 rather than cross <= 0.
  • Dropping final carries, mischecking 32-bit overflow, or mishandling zero/negatives: omitting 'or carry' in digit loops fails on 99 + 1, testing result * 10 + digit > limit overflows before the comparison instead of result > (limit - digit) // 10, and n == 0 requires explicit base cases in base conversion, digital roots, and power checks.
  • Overlooking coincident points and 1-based indexing shifts: four identical points yield six zero distances in Valid Square unless dist[0] > 0 is enforced, observer-coincident points have undefined atan2(0, 0) angles in visibility sweeps, and 1-indexed divisor positions require reading nums[i - 1].
2D Cross Product & GCD-Reduced Slope KeyDetermine turn direction or collinearity without division, or group points on the same line using exact hashable slope tuples.
import math

def cross(o, a, b):
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

def canonical_slope(x0, y0, x1, y1):
    dx, dy = x1 - x0, y1 - y0
    g = math.gcd(dx, dy)
    dx, dy = dx // g, dy // g
    if dx < 0 or (dx == 0 and dy < 0):
        dx, dy = -dx, -dy
    return (dy, dx)
Right-to-Left Digit Stream Addition with CarryAdd numbers stored as strings, digit arrays, or linked lists in arbitrary bases without fixed-width integer overflow.
def add_digit_streams(a, b, base=10): 
    i, j, carry, out = len(a) - 1, len(b) - 1, 0, []
    while i >= 0 or j >= 0 or carry:
        total = carry + (a[i] if i >= 0 else 0) + (b[j] if j >= 0 else 0)
        carry, digit = divmod(total, base)
        out.append(digit)
        i, j = i - 1, j - 1
    return out[::-1]
Binary Exponentiation (Exponentiation by Squaring)Compute x^n or apply an associative transformation n times in O(log |n|) steps by halving the exponent each round.
def fast_pow(x, n):
    if n < 0:
        x, n = 1 / x, -n
    result = 1
    while n > 0:
        if n & 1:
            result *= x
        x *= x
        n >>= 1
    return result
🔒 PRO PROBLEMTarget: O(n) time · O(1) space

15. Self Crossing

Pattern Trigger: the path's shape limits hits → check a few recent moves

Problem #01 of every pattern lesson is unlocked free outside the paywall. Unlock all 540 Python 3.14 problems, step-by-step solution editorials, and 80 narrated HD video lessons with Monthly ($69), 3-Month ($149), or Annual ($299) access — or 50% off for verified university students.

Pattern Checkpoint Quizzes

CHECKPOINT QUIZ #1

The first step is one across and two up. The next step is two across and one up. Which way does the path turn?