Topic 18: Math & Geometry

Key-Intuition: Math problems focus on number theory, geometry transformations, and arithmetic properties involving grids or shapes.

Canonical Questions #

Matrix Rotations and Traversals #

• Rotate matrices, spiral and zigzag traversal, layer-by-layer processing

Problems #

1. Rotate Image (48)

   This question is ALL about being precise in the index accesses. We need to do swaps of cell values so source and destination cells as all we need to define properly.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

   # verbose, with clearer extra variables class Solution: def rotate(self, matrix: List[List[int]]) -> None: """ Do not return anything, modify matrix in-place instead. """ n = len(matrix) for layer in range(n // 2): # define layer boudaries: first = layer last = n - layer - 1 # items in the "buffer" for i in range(first, last): # we read them all offset = i - first top = matrix[first][i] left = matrix[last - offset][first] bottom = matrix[last][last - offset] right = matrix[i][last] # then we write them, the 90degree rotation matrix[first][i] = left matrix[last - offset][first] = bottom matrix[last][last - offset] = right matrix[i][last] = top # cleaned up class Solution: def rotate(self, matrix: List[List[int]]) -> None: """ Do not return anything, modify matrix in-place instead. """ n = len(matrix) for layer in range(n // 2): first = layer last = n - 1 - layer for i in range(first, last): offset = i - first temp = matrix[first][i] # save top # perform 4-way swap clockwise matrix[first][i] = matrix[last - offset][first] # left to top matrix[last - offset][first] = matrix[last][last - offset] # bottom to left matrix[last][last - offset] = matrix[i][last] # right to bottom matrix[i][last] = temp # top to right

   Code Snippet 1: Rotate Image (48) – swapping cell values

   There’s another approach, which is to just do a transpose then reverse the rows. That’s pretty straightforward too:

   1 2 3 4 5 6 7 8 9 10 11

   class Solution: def rotate(self, matrix: List[List[int]]) -> None: n = len(matrix) # Transpose 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()

   Code Snippet 2: Rotate Image (48) – transpose then reverse rows
   Pattern Extraction

   Core Insight: 90-degree clockwise rotation = transpose the matrix (swap rows and columns), then reverse each row. Alternatively: reverse rows top-to-bottom, then transpose. Pattern Name: Matrix Rotation via Transpose + Reverse Canonical Section: Math & Geometry > Matrix Transformations Recognition Signals:

   • “Rotate matrix 90 degrees” in-place
   • Square matrix (\(n \times n\))
   • \(O(1)\) extra space (in-place)

   Anti-Signals:

   • Non-square matrix – can’t rotate in-place (dimensions change)
   • Rotate by 180 – reverse each row AND reverse row order (simpler than 90)
   • Rotate by 270 (or -90) – transpose then reverse each column (or reverse then transpose)

   Decision Point: 90 CW = transpose + reverse rows. 90 CCW = reverse rows + transpose (or transpose + reverse columns). 180 = two 90 rotations, or reverse both dimensions.

   Pitfalls and Misconceptions

   1. Trap: Transposing the full matrix instead of just the upper triangle. Why: Swapping matrix[i][j] and matrix[j][i] for ALL \(i, j\) swaps each pair twice, returning to the original. Correction: Only swap where j > i (upper triangle): for i in range(n): for j in range(i+1, n).
   2. Trap: Confusing clockwise vs counter-clockwise rotation. Why: CW = transpose then reverse rows. CCW = transpose then reverse columns. Mixing them up produces the wrong rotation. Correction: Test on a 2x2 example: [[1,2],[3,4]] CW should give [[3,1],[4,2]].
   Problem Mutations

   1. What if the rotation were 180 degrees? (stress-tests: 90 degrees) Reverse each row, then reverse the row order. Or apply 90-degree rotation twice.
   2. What if the matrix were not square? (stress-tests: square assumption) Can’t rotate in-place because the result has different dimensions (\(m \times n\) becomes \(n \times m\)). Need a new matrix.
   3. What if you needed to rotate a specific layer/ring only? (stress-tests: full rotation) Process the outer ring, then recurse on the inner submatrix. The four-corner swap pattern processes one layer at a time.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Standardised annotation dropdowns for Rotate Image generated via batch canonical enrichment pass. Review against personal solving experience and adjust.
   

2. Spiral Matrix (54)

   Again, we just need to be careful about the boundaries and we’re good. The exit cases matter too.

   Be consistent about the intervals (closed, open? closed, closed?) and just put some comments to avoid getting confused about the indices.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

   from typing import List class Solution: def spiralOrder(self, matrix: List[List[int]]) -> List[int]: if not matrix or not matrix[0]: return [] rows, cols = len(matrix), len(matrix[0]) left, right = 0, cols - 1 top, bottom = 0, rows - 1 result = [] while left <= right and top <= bottom: # Traverse top row from left to right for col in range(left, right + 1): result.append(matrix[top][col]) top += 1 # Traverse right column from top to bottom for row in range(top, bottom + 1): result.append(matrix[row][right]) right -= 1 if top <= bottom: # Traverse bottom row from right to left for col in range(right, left - 1, -1): result.append(matrix[bottom][col]) bottom -= 1 if left <= right: # Traverse left column from bottom to top for row in range(bottom, top - 1, -1): result.append(matrix[row][left]) left += 1 return result

   Code Snippet 3: Spiral Matrix (54)
   Pattern Extraction

   Core Insight: Simulate the spiral by maintaining four boundaries (top, bottom, left, right) and traversing: right across top, down right side, left across bottom, up left side. Shrink boundaries after each traversal. Pattern Name: Layer-by-Layer Boundary Peeling Canonical Section: Math and Geometry > Matrix Traversals Recognition Signals:

   • “Traverse matrix in spiral order”
   • Four-directional traversal with shrinking boundaries
   • Process one layer at a time

   Anti-Signals:

   • Need to generate a spiral matrix – same traversal but write instead of read. Connects to LC 59

   Decision Point: Spiral traversal = four loops per layer with boundary checks after each direction.

   Pitfalls and Misconceptions

   1. Trap: Not checking boundaries after each direction change. Why: For non-square matrices, the inner layer might be a single row or column. Without checks, you traverse it twice. Correction: After traversing right, check if top > bottom: break. After traversing down, check if left > right: break.
   Problem Mutations

   1. What if you needed to fill a matrix in spiral order? (stress-tests: read vs write) Same traversal, write incrementing values. Connects to LC 59.
   2. What if the spiral went counter-clockwise? (stress-tests: direction) Swap the traversal order: down, right, up, left (or adjust boundary shrinking accordingly).
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Standardised annotation dropdowns for Spiral Matrix generated via batch canonical enrichment pass.
   

3. Set Matrix Zeroes (73)

   This is pretty nifty, we basically use the first row and first column to track what we need to set to zero, then after sweeping through the cells, we can just set the zeros in one fell swoop. Keep in mind that we should see this as 3 phases: A: track if the first row / first column has zeroes (to be done as the final step) B: use the first row / first column as markers, then mark the inner cells correctly after visiting each cell and tracking using the markers C: zeroing the first row / first column if required.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

   class Solution: def setZeroes(self, matrix: List[List[int]]) -> None: R, C = len(matrix), len(matrix[0]) first_row_zero = any(matrix[0][c] == 0 for c in range(C)) first_col_zero = any(matrix[r][0] == 0 for r in range(R)) # Use first row and column as markers for r in range(1, R): for c in range(1, C): if matrix[r][c] == 0: matrix[r][0] = 0 matrix[0][c] = 0 # Zero rows based on first column for r in range(1, R): if matrix[r][0] == 0: for c in range(1, C): matrix[r][c] = 0 # Zero columns based on first row for c in range(1, C): if matrix[0][c] == 0: for r in range(1, R): matrix[r][c] = 0 # Zero first row if needed if first_row_zero: for c in range(C): matrix[0][c] = 0 # Zero first column if needed if first_col_zero: for r in range(R): matrix[r][0] = 0

   Code Snippet 4: Set Matrix Zeroes (73)
   Pattern Extraction

   Core Insight: Use the first row and first column as markers. If matrix[i][j] = 0=, mark matrix[i][0] = 0 and matrix[0][j] = 0. Then sweep to zero rows/columns. Two extra booleans track the first row/column. Pattern Name: In-Place Marker Rows/Columns Canonical Section: Math and Geometry > Matrix Transformations Recognition Signals:

   • “Set entire row and column to zero” for each zero cell
   • \(O(1)\) extra space required
   • In-place modification using the matrix itself

   Anti-Signals:

   • \(O(m + n)\) space is fine – use separate boolean arrays (simpler)

   Decision Point: \(O(1)\) space forces using the matrix’s own first row/column as markers.

   Pitfalls and Misconceptions

   1. Trap: Zeroing out markers before using them. Why: If you zero the first row early, you lose the column markers. Correction: Process the interior first, then the first row and column last.
   2. Trap: Forgetting separate boolean flags for first row and column. Why: matrix[0][0] can only serve as marker for one of them. Correction: Use matrix[0][0] for columns and a separate first_row_zero boolean for the first row.
   Problem Mutations

   1. What if the constraint were \(O(m + n)\) space? (stress-tests: \(O(1)\) space) Use separate boolean arrays for rows and columns. Much simpler.
   2. What if you needed to set to a specific value (not zero)? (stress-tests: zero-specific) Same algorithm but the marker value must be distinguishable from the fill value.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Standardised annotation dropdowns for Set Matrix Zeroes generated via batch canonical enrichment pass.
   

4. Sort Matrix by Diagonals (3446)

   This one is all about using the diagonal trick (represent by the y intercept, (row - col)) and sorting within. The input sizes allows us to tolerate this \(O(n^{2} \log n)\) solution

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

   class Solution: def sortMatrix(self, grid: List[List[int]]) -> List[List[int]]: """ It's about uniquely identifying diagonals, then doing sorting within it. looks like a linear approach might work based on the input sizes uniquely identifying a diagonal: using the "y intercepts": row - col """ n = len(grid) if n <= 1: return grid for diagonal in range(-(n - 1), n): # NOTE: valid diagonals are from -(n - 1) to +(n - 1) inclusive # diagonal is_reverse = diagonal < 0 sort_candidates = [] # (val) for row in range(0, n): if 0 <= (col:=(row - diagonal)) < n: sort_candidates.append(grid[row][col]) sorted_candidates = sorted(sort_candidates, reverse=(is_reverse)) for row in range(0, n): if 0 <= (col:=(row - diagonal)) < n: grid[row][col] = sorted_candidates.pop() return grid

   Code Snippet 5: Sort Matrix by Diagonals (3446)
   Pattern Extraction

   Core Insight: Each diagonal is identified by row - col (constant along a diagonal). Collect elements per diagonal, sort them, place back. Pattern Name: Diagonal Extraction + Sort + Replacement Canonical Section: Math & Geometry > Matrix Traversals Recognition Signals:

   • “Sort each diagonal” of a matrix
   • Diagonals identified by row - col

   Anti-Signals:

   • Sort rows or columns – simpler, no diagonal extraction

   Decision Point: Group elements by row - col, sort each group, place back in order.

   Pitfalls and Misconceptions

   1. Trap: Not using row - col as the diagonal key. Why: Other indexing schemes (like row + col for anti-diagonals) extract the wrong diagonals. Correction: row - col for top-left to bottom-right diagonals. row + col for anti-diagonals.
   Problem Mutations

   1. What if you needed to sort anti-diagonals? (stress-tests: main diagonals) Use row + col as the key instead of row - col.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Batch annotation for Sort Matrix by Diagonals.
   

Number Theory Computations #

• GCD, LCM, modular arithmetic, prime testing, factorization, integer properties

Problems #

1. TODO GCD of Strings (1071)

2. Happy Number (202)

   This question is just about “cycle detection” within a process that we do. A naive approach does things by using a history set. An optimal one would optimise space by going through a floyd’s tortoise and hare method and check for cycles (or end state of 1 if happy)

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

   # m1: tortoise and hare class Solution: def isHappy(self, n: int) -> bool: def next_num(num): return sum(int(s) ** 2 for s in str(num)) slow = n fast = next_num(n) while fast != 1 and slow != fast: slow = next_num(slow) fast = next_num(next_num(fast)) return fast == 1 # m2: set for history class Solution: def isHappy(self, n: int) -> bool: visited = set() while n != 1: copy = n next_n = 0 while copy > 0: next_n += (copy % 10) ** 2 # GOTCHA: this has to be an integer division, not a float division. This was a source of error copy //= 10 if next_n in visited: # we have found a loop: return False visited.add(next_n) n = next_n return True

   Code Snippet 6: Happy Number (202)
   Pattern Extraction

   Core Insight: The sequence of digit-square-sums either reaches 1 or enters a cycle. Use Floyd’s cycle detection (tortoise and hare) or a hash set to detect cycles. Pattern Name: Cycle Detection in Implicit Sequence Canonical Section: Math and Geometry > Number Theory Computations Recognition Signals:

   • Repeated application of a function produces a sequence
   • Sequence either converges or cycles
   • Need to detect convergence vs cycle

   Anti-Signals:

   • The sequence is guaranteed to converge – no cycle detection needed
   • The function isn’t well-defined (stochastic, non-deterministic) – cycle detection doesn’t apply

   Decision Point: Floyd’s tortoise and hare applies to ANY sequence defined by repeated function application. Same principle as linked list cycle detection.

   Pitfalls and Misconceptions

   1. Trap: Not recognising that this is a cycle detection problem. Why: The “happy number” framing obscures the structural equivalence to linked list cycle detection. Correction: Define next(n) = sum of squared digits. The sequence n, next(n), next(next(n)), ... either hits 1 or cycles. Use Floyd’s or a set.
   2. Trap: Using a set without considering memory for very long chains. Why: The set grows with each step. Floyd’s uses \(O(1)\) space. Correction: Floyd’s: slow = next(n), fast = next(next(n)). If they meet at 1, happy. If they meet elsewhere, not happy.
   Problem Mutations

   1. What if you needed to find the cycle length? (stress-tests: boolean vs measurement) After detection, keep one pointer stationary and count steps until they meet again.
   2. What if the function were different (e.g., sum of cubes)? (stress-tests: specific function) Same cycle detection algorithm. The function definition changes but the detection logic is identical.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Standardised annotation dropdowns for Happy Number generated via batch canonical enrichment pass.
   

3. Pow(x, n) (50)

   This question is a about fast exponentiation, we need to handle negative indices and odd indices. Negative indices can be made positive by using the reciprocal of a number. Odd indices can be made even by multiplying it (which effectively decrements the index from an odd to an even numbered index.)

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

   # ITERATIVE FAST BINARY EXPONENTIATION class Solution: def myPow(self, x: float, n: int) -> float: # iterative fast exponentiation: N = n # N is the running exponent that we shall be using if N < 0: # if negative exponent, then make it positive, use the reiprocal for the operand x = 1 / x N = -N result = 1.0 curr_product = x while N > 0: # if first bit is 1 / it's odd: if N % 2 == 1: result *= curr_product # decrement so that it's even and we can power this curr_product *= curr_product N //= 2 # half the exponent return result # RECURSIVE FAST BINARY EXPONENTIATION class Solution: def myPow(self, x: float, n: int) -> float: if n == 0: return 1.0 if n < 0: return 1 / self.myPow(x, -n) half = self.myPow(x, n // 2) if n % 2 == 0: return half * half else: return half * half * x

   Code Snippet 7: Pow(x, n) (50)

   of course we can “cheat” using python syntax: x ** n

   Pattern Extraction

   Core Insight: Exponentiation by squaring: \(x^n = (x^{n/2})^2\) for even \(n\), and \(x \cdot x^{n-1}\) for odd \(n\). Reduces \(O(n)\) multiplications to \(O(\log n)\). Pattern Name: Fast Exponentiation (Binary Exponentiation) Canonical Section: Math & Geometry > Number Theory Computations Recognition Signals:

   • “Compute \(x^n\)” efficiently
   • \(n\) can be very large (rules out linear iteration)
   • Negative exponents: \(x^{-n} = 1 / x^n\)

   Anti-Signals:

   • Need modular exponentiation (\(x^n \mod m\)) – same algorithm, just take mod at each step
   • Matrix exponentiation for recurrences – same squaring structure applied to matrices

   Decision Point: The halving structure (\(n \to n/2\)) gives \(O(\log n)\). This is the same principle as binary search but applied to computation rather than search.

   Pitfalls and Misconceptions

   1. Trap: Using linear iteration (\(x \cdot x \cdot … \cdot x\), \(n\) times). Why: \(O(n)\) is too slow when \(n\) can be \(2^{31}\). Correction: Use recursive or iterative squaring: halve \(n\) each step.
   2. Trap: Not handling negative \(n\) correctly. Why: \(x^{-n} = (1/x)^n\). If you negate \(n\) for the recursion, make sure to also invert \(x\) (or compute \(1 / x^{|n|}\) at the end). Correction: At the start: if n < 0: x = 1/x; n = -n.
   3. Trap: Integer overflow when negating \(n = -2^{31}\) (in languages with fixed-width integers). Why: \(-(-2^{31}) = 2^{31}\) overflows a 32-bit signed integer. Correction: In Python, not an issue. In Java/C++, use long for \(n\).
   Problem Mutations

   1. What if you needed \(x^n \mod m\)? (stress-tests: exact computation) Same algorithm, take % m at each multiplication step. This is modular exponentiation, used in RSA and other crypto.
   2. What if you needed to compute Fibonacci(\(n\)) in \(O(\log n)\)? (stress-tests: scalar exponentiation) Matrix exponentiation: raise the Fibonacci transition matrix $[[1,1],[1,0]]$ to the $n$-th power using the same squaring technique.
   3. What if the base were a matrix instead of a scalar? (stress-tests: scalar base) Same algorithm, replace scalar multiplication with matrix multiplication. Used for linear recurrence solving.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Standardised annotation dropdowns for Pow(x, n) generated via batch canonical enrichment pass. Review against personal solving experience and adjust.
   

4. Plus One (66)

   This is the human-like calculation. I have both an inplace and an aux list approach, naturally the in-place one is space optimised, but both are good enough. The optimised version is special to this incrementing context, but the other M2 is generic enough.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

   # m1: in place, optimal class Solution: def plusOne(self, digits: List[int]) -> List[int]: n = len(digits) for i in range(n-1, -1, -1): digits[i] += 1 # early return, no carrying needed: if digits[i] < 10: return digits digits[i] = 0 # If we reach here, it means all digits were `9` return [1] + digits # m2: more generic way of handling this class Solution: def plusOne(self, digits: List[int]) -> List[int]: carry = 1 ans = [] for idx in range(len(digits) - 1, -1, -1): new_digit = digits[idx] + carry if new_digit >= 10: # GOTCHA: this was my initial fault # new_digit, carry = divmod(new_digit, 10) carry, new_digit = divmod(new_digit, 10) else: carry = 0 ans.append(new_digit) # remember to clear out pending carry! if carry: ans.append(carry) return list(reversed(ans))

   Code Snippet 8: Plus One (66)
   Pattern Extraction

   Core Insight: Process digits right to left with carry propagation. Most cases: just increment the last digit. Edge case: all 9s (e.g., 999 -> 1000) requires prepending a 1. Pattern Name: Right-to-Left Digit Processing with Carry Canonical Section: Math and Geometry > Arithmetic Simulation Recognition Signals:

   • “Add one to a number represented as an array of digits”
   • Carry propagation from right to left
   • Edge case: all 9s

   Anti-Signals:

   • Adding arbitrary numbers (not just 1) – generalise to full addition. Connects to LC 415

   Decision Point: Simple carry propagation. The only interesting case is when carry propagates through all digits.

   Pitfalls and Misconceptions

   1. Trap: Converting to integer, adding 1, converting back. Why: Works for small numbers but overflows for very large numbers in some languages. Also misses the point of the exercise. Correction: Process digits directly with carry.
   2. Trap: Not handling the all-9s case (carry propagates past the most significant digit). Why: The result has one more digit than the input (e.g., 999 -> 1000). Need to prepend a 1. Correction: If carry remains after processing all digits, insert 1 at the front: digits.insert(0, 1) or return [1] + [0] * len(digits).
   Problem Mutations

   1. What if you needed to add an arbitrary number \(k\) instead of 1? (stress-tests: fixed increment) Generalise carry propagation to handle multi-digit increments.
   2. What if the digits were in reverse order? (stress-tests: most significant first) Process left to right with carry. Simpler because you can just append.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Standardised annotation dropdowns for Plus One generated via batch canonical enrichment pass.
   

5. Multiply Strings (43)

   This is the human multiplication algo. I think it’s a little non-trivial initially.

   Core intuition: For two digits at positions i (from right in num1) and j (from right in num2), the product contributes to position i + j + 1 in the result array (starting from 0 on the left, with leftmost digit being the most significant).

   Any overflow (carry) is propagated to i + j, the next more significant position.

   We go right to left for both the strings and fill up a results list of size (n + m), the max possible number of digits we may have. We consider what the unit index should be and what the carry index should be. Then we gather the partial sums, which give us the unit digit and the carry value. Now we can use the same result array of digits and update the unit idx and carry indices accordingly. Finally we can just convert the result to a string and skip over the leading zeroes.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

   class Solution: def multiply(self, num1: str, num2: str) -> str: # early returns if either of them is 0 if num1 == "0" or num2 == "0": return "0" n, m = len(num1), len(num2) max_num_places = n + m result = [0] * max_num_places # We process from least significant digit to most significant digit for i in range(n-1, -1, -1): for j in range(m-1, -1, -1): unit_idx = i + j + 1 carry_idx = i + j mul = int(num1[i]) * int(num2[j]) partial_sum = mul + result[i + j + 1] unit_digit = partial_sum % 10 carry_value = partial_sum // 10 result[unit_idx] = unit_digit result[carry_idx] += carry_value # Convert result to string skipping leading zeros result_str = [] leading_zero = True for digit in result: leading_zero = leading_zero and digit == 0 # skip leading zeroes if leading_zero: continue result_str.append(str(digit)) return "".join(result_str) if result_str else "0"

   Code Snippet 9: Multiply Strings (43)
   Pattern Extraction

   Core Insight: Simulate long multiplication digit by digit. num1[i] * num2[j] contributes to result[i + j + 1] (ones) and result[i + j] (carry). Process right to left. Pattern Name: Digit-by-Digit Long Multiplication Canonical Section: Math and Geometry > Arithmetic Simulation Recognition Signals:

   • “Multiply two numbers represented as strings”
   • Can’t use built-in big integer multiplication
   • Result has at most len(num1) + len(num2) digits

   Anti-Signals:

   • Numbers fit in standard integer types – just convert and multiply
   • Addition, not multiplication – simpler. Connects to LC 415

   Decision Point: Grade-school multiplication algorithm simulated in code.

   Pitfalls and Misconceptions

   1. Trap: Indexing the result array incorrectly. Why: num1[i] * num2[j] goes into positions i + j (tens) and i + j + 1 (ones). Off-by-one corrupts the result. Correction: p = d1 * d2 + result[i + j + 1]. result[i + j + 1] = p % 10; result[i + j] + p // 10=.
   2. Trap: Not stripping leading zeros from the result. Why: The result array has leading zeros from initialisation. Correction: result.lstrip('0') or '0'.
   Problem Mutations

   1. What if you needed division instead of multiplication? (stress-tests: operation type) Long division: repeatedly subtract and track quotient digits. Connects to LC 29.
   2. What if one number were very small (single digit)? (stress-tests: both large) Single sweep: multiply each digit by the small number with carry. \(O(n)\).
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Standardised annotation dropdowns for Multiply Strings generated via batch canonical enrichment pass.
   

6. Maximum Median Sum of Subsequences of Size 3 (3627)

   This is just a sort to create the first partitions then just use step size of two and get pairs.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

   class Solution: def maximumMedianSum(self, nums: List[int]) -> int: """ To get the biggest medians, we realise that we can sort the nums (so that we have it monotonically increasing). we will have 2 regions [--As---|---Bs and Cs----] So the Bs and Cs will come in pairs so first triple would be A1, B1,B2, then A2,B3,B4, then A3,B5,B6 until we reach the end of the array. This keeps the medians as large as possible. The step size of2 is what we observe from the pattern above. """ nums.sort() res = 0 for i in range(len(nums) // 3, len(nums), 2): res += nums[i] return res

7. (prime sieve, divisor summation problems)

Polynomial and Number Evaluation via Horner’s Method #

• Efficient digit-by-digit evaluation, modular number building, polynomial evaluation
• we can avoid the big integer overheads (esp for python) by doing modulo eagerly to partial sums

Problems #

1. Concatenate Non-Zero Digits and Multiply by Sum II (3756)

   The intuition for this is simple: do eager applications of modulo so as to avoid big integer overheads and hence TLE errors. This is formalised via Horner’s Method which is an optimal way of evaluating polynomial of degree \(n\) with only \(n\) multiplications and \(n\) additions

   Pattern Extraction

   Core Insight: When computing a number modulo \(m\) from digit-by-digit input, reduce after each digit using Horner’s method instead of constructing the full number first. This avoids big-integer arithmetic and Python’s 4300-digit int() conversion limit.

   Pattern Name: Horner’s Method for Modular Number Evaluation

   Canonical Section: Math & Geometry > Number Theory Computations > Polynomial and Number Evaluation via Horner’s Method

   Recognition Signals:

   • “Compute a number modulo \(m\)” from a digit sequence or string
   • String is long (>4300 chars for full reconstruction)
   • Need to filter digits (e.g., skip zeros) before evaluation
   • Queries over substrings requiring multiple evaluations

   Anti-Signals:

   • Number fits in standard integer type – just convert directly
   • Need the full number, not modulo – requires constructing it fully
   • Number is already an integer (not a string) – Horner’s doesn’t apply
   • Computing only digit sum (no positional weighting) – simple loop suffices

   Decision Point: “Do I need (number % mod) from a string?” If yes, and string is long: Horner’s method. If “do I need the actual number”: full construction unavoidable. If “only sum of digits”: no weighting needed, skip Horner’s.

   Interviewer Comms: “For long digit strings, I can’t construct the full number — it hits Python’s 4300-digit limit. Instead, I use Horner’s method: iterate through digits left to right, and at each step compute x = (x * 10 + digit) % mod. This keeps x bounded by mod at all times, avoiding big-integer overhead.”

   Pitfalls and Misconceptions

   1. Trap: Constructing the full number via int("".join(digits)) before taking modulo. Why: For strings >4300 digits, Python raises ValueError: Exceeds the limit (4300 digits) for integer string conversion. Big-integer arithmetic is also slow for intermediate values. Correction: Apply modulo during evaluation, not after. Use Horner’s: x = (x * 10 + digit) % mod at each step.

   2. Trap: Using exponentiation to weight digits: sum(digit * (10 ** (n - 1 - idx)) for idx, digit in enumerate(digits)). Why: \(O(n^2)\) or worse depending on big-integer multiplication. For n = 5000, this TLEs. Correction: Horner’s method is \(O(n)\) scalar operations. Rewrite as: x = 0; for digit in digits: x = (x * 10 + digit) % mod.

   3. Trap: Not filtering leading zeros before applying Horner’s. Why: Leading zeros don’t affect the numerical value but do affect iteration count unnecessarily. Correction: Pre-filter: digits = [int(c) for c in s[l:r+1] if c ! ‘0’]= Then apply Horner’s on the filtered list.

   4. Trap: Forgetting to reduce modulo inside the loop. Why: Without intermediate reduction, you still construct large intermediate values (e.g., before the final modulo in multiplication). Correction: x = (x * 10 + digit) % mod — reduce at every step, not just once at the end.

   Problem Mutations

   1. What if you needed the actual number, not modulo? (stress-tests: modular constraint) Full construction unavoidable. You’d need to use sys.set_int_max_str_digits() to increase Python’s limit or switch to a language without this limit. Horner’s advantage disappears.

   2. What if the modulus were different (e.g., \(10^9 + 9\) instead of \(10^9 + 7\))? (stress-tests: specific modulus) Same algorithm, change the mod constant. Horner’s applies to any modulus.

   3. What if you needed the product of all query results instead of individual results? (stress-tests: single vs aggregate) Reduce each intermediate product modulo mod, then multiply them together (with modulo at each step).

   4. What if digits could include leading zeros that must be kept? (stress-tests: zero-filtering) Remove the if c ! ‘0’= condition. Horner’s still applies; the numerical value is unchanged (leading zeros don’t affect the result).

   5. What if you needed digit sum and positional number evaluation? (stress-tests: combined operations) Compute both in one pass: accumulate digit sum in a separate variable while running Horner’s for the number. \(O(n)\) total.

   AI usage disclosure Claude Sonnet 4.6 · rubber ducking

   Standardised annotation dropdowns for Horner's Method problem (Sum and Multiply variant) generated via coaching session. Core TIL: Python's `int()` function refuses to parse strings >4300 digits (security limit for denial-of-service prevention); Horner's method side-steps this by never constructing the full number. Reduction during evaluation is mandatory for long strings.
   

Geometric Validation and Overlap #

• Check point-inside-shape, polygon validation, geometric distance and overlap

Problems #

1. TODO Valid Square (593)

2. Type of Triangle (612)

   Pattern Extraction

   Core Insight: Check triangle inequality first, then classify by side equality: all equal = equilateral, two equal = isosceles, none equal = scalene. Pattern Name: Geometric Classification with Validity Check Canonical Section: Math & Geometry > Geometry Problems Recognition Signals:

   • “Classify a triangle” by side lengths
   • Triangle inequality: sum of any two sides > third

   Anti-Signals:

   • Need to compute area – different formulas

   Decision Point: Sort sides and check a + b > c (only need the largest pair). Then classify by equality.

   Pitfalls and Misconceptions

   1. Trap: Not checking the triangle inequality first. Why: Three sides that violate the inequality don’t form a triangle. Correction: Sort: a < b <= c=. Check a + b > c. If fails, return “none”.
   Problem Mutations

   1. What if you needed to classify by angles? (stress-tests: side-based classification) Use the law of cosines. c^2 < a^2 + b^2 = acute. Equal = right. Greater = obtuse.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Batch annotation for Type of Triangle.
   

3. Detect Squares (2013)

   These are at its core just counting problems on the Cartesian plane. Our objective is to just represent the data efficiently and use it to gather some stats that we need. So we store the points within a defaultdict, keyed by the tuple of the x,y coordinate. The main trick is that for each pair of points (of the same x value), we need to treat that vertical line as two cases: A: the left side of the square (so we look right) and B: the right side of the square (so we look left)

   Multiplicity may or may not matter here. Things like “duplicate points are allowed and should be treated as different points” \(\implies\) need to handle duplicates properly. This has other implications like we can’t use a set for this since the duplicates will just be absorbed and that info would be lost.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

   from collections import defaultdict class DetectSquares: def __init__(self): self.points = defaultdict(int) def add(self, point: List[int]) -> None: self.points[tuple(point)] += 1 def count(self, point: List[int]) -> int: x, y = point result = 0 # get candidates (for same x, diff y): for (can_x, can_y), count in list(self.points.items()): # reject impossibles if not (can_x == x and can_y != y): continue side = abs(can_y - y) # possibility 1: we check to the right: p1 = (x, can_y) p2 = (x + side, y) p3 = (x + side, can_y) num_p1, num_p2, num_p3 = [self.points[pt] for pt in [p1, p2, p3]] result += (num_p1 * num_p2 * num_p3) # possibility 2: we check to the left: p4 = (x - side, can_y) p5 = (x - side, y) num_p4, num_p5 = [self.points[pt] for pt in [p4, p5]] result += (num_p1 * num_p4 * num_p5) return result

   Code Snippet 10: Detect Squares (2013)
   Pattern Extraction

   Core Insight: Store all added points. For each query point, look for potential diagonal partners. A diagonal partner shares neither x nor y with the query but both the x-mate and y-mate must exist. Pattern Name: Hash Map Point Lookup for Geometric Queries Canonical Section: Math & Geometry > Geometry Problems Recognition Signals:

   • “Count axis-aligned squares” passing through a query point
   • Dynamic point addition + geometric queries
   • Hash map of point counts

   Anti-Signals:

   • Tilted squares (not axis-aligned) – need to check all distance-based pairs

   Decision Point: Axis-aligned squares: fix one point, enumerate diagonal candidates, check the other two corners exist.

   Pitfalls and Misconceptions

   1. Trap: Only checking for squares where the query point is a corner, missing other configurations. Why: The query point can be any of the four corners. Must check all rotations. Correction: For each point \((px, py)\) with the same x-coordinate as the query, compute side length and check if both remaining corners exist.
   2. Trap: Not using Counter for point counts (missing duplicate points). Why: Multiple points at the same coordinates contribute multiplicatively to the square count. Correction: Use Counter for point frequencies. Multiply counts when computing squares.
   Problem Mutations

   1. What if squares could be tilted (not axis-aligned)? (stress-tests: axis-aligned) Need to check all point pairs and verify rotational square conditions. \(O(n^2)\) per query.
   2. What if you needed rectangles instead of squares? (stress-tests: square constraint) Enumerate pairs with same x-coordinate and pairs with same y-coordinate. Check all rectangle combinations.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Batch annotation for Detect Squares.
   

4. Minimum Sensors to Cover Grid (3638)

   This is a coverage / tiling question, just have to be careful about the ranges and such.

   1 2 3 4 5 6 7 8 9

   class Solution: def minSensors(self, n: int, m: int, k: int) -> int: # each sensor covers a square of sides (2k + 1): from rows: r-k to r+k and columns c-k to c+k, so place sensors at that stride side_length = (2 * k) + 1 # remember to do ceiling division: row_iters = -(-n // side_length) col_iters = -(-m // side_length) return row_iters * col_iters

   Avoid Backtracking When: You see a “minimum covering,” “tiling,” or “dominating set” on a regular grid: always check for formulaic or geometric solutions first.

Coordinate Geometry and Transformations #

• Point rotations, translations, reflections, polygon area and perimeter calculations

TODO Problems #

1. Point rotation around origin
2. Polygon area using Shoelace theorem
   • Cross-product formula: triangle area calculation as in Largest Triangle Area (812)

     1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

     class Solution: def largestTriangleArea(self, points: List[List[int]]) -> float: """ Inputs suggest that we can brute force this, so no need to think of nifty optimisations. Attempt proxy calculation instead of 1/2 * h * b consider 3 points on a rectangle: fix one and the other two become sides, so we just find the distance between them. xa, ya and xb, yb => distance between them can be proxied via: will be (yb - ya) + (xb - xa) We can't make the proxies ans because we need the actual area. We have to use the cross-product formula here. """ n = len(points) max_area = -float('inf') for i in range(n - 2): xi, yi = point_i = points[i] for j in range(i + 1, n - 1): xj, yj = point_j = points[j] for k in range(j + 1, n): xk, yk = point_k = points[k] # Calculate area using cross product formula area = abs(xi*(yj - yk) + xj*(yk - yi) + xk*(yi - yj)) / 2.0 if area > max_area: max_area = area return max_area

     Code Snippet 11: Largest Triangle Area (812)
3. Symmetry detection in point clouds
4. Simulation Problems

   1. Walking Robot Simulation (874)

      This is just a classic simulation question. We should represent directions as unit vectors and we can keep track of direction changes via modifications of relative indices within the directions list. That’s nifty.

      Alternatively, we could also represent direction as a bearing angle.

      1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

      class Solution: def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int: OBSTACLES = set(map(tuple, obstacles)) DIRS = [(0, 1), (1, 0), (0, -1), (-1, 0)] # N, E, S, W x = y = dir_idx = 0 max_dist = 0 for cmd in commands: if cmd == -2: # turn left dir_idx = (dir_idx - 1) % 4 elif cmd == -1: # turn right dir_idx = (dir_idx + 1) % 4 else: dx, dy = DIRS[dir_idx] for _ in range(cmd): nx, ny = x + dx, y + dy if (nx, ny) in OBSTACLES: break x, y = nx, ny max_dist = max(max_dist, x*x + y*y) return max_dist

      Code Snippet 12: Walking Robot Simulation (874)
      Pattern Extraction

      Core Insight: Simulate the robot’s movement step by step. Use a set of obstacle coordinates for \(O(1)\) collision checking. Track direction as an index into a direction array. Pattern Name: Grid Simulation with Obstacle Set Canonical Section: Math & Geometry > Simulation Recognition Signals:

      • “Simulate robot movement” with turn commands and obstacles
      • Track maximum distance from origin

      Anti-Signals:

      • Need shortest path (not simulation) – BFS
      • No obstacles – just compute final position mathematically

      Decision Point: Step-by-step simulation with obstacle checking. The set lookup is the key optimisation (\(O(1)\) vs \(O(k)\) per step).

      Pitfalls and Misconceptions

      1. Trap: Using a list for obstacle lookup instead of a set. Why: List lookup is \(O(k)\) per step. With many steps and obstacles, this TLEs. Correction: Convert obstacles to a set of tuples: obstacle_set = set(map(tuple, obstacles)).
      2. Trap: Moving the full distance at once instead of step by step. Why: Obstacles along the path are missed if you teleport to the destination. Correction: Move one cell at a time, checking for obstacles at each step.
      Problem Mutations

      1. What if the robot could move diagonally? (stress-tests: 4-directional) Add diagonal directions to the direction array. Same simulation.
      2. What if obstacles could appear/disappear? (stress-tests: static obstacles) Update the obstacle set dynamically. Same simulation with mutable set.
      AI usage disclosure Claude Opus 4.6 · content enrichment

          Batch annotation for Walking Robot Simulation.
      

Math Enumeration #

Typically bounded universe enumerations based on some rules

Problems #

1. Sequential Digits (1291)

   For this, the bounded universe is small so we can just pre-prep and do the thing, or we can just step-through based on the digit count.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

   class Solution: def sequentialDigits(self, low: int, high: int) -> List[int]: """ It's a matter of getting the math right, which ends up just being simulated steps to take, the digit counts determined by low, high shall be the outer loop. """ ans = [] n_digits_low, n_digits_high = len(list(str(low))), len(list(str(high))) get_step = lambda n: sum(1 * (10 ** idx) for idx in range(n)) for digit_count in range(n_digits_low, n_digits_high + 1): step = get_step(digit_count) curr = int("".join(str(idx + 1) for idx in range(digit_count))) upper = int("".join(reversed(list(str(9 - idx) for idx in range(digit_count))))) while curr < low: curr += step while curr <= (min(upper,high)): ans.append(curr) curr += step return ans

   Code Snippet 13: My solution: doing stepping

   1 2 3 4 5 6 7 8 9 10 11 12 13 14

   def sequentialDigits(self, low: int, high: int) -> List[int]: ans = [] # Generate all possible sequential digit numbers for length in range(1, 10): # 1 to 9 digit numbers for start_digit in range(1, 11 - length): # Starting digit 1 to 9-length+1 # Construct number: start_digit, start_digit+1, ..., start_digit+length-1 num = int("".join(str(start_digit + i) for i in range(length))) if num > high: return ans # Early exit: generated in order if num >= low: ans.append(num) return ans

   Code Snippet 14: Alternative, pre-calculate the universe
   Pattern Extraction

   Core Insight: When search space is provably finite and small (≤10^6), enumerate all candidates and filter. Iteration logic (stepping, bounds calculation) is error-prone; construction is direct.

   Pattern Name: Bounded Enumeration / Mathematical Construction

   Canonical Section: Mathematical Enumeration (or Combinatorics if exists)

   Recognition Signals:

   • “Find all numbers where property X holds” (not count/optimize, but enumerate)
   • Search space is finite and small: sequential digits (45 numbers), valid parentheses (Catalan), k-digit numbers
   • Constraints allow O(space) or O(space log space) generation
   • n ≤ 10 (or search space ≤ ~10^6)

   Anti-Signals:

   • Problem asks for count only (not enumeration) → use DP/combinatorics formula
   • Search space is exponential (2^n subsets, n! permutations without bounds) → use backtracking, not enumeration
   • Problem requires optimization (max/min over candidates) → BFS/greedy/DP instead
   • Candidates have internal structure that’s hard to construct (e.g., binary trees) → build, don’t enumerate

   Decision Point: Distinguish from Mathematical Stepping (iteratively compute next candidate via formula, e.g., Fibonacci) and Backtracking (explore search tree, prune). This problem: space is small enough to construct directly, so skip stepping logic and avoid backtracking overhead.

   Interviewer Comms: “There are exactly 45 sequential digit numbers (sum 1+2+…+9). I’ll enumerate all by length and starting digit, yielding them in sorted order, then filter by range. No stepping math needed.”

   Pitfalls and Misconceptions

   1. Trap: Derive a “step” value (111 for 3-digit numbers) and iterate using mathematical formula to jump between candidates. Why: Adds complexity and bounds-checking error surface. Step calculation itself is error-prone (off-by-one in upper bound, wrong geometric series formula). Correction: Directly construct each number by looping through (length, start_digit) pairs. Construction is self-verifying.

   2. Trap: Calculate the “upper bound” for each digit-count using reversed/complex logic (e.g., 789 for 3 digits). Why: Reversing logic is cognitively hard; easy to confuse indices. Correction: Use `range(10 - length, 10)` for upper bound construction.

   3. Trap: Miss that the problem is solvable in O(1) time (45 fixed candidates). Why: Overthinking as a “range query” problem when it’s just enumeration. Correction: Count the universe: 9 + 8 + … + 1 = 45. This is a clue to generate all.

   4. Trap: Use a helper lambda or complex list comprehension (e.g., `sum(1 * (10 * idx) …)`) instead of the geometric series closed form. *Why: Premature optimization / micro-engineering. Correction: Use `(10**n - 1) // 9` if you must step; better: don’t.

   Problem Mutations

   1. What if: Numbers must be strictly increasing (not just sequential digits, but also no ties). Stress test: Already true for sequential digits (each digit is +1 from prev). Impact: No change; solution still works.

   2. What if: Allow “reverse sequential” (321, 432, …, 987)? Stress test: Loop becomes nested: for length and for start_digit in range(0, 10 - length). No stepping formula; still O(1) construction.

   3. What if: Range is [low, high] where low and high can have 10+ digits? Stress test: Sequential digits cap at 123456789 (9 digits). If low > 123456789, return empty. Early exit handles this; no complexity change.

   4. What if: Find the k-th smallest sequential digit number (without materializing the list)? Stress test: Direct indexing into (length, start_digit) grid. k ≤ 45, so still O(1).

   5. What if: Numbers can have repeated digits (e.g., 1223, 111)? Stress test: No longer “sequential”; problem becomes density enumeration. Approach breaks; would need a different characterization (e.g., DP on digit DP state).

   AI usage disclosure Claude Sonnet 4.6 · coaching

   This canonical entry was drafted during a coaching session on LC 1291 (Sequential Digits). The framing emphasizes recognizing bounded enumeration as the core pattern and avoiding over-engineering with mathematical stepping logic. Pitfalls target the specific misconceptions from the user's original solution (step calculation, upper bound derivation). Mutations stress-test the finite universe assumption and show how the approach breaks under constraint changes.
   

Line and Segment Intersection / Sweeping #

• Line equations, sweep-line algorithms, interval intersection problems

Problems #

1. Line Sweep Algorithms(study guide)

   • Find the Number of Ways to Place People II (3027)

     This requires us to sort in both dimensions (ascending x and descending y) to aide our use of the sweepline algo.

     1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

     class Solution: def numberOfPairs(self, points: List[List[int]]) -> int: """ choosing A,B: A-B rectangle formation is more of consider xa,ya and xb,yb. As long as xb is not less than xa and yb is not more than ya then it's a legit choice for A,B identifying: unhapiness. consider a sorted array of points (sorted by x then y). For any two idx i, j where i is for potential placement of A and j is for potential placement of B (assume that works). so let it be xidx, yidx for the point in between. anything in the middle must be out of the enclosure. i.e xidx < xa or xidx > xb or yidx > ya and yidx < yb for it to be legit === optimising: if it's sorted and we take two points,then the x value is in between, so we only care about the y values whether they are outside. """ points.sort() n = len(points) count = 0 placements = set() for right in range(1, n): for left in range(right): xa,ya = points[left] # alice coords xb, yb = points[right] # bob coords print(f"xa,ya {xa,ya} | xb,yb {xb,yb}") if xa == xb and yb > ya: # swap them if possible xa, ya, xb, yb = xb, yb, xa, ya print(f"\tswapped, placement:{(xa, ya, xb, yb)}") if xb < xa or yb > ya: # not possible to form enclosure print("not possible to place A and B: no rect") continue has_violating_mid_point = any((yb < ymid < ya and xa < xmid < xb) for xmid, ymid in points[left + 1:right]) if has_violating_mid_point: print("\tnot possible to place A and B: unhappy") continue print(f"adding placement:{(xa, ya, xb, yb)}") placements.add((xa, ya, xb, yb)) return len(placements)

     Code Snippet 15: Find the Number of Ways to Place People II (3027)
2. Interval intersection problems (e.g., merge intervals)

Counting and Combinatorial Geometry #

• Counting lattice points, number of triangles or polygons from points

Problems #

1. Counting right triangles on a grid

2. Pick’s theorem application problems

3. Count Number of Trapezoids I (3623)

   Even for the naive approach, we need a way to preprocess to do some combinatorics on. Grouping via the y-values comes to mind, then the rest is just doing arithmetic on it. The way to avoid a TLE is to realise that we don’t need to keep intermediate lists, just counts is sufficient so that we can then do running sums instead of pairwise sums.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

   from collections import defaultdict class Solution: def countTrapezoids(self, points: List[List[int]]) -> int: """ We do pairwise running sums instead of having to keep track of too many / too long lists and running out of time and/or memory. first: organise the values: """ MOD = 10 ** 9 + 7 level_to_points = defaultdict(int) for _, y in points: level_to_points[y] += 1 """ Here we are doing running sums, at each level, the new shapes = running count of points * pairs in that level (modulo-ed) as expected. As for the running count, it's raelly just a sum of pairs encountered so far. """ shapes, running_count_points = 0, 0 for _, n in level_to_points.items(): pairs = (n * (n - 1)) // 2 # n choose 2 shapes += (pairs * running_count_points) % MOD running_count_points += pairs % MOD return shapes % MOD

   Code Snippet 16: Count Number of Trapezoids I (3623)
   Pattern Extraction

   Core Insight: A trapezoid has exactly one pair of parallel sides. For each pair of points defining a line, compute the slope. Group lines by slope and check for parallel pairs that form valid trapezoids. Pattern Name: Slope-Based Geometric Grouping Canonical Section: Math & Geometry > Geometry Problems Recognition Signals:

   • “Count geometric shapes” from a point set
   • Parallel sides identified by equal slopes
   • Slope comparison using cross-product to avoid floating point

   Anti-Signals:

   • Need to find specific shapes with additional constraints (right angles, equal sides)

   Decision Point: Parallelism = equal slopes. Use cross-product dy1 * dx2 = dy2 * dx1= to avoid floating point.

   Pitfalls and Misconceptions

   1. Trap: Using floating-point division for slopes. Why: Floating point introduces precision errors. (dy1/dx1 = dy2/dx2)= can fail for nearly-equal slopes. Correction: Cross-multiply: dy1 * dx2 = dy2 * dx1=. Exact integer arithmetic.
   Problem Mutations

   1. What if you needed parallelograms (two pairs of parallel sides)? (stress-tests: one pair) Count pairs of parallel line segments. Parallelogram = two such pairs from four points.
   2. What if points were in 3D? (stress-tests: 2D) Parallelism still defined by direction vectors. Cross-product becomes 3D.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Batch annotation for Count Number of Trapezoids I.
   

4. Count Number of Trepezoids II (3625)

   This is interesting, super tedious. It requires the keen understanding of inclusion exclusion principle to guide combinatorial counting. The extension part from before is to be able to know how to group things together.

   There’s a bunch of learnings here: slope normalisation, inclusion exclusion pattern, intercept calculation and parellogram counting. Check it out in the algos file.

   Community solution:

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53

   from math import gcd from collections import Counter from itertools import combinations from math import comb from typing import List class Solution: def countTrapezoids(self, points: List[List[int]]) -> int: # Counters for different groupings we'll use for combinatorial counting slopes = Counter() # Count of all line segments grouped only by their slope (dx, dy) lines = Counter() # Count of line segments grouped by slope and intercept (dx, dy, intercept) mids = Counter() # Count of midpoint occurrences from all pairs of points (x1+x2, y1+y2) midlines = Counter() # Count of midpoints paired also with line info (x1+x2, y1+y2, dx, dy, intercept) # Iterate over all unique pairs of points for (x1, y1), (x2, y2) in combinations(points, 2): dx, dy = x2 - x1, y2 - y1 g = gcd(dx, dy) # Normalize slope to smallest integer ratio dx, dy = dx // g, dy // g # Normalize direction of the slope so it's always consistent: # dx > 0 or if dx == 0, dy must be > 0. This ensures (1, 2) and (-1, -2) are treated the same if dx < 0 or (dx == 0 and dy < 0): dx, dy = -dx, -dy # Calculate intercept in integer form to avoid floating fraction errors # The intercept is proportional to "line constant" in line equation rewritten as dx*y - dy*x = intercept inter = dx * y1 - dy * x1 # Count the number of line segments with this slope (dx, dy) slopes[(dx, dy)] += 1 # Count the number of line segments with this exact line: slope + intercept lines[(dx, dy, inter)] += 1 # Count midpoints (x1+x2, y1+y2) to detect parallelograms later (pairs of segments sharing midpoint) mids[(x1 + x2, y1 + y2)] += 1 # Count midpoint and line tuple to fix overcounting when midpoint lines overlap midlines[(x1 + x2, y1 + y2, dx, dy, inter)] += 1 # We apply combinatorial counting (n choose 2) to find pairs: # 1. Count pairs of segments with same slope (all pairs of parallel lines) # 2. Subtract pairs of segments on the exact same line (to avoid counting segments of same line as trapezoids) # 3. Subtract pairs that share the same midpoint (parallelograms counted wrongly as trapezoids) # 4. Add back pairs that share both midpoint and line (fix double subtraction in step 2 and 3) ans = sum(comb(v, 2) for v in slopes.values()) \ ​ - sum(comb(v, 2) for v in lines.values()) \ ​ - sum(comb(v, 2) for v in mids.values()) \ ​ + sum(comb(v, 2) for v in midlines.values()) return ans

   Code Snippet 17: Count Number of Trepezoids II (3625)
   Pattern Extraction

   Core Insight: Extension of Trapezoids I with additional constraints (e.g., area computation, no three collinear points). Same slope-grouping approach with additional geometric checks. Pattern Name: Slope-Based Geometric Grouping with Constraints Canonical Section: Math & Geometry > Geometry Problems Recognition Signals:

   • “Count trapezoids” with additional validity constraints
   • Extension of the base counting problem

   Anti-Signals:

   • Simple counting without constraints – Trapezoids I

   Decision Point: Same slope grouping, additional filters per candidate trapezoid.

   Pitfalls and Misconceptions

   1. Trap: Not handling degenerate cases (collinear points, zero-area shapes). Why: Four collinear points don’t form a trapezoid. Three collinear points create a degenerate case. Correction: Add collinearity checks before counting.
   Problem Mutations

   1. What if the points were on a grid with integer coordinates? (stress-tests: general coordinates) Integer coordinates make cross-product computation exact. No special handling needed.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Batch annotation for Count Number of Trapezoids II.
   

Mathematical Series and Summations #

• Sum of arithmetic/geometric progressions, modular summations, combinatorics

Problems #

1. Sum of powers

2. Combinatorial counting with constraints

3. Alice and Bob Playing Flower Game (3021)

   This is a basic counting question. We inspect and realise that it’s a simple math property: if the overall units is odd-numbered, then Alice will win if she starts first. For that to happen, the two operands that form up the total; one should be odd and the other should be even. We just count that.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

   class Solution: def flowerGame(self, n: int, m: int) -> int: """ The objective is for alice to win, she also starts first ==> x, y form an odd pair I know that it's also a build-up of values, because we question boils down to: given n and m, pick odd pairs (x, y) such that x in [1, n] and y in [1, m] so (x + y) must be odd This is just a pure combinations question. case 1: x is odd, y is even case 2: y is odd, x is even """ get_odd_nums = lambda num: (num + 1) // 2 get_even_nums = lambda num: (num) // 2 case_1 = get_odd_nums(n) * get_even_nums(m) case_2 = get_even_nums(n) * get_odd_nums(m) return case_1 + case_2

   Code Snippet 18: Alice and Bob Playing Flower Game (3021)
   Pattern Extraction

   Core Insight: Game theory / mathematical analysis. Determine winning conditions based on parity of total flowers. Alice wins when the total is odd (she moves first and last). Count pairs \((x, y)\) where \(x + y\) is odd. Pattern Name: Parity-Based Game Analysis Canonical Section: Math & Geometry > Game Theory / Combinatorics Recognition Signals:

   • “Who wins the game” based on counts
   • Parity determines the winner
   • Count winning configurations

   Anti-Signals:

   • Game involves strategy (not just parity) – minimax/game DP

   Decision Point: When the game is purely turn-based (take one item per turn, alternating), parity of the total determines the winner.

   Pitfalls and Misconceptions

   1. Trap: Simulating the game instead of using the parity insight. Why: Simulation is \(O(x + y)\) per game. The parity insight gives \(O(1)\). Correction: \(x + y\) odd = Alice wins. Count pairs: odd \(x\) \(\times\) even \(y\) + even \(x\) \(\times\) odd \(y\).
   Problem Mutations

   1. What if the game had different rules (e.g., take 1-3 per turn)? (stress-tests: take-one) Sprague-Grundy theorem. Need to compute Grundy values, not just parity.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Batch annotation for Alice and Bob Playing Flower Game.
   

Fraction and Rational Number Canonical Forms #

• Simplify fractions, compare rational numbers, gcd-based normalization

Problems #

1. Repeated fraction detection
2. Fraction addition and comparison properly normalized

Polygon and Convex Hull Problems #

• Convex hull algorithms, polygon triangulation and area calculation

TODO Problems #

• Jarvis March (Gift Wrapping)
• Graham Scan

Prime Factorization and Divisor Problems #

• Prime factor counting, divisor enumeration, factorization problems

TODO Problems #

• Prime sieve (Sieve of Eratosthenes)
• Count divisors of a number efficiently

Modular Arithmetic and Number Systems #

• Modular inverse, CRT, multiplicative groups, number base conversions

TODO Problems #

• Modular exponentiation
• Chinese Remainder Theorem problems
• Base conversions and representations

Trigonometry and Angle Calculations #

• Angle calculations from coordinates, vector dot/cross products

TODO Problems #

• Compute angle between vectors
• Determine clockwise/counter-clockwise orientation

Geometric Probability and Randomized Geometry #

• Probabilistic interpretations involving geometry, area/length probabilities

TODO Problems #

• Probability of random point in polygon/subshape

SOE #

• Integer division pitfalls causing truncation errors

• Floating point precision or rounding errors

• Incorrect coordinate handling or orientation mistakes

• Issues with index accesses for grids / matrices

  1. Off-by-One Errors:

     • When iterating elements for swap within a layer, loop from first to last - 1 (not including last), otherwise repeated swaps or out-of-bound accesses happen.

  2. Incorrect offset Computation:

     • Calculate offset = i - first precisely to map indices correctly.

  3. Layer Limits:

     • Iterate only through n // 2 layers; middle layer in odd-sized matrix remains untouched.

  4. Temp Variable:

     • Forgetting to use a temporary variable results in corrupted values due to overwriting.

  5. Indexing Mistakes:

     • Confusing row-column indexing across four parts can cause wrong assignments.

  6. Not Handling Single-Element Matrix:

     • For n=1, the matrix is unchanged and should be considered.

Decision Flow #

• Matrix rotations? → 2D index math + reverse/swap
• GCD/LCM? → Euclidean algorithm
• Geometry intersection? → Coordinate comparisons and axis alignments

Styles, Tricks and Boilerplate #

Styles #

• For the grid like traversals, it seems that the first parameter to create that others can be based off of is just layer

• Be consistent about the intervals (closed, open? closed, closed?) and just put some comments to avoid getting confused about the indices.

Tricks #

• Number theory stuff

  1. Number factorisation – see boilerplate below

• Python Recipe: Transposing is super simple in python:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

  def oneliner_transpose(matrix): """ zip() with the unpacking operator will group elements from each row at the same index together. The listcomp is necessary here because we would get tuples otherwise. """ return [list(row) for row in zip(*matrix)] def transpose_inplace(matrix): n = len(matrix) # Only need to iterate up to n-1 since we're swapping pairs for i in range(n): # Start from i+1 to avoid redundant swaps for j in range(i + 1, n): # Use tuple assignment to swap elements matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j] return matrix

• Python recipe: divmod is very useful

  • to get carry and remainder: carry, new_digit = divmod(new_digit, 10)

• for grid questions, remember that one way to do in place changes is to use the first row / first column as a marker set to keep track of the kind of actions that we need to do. The “Set Matrix Zeroes (73)” problem is an example of this.

Boilerplate #

Fast Exponentiation #

we check the index, try to force out a even number, then we multiply with itself iteratively.

we need to handle negative indices and odd indices. Negative indices can be made positive by using the reciprocal of a number. Odd indices can be made even by multiplying it (which effectively decrements the index from an odd to an even numbered index.)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

# ITERATIVE FAST BINARY EXPONENTIATION
class Solution:
    def myPow(self, x: float, n: int) -> float:
        # iterative fast exponentiation:
        N = n # N is the running exponent that we shall be using

        if N < 0:   # if negative exponent, then make it positive, use the reiprocal for the operand
            x = 1 / x
            N = -N

        result = 1.0
        curr_product = x

        while N > 0:
            # if first bit is 1 / it's odd:
            if N % 2 == 1:
                result *= curr_product # decrement so that it's even and we can power this

            curr_product *= curr_product
            N //= 2 # half the exponent

        return result

# RECURSIVE FAST BINARY EXPONENTIATION
class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n == 0:
            return 1.0
        if n < 0:
            return 1 / self.myPow(x, -n)
        half = self.myPow(x, n // 2)
        if n % 2 == 0:
            return half * half
        else:
            return half * half * x

Sieve of Eratosthenes #

Prime factor bool array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def sieve(limit):
    """
    Returns a list of prime numbers within limit (inclusive)
    """
    is_prime = [True] * (limit + 1)
    is_prime[0], is_prime[1] = False, False
    # remember we only need to do till sqrt of the limit
    for num in range(2, int(sqrt(limit) + 1)):
        if is_prime[num]:
            # negate its multiples:
            for j in range(num * num, limit + 1, num):
                is_prime[j] = False

    return is_prime

Factorisation #

• basic number factorisation

  1 2 3 4 5 6 7 8

  def get_factors(x): # Return all factors of x >= 1 in sorted order result = set() for f in range(1, int(x**0.5) + 1): if x % f == 0: result.add(f) result.add(x // f) return sorted(result)

  Code Snippet 21: Factorisation

• Prime Factorisation

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

  def prime_factors(num): """ Returns a set of prime factors for a number: """ factors = set() temp = num # prime factorisation for i in range(2, int(sqrt(num)) + 1): if not is_prime[i]: continue while temp % i == 0: factors.add(i) temp //= i if temp == 1: break if temp > 1: # then temp is a prime too factors.add(temp) return factors

  Code Snippet 22: Factorisation

  for the is_prime check, we can use the Sieve of Eratosthenes boilerplate above.

TODO KIV #