Topic 18: Math & Geometry

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

Canonical Question Types #

Matrix Rotations and Traversals #

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

Problems #

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

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()

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

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

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

Number Theory Computations #

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

Problems #

TODO GCD of Strings (1071)

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

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

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

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))

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"

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

(prime sieve, divisor summation problems)

Geometric Validation and Overlap #

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

Problems #

TODO Valid Square (593)
Type of Triangle (612) ✅

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

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 #

Point rotation around origin

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

Symmetry detection in point clouds

Simulation Problems

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

Line and Segment Intersection / Sweeping #

Line equations, sweep-line algorithms, interval intersection problems

Problems #

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)

Interval intersection problems (e.g., merge intervals)

Counting and Combinatorial Geometry #

Counting lattice points, number of triangles or polygons from points

Problems #

Counting right triangles on a grid
Pick’s theorem application problems

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

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

Mathematical Series and Summations #

Sum of arithmetic/geometric progressions, modular summations, combinatorics

Problems #

Sum of powers
Combinatorial counting with constraints

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

Fraction and Rational Number Canonical Forms #

Simplify fractions, compare rational numbers, gcd-based normalization

Problems #

Repeated fraction detection
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

Style, Tricks and Boilerplates #

Style #

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

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)

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.

Formalised Algos #

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)

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

for the is_prime check, we can generate a prime sieve like so:

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

def sieve(limit):
    """
    Returns a list of prime numbers within limit (inclusive)
    """
    is_prime = [True] * (limit + 1) # effectively makes this 1-indexed
    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

is_prime = sieve(max_val) # is the reference prime-sieve