Skip to content

21. Math and Geometry#

Theory#

Math and geometry problems in interviews rarely require calculus. They combine number theory (GCD, modular arithmetic, exponentiation), 2D coordinate reasoning (slopes, distances, matrix traversal), and occasionally vector operations (dot/cross product for orientation and area). The pattern is: translate the problem into a mathematical invariant, then implement it carefully while avoiding floating-point pitfalls.

See also: Bit Manipulation (XOR, bit tricks), Binary Search (Sqrt(x) via search on answer), Fast and Slow Pointers (Happy Number cycle detection).

Vectors#

A 2D vector is an ordered pair (x, y) representing displacement from the origin. In code, points and vectors are often the same type; context distinguishes position vs direction.

Operation Formula Use in DSA
Add (x₁, y₁) + (x₂, y₂) = (x₁+x₂, y₁+y₂) Translate points; sum edge vectors
Scalar multiply k · (x, y) = (kx, ky) Scale direction
Magnitude \|v\| = √(x² + y²) Distance from origin
Unit vector v / \|v\| Normalize slope (avoid floats — use GCD instead)

Dot product: a · b = x₁x₂ + y₁y₂

  • a · b = 0 → vectors are perpendicular
  • Sign tells whether angle is acute or obtuse
  • Projects one vector onto another: proj_a(b) = (a·b / |a|²) · a

Cross product (2D): treat vectors as 3D with z = 0. The scalar result is the signed z-component:

a × b = x₁y₂ − x₂y₁

Sign of a × b Meaning
> 0 b is counter-clockwise from a
< 0 b is clockwise from a
= 0 Collinear (same or opposite direction)

Use cross product for orientation tests (convex hull, "which side of a line?") and area: triangle area = |a × b| / 2.

GCD and LCM#

Greatest Common Divisor (GCD) — largest integer dividing both a and b.

Euclidean algorithm:

def gcd(a: int, b: int) -> int:
    while b:
        a, b = b, a % b
    return abs(a)

Extended GCD finds x, y such that ax + by = gcd(a, b) — used in modular inverse problems.

Least Common Multiple: lcm(a, b) = |a · b| / gcd(a, b)

Why GCD matters in geometry:

  • Represent slope as reduced fraction (dy, dx) with gcd(|dy|, |dx|) = 1 — avoids floating-point equality bugs in "points on a line" problems.
  • Normalize direction vectors so (dy, dx) and (-dy, -dx) map to the same key.

Modular Arithmetic#

When results can overflow or you need remainders, work in mod m.

Core properties (for integers a, b and mod m):

  • (a + b) mod m = ((a mod m) + (b mod m)) mod m
  • (a · b) mod m = ((a mod m) · (b mod m)) mod m
  • (a − b) mod m = ((a mod m) − (b mod m) + m) mod m ← handle negatives

Modular exponentiation (binary exponentiation / exponentiation by squaring):

def mod_pow(base: int, exp: int, mod: int) -> int:
    result, b = 1, base % mod
    while exp:
        if exp & 1:
            result = (result * b) % mod
        b = (b * b) % mod
        exp >>= 1
    return result

Time: O(log exp). Used in Pow(x, n), Super Pow, and cryptography-style problems.

Tip: For x^n where n is negative, compute x^|n| then take reciprocal: 1 / x^n.

Coordinate Geometry Basics#

Concept Formula / Rule
Distance √((x₂−x₁)² + (y₂−y₁)²) — compare squared distance to avoid sqrt
Slope (y₂−y₁) / (x₂−x₁) — use reduced (dy, dx) pair instead of float
Collinearity Cross product (p−a) × (q−a) == 0 for points p, q, a
Line through origin Points (x, y) with y/x = k share slope k
Rectangle overlap Intervals overlap on both axes ⟺ rectangles intersect
Matrix as grid (row, col) with directions (dr, dc) — map compass to deltas

Direction vectors for matrix traversal:

DIRS_4 = [(0, 1), (1, 0), (0, -1), (-1, 0)]   # right, down, left, up
DIRS_8 = DIRS_4 + [(1, 1), (1, -1), (-1, -1), (-1, 1)]

In-place matrix transforms: rotate 90° clockwise = transpose then reverse each row; reflect across anti-diagonal = swap matrix[i][j] with matrix[j][i] then reverse rows.

Problems at a glance#

LC Problem
48 1. Rotate Image ↗
73 2. Set Matrix Zeroes ↗
54 3. Spiral Matrix ↗
50 4. Pow(x, n) ↗
149 5. Max Points on a Line ↗
1232 6. Check If It Is a Straight Line ↗
372 7. Super Pow ↗
367 8. Valid Perfect Square ↗
836 9. Rectangle Overlap ↗
2013 10. Detect Squares ↗

Problems#

1. Rotate Image (Leetcode:48)#

Problem Statement

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees clockwise.

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]

Example 2:

Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

Constraints:

n == matrix.length == matrix[i].length
1 <= n <= 20
-1000 <= matrix[i][j] <= 1000

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
from typing import List

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)

        # Transpose: swap matrix[i][j] with matrix[j][i]
        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()
Explanation:

  1. 90° clockwise equals transpose then reverse each row.
  2. Transpose reflects across the main diagonal: element at (i, j) moves to (j, i).
  3. Reversing rows completes the clockwise rotation in O(1) extra space.

Time: O(n²)  |  Space: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
from typing import List

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)
        for layer in range(n // 2):
            first, last = layer, n - 1 - layer
            for i in range(first, last):
                offset = i - first
                top = matrix[first][i]
                matrix[first][i] = matrix[last - offset][first]
                matrix[last - offset][first] = matrix[last][last - offset]
                matrix[last][last - offset] = matrix[i][last]
                matrix[i][last] = top
Explanation:

  1. Process concentric layers from outside in.
  2. Each group of four cells rotates as a 4-cycle: top → left → bottom → right.
  3. Direct in-place rotation without explicit transpose — same complexity, more index arithmetic.

Time: O(n²)  |  Space: O(1)

2. Set Matrix Zeroes (Leetcode:73)#

Problem Statement

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0s.

You must do it in place.

Example 1:

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]

Example 2:

Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]

Constraints:

m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
-2^31 <= matrix[i][j] <= 2^31 - 1

Follow up:

A straightforward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best.
Could you devise a constant space solution?

Code and Explanation 

 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 typing import List

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        m, n = len(matrix), len(matrix[0])
        first_row_zero = any(matrix[0][j] == 0 for j in range(n))
        first_col_zero = any(matrix[i][0] == 0 for i in range(m))

        # Use first row/col to mark which rows/cols need zeroing
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][j] == 0:
                    matrix[i][0] = 0
                    matrix[0][j] = 0

        # Zero cells based on markers (skip row 0 and col 0)
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][0] == 0 or matrix[0][j] == 0:
                    matrix[i][j] = 0

        if first_row_zero:
            for j in range(n):
                matrix[0][j] = 0
        if first_col_zero:
            for i in range(m):
                matrix[i][0] = 0
Explanation:

  1. Record whether row 0 or column 0 originally contained a zero (they need special handling).
  2. For each zero at (i, j), mark matrix[i][0] and matrix[0][j] — reusing first row/column as bit flags.
  3. Second pass zeroes interior cells using markers, then fix row 0 and column 0 last.

Time: O(m · n)  |  Space: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
from typing import List

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        m, n = len(matrix), len(matrix[0])
        zero_rows, zero_cols = set(), set()

        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    zero_rows.add(i)
                    zero_cols.add(j)

        for i in zero_rows:
            for j in range(n):
                matrix[i][j] = 0
        for j in zero_cols:
            for i in range(m):
                matrix[i][j] = 0
Explanation:

  1. Collect all row and column indices that contain at least one zero.
  2. Zero entire rows and columns in separate passes.
  3. Simpler to reason about, but uses O(m + n) extra space.

Time: O(m · n)  |  Space: O(m + n)

3. Spiral Matrix (Leetcode:54)#

Problem Statement

Given an m x n matrix, return all elements of the matrix in spiral order.

Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]

Example 2:

Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

Constraints:

m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrix[i][j] <= 100

Code and Explanation 

 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
from typing import List

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        result = []
        top, bottom = 0, len(matrix) - 1
        left, right = 0, len(matrix[0]) - 1

        while top <= bottom and left <= right:
            for col in range(left, right + 1):
                result.append(matrix[top][col])
            top += 1

            for row in range(top, bottom + 1):
                result.append(matrix[row][right])
            right -= 1

            if top <= bottom:
                for col in range(right, left - 1, -1):
                    result.append(matrix[bottom][col])
                bottom -= 1

            if left <= right:
                for row in range(bottom, top - 1, -1):
                    result.append(matrix[row][left])
                left += 1

        return result
Explanation:

  1. Maintain four boundaries: top, bottom, left, right.
  2. Traverse right → down → left → up, then shrink the corresponding boundary.
  3. Guard the left/up passes with if top <= bottom / if left <= right to avoid duplicates on non-square matrices.

Time: O(m · n)  |  Space: O(1) excluding output

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from typing import List

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix:
            return []
        m, n = len(matrix), len(matrix[0])
        dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # R, D, L, U
        r = c = di = 0
        result = []
        visited = [[False] * n for _ in range(m)]

        for _ in range(m * n):
            result.append(matrix[r][c])
            visited[r][c] = True
            nr, nc = r + dirs[di][0], c + dirs[di][1]
            if 0 <= nr < m and 0 <= nc < n and not visited[nr][nc]:
                r, c = nr, nc
            else:
                di = (di + 1) % 4
                r += dirs[di][0]
                c += dirs[di][1]

        return result
Explanation:

  1. Walk using a direction index that rotates on hitting a wall or visited cell.
  2. Direction vectors encode coordinate geometry: (dr, dc) pairs.
  3. Easier to extend to similar spiral-fill problems; uses O(m · n) visited space.

Time: O(m · n)  |  Space: O(m · n)

4. Pow(x, n) (Leetcode:50)#

Problem Statement

Implement pow(x, n), which calculates x raised to the power n (i.e., x^n).

Example 1:

Input: x = 2.00000, n = 10
Output: 1024.00000

Example 2:

Input: x = 2.10000, n = 3
Output: 9.26100

Example 3:

Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2⁻² = 1/2² = 1/4 = 0.25

Constraints:

-100.0 < x < 100.0
-2^31 <= n <= 2^31 - 1
n is an integer.
Either x is not zero or n > 0.
-10^4 <= x^n <= 10^4

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n < 0:
            x, n = 1 / x, -n

        result = 1.0
        while n:
            if n & 1:
                result *= x
            x *= x
            n >>= 1
        return result
Explanation:

  1. Handle negative exponent: compute x^|n| then invert (1/x each step).
  2. Exponentiation by squaring: if n is odd, multiply result by current x; then square x and halve n.
  3. Each bit of n processed once → O(log n) multiplications instead of O(n).

Time: O(log n)  |  Space: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n == 0:
            return 1.0
        if n < 0:
            return self.myPow(1 / x, -n)
        if n % 2 == 0:
            half = self.myPow(x, n // 2)
            return half * half
        return x * self.myPow(x, n - 1)
Explanation:

  1. Base case: x^0 = 1.
  2. Even n: x^n = (x^(n/2))² — halve the problem.
  3. Odd n: peel one factor and recurse. Same O(log n) depth, more stack frames.

Time: O(log n)  |  Space: O(log n) recursion stack

5. Max Points on a Line (Leetcode:149)#

Problem Statement

Given an array of points where points[i] = [xᵢ, yᵢ] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.

Example 1:

Input: points = [[1,1],[2,2],[3,3]]
Output: 3

Example 2:

Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4

Constraints:

1 <= points.length <= 300
points[i].length == 2
-10^4 <= xᵢ, yᵢ <= 10^4
All the points are unique.

Code and Explanation 

 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
from typing import List
from collections import defaultdict

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        n = len(points)
        if n <= 2:
            return n

        def gcd(a: int, b: int) -> int:
            while b:
                a, b = b, a % b
            return abs(a)

        def slope_key(x1, y1, x2, y2):
            dx, dy = x2 - x1, y2 - y1
            if dx == 0:
                return (0, 1)          # vertical line
            if dy == 0:
                return (1, 0)          # horizontal line
            g = gcd(dx, dy)
            dx //= g
            dy //= g
            if dx < 0:                 # canonical direction
                dx, dy = -dx, -dy
            return (dx, dy)

        ans = 0
        for i in range(n):
            counts = defaultdict(int)
            same = 1
            for j in range(i + 1, n):
                if points[i] == points[j]:
                    same += 1
                    continue
                key = slope_key(points[i][0], points[i][1],
                                points[j][0], points[j][1])
                counts[key] += 1
            local_max = same
            for cnt in counts.values():
                local_max = max(local_max, cnt + same)
            ans = max(ans, local_max)

        return ans
Explanation:

  1. Fix an anchor point points[i] and count how many other points share each slope.
  2. Represent slope as reduced fraction (dx, dy) via GCD — avoids float comparison errors.
  3. Canonicalize direction (flip signs so dx > 0) so (1,2) and (-1,-2) match.
  4. Track duplicate anchor coordinates separately (same counter).

Time: O(n²)  |  Space: O(n)

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

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        n = len(points)
        if n <= 2:
            return n

        ans = 0
        for i in range(n):
            for j in range(i + 1, n):
                count = 2
                x1, y1 = points[i]
                x2, y2 = points[j]
                for k in range(n):
                    if k == i or k == j:
                        continue
                    x3, y3 = points[k]
                    # Cross product (x2-x1, y2-y1) x (x3-x1, y3-y1) == 0 → collinear
                    if (x2 - x1) * (y3 - y1) == (y2 - y1) * (x3 - x1):
                        count += 1
                ans = max(ans, count)
        return ans
Explanation:

  1. Pick two points to define a line; test every third point with cross product = 0.
  2. Integer arithmetic only — no slope division.
  3. O(n³) but clear geometrically; acceptable for small constraints or as interview warm-up before optimizing to O(n²).

Time: O(n³)  |  Space: O(1)

6. Check If It Is a Straight Line (Leetcode:1232)#

Problem Statement

You are given an array coordinates, coordinates[i] = [x, y], where [x, y] represents the coordinate of a point. Check if these points make a straight line in the XY plane.

Example 1:

Input: coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]]
Output: true

Example 2:

Input: coordinates = [[1,1],[2,2],[3,4],[4,5],[5,6],[7,7]]
Output: false

Constraints:

2 <= coordinates.length <= 1000
coordinates[i].length == 2
-10^4 <= xᵢ, yᵢ <= 10^4
coordinates contains no duplicate point.

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
from typing import List

class Solution:
    def checkStraightLine(self, coordinates: List[List[int]]) -> bool:
        x0, y0 = coordinates[0]
        x1, y1 = coordinates[1]
        for x2, y2 in coordinates[2:]:
            if (x1 - x0) * (y2 - y0) != (y1 - y0) * (x2 - x0):
                return False
        return True
Explanation:

  1. Use first two points as reference direction vector (x1−x0, y1−y0).
  2. Every other point must satisfy cross product = 0 with the reference — integer safe, no division.
  3. Handles vertical lines naturally (no undefined slope).

Time: O(n)  |  Space: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
from typing import List

class Solution:
    def checkStraightLine(self, coordinates: List[List[int]]) -> bool:
        x0, y0 = coordinates[0]
        x1, y1 = coordinates[1]
        dx, dy = x1 - x0, y1 - y0

        for x2, y2 in coordinates[2:]:
            if dx * (y2 - y0) != dy * (x2 - x0):
                return False
        return True
Explanation:

  1. Equivalent to comparing (y2−y0)/(x2−x0) with (y1−y0)/(x1−x0) via cross-multiplication.
  2. Same cross-product logic, written as slope equality without floating point.

Time: O(n)  |  Space: O(1)

7. Super Pow (Leetcode:372)#

Problem Statement

Your task is to calculate aᵇ mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array.

Example 1:

Input: a = 2, b = [3]
Output: 8

Example 2:

Input: a = 2, b = [1,0]
Output: 1024

Example 3:

Input: a = 1, b = [4,3,3,8,5,2]
Output: 1

Constraints:

1 <= a <= 2^31 - 1
1 <= b.length <= 2000
0 <= b[i] <= 9
b does not contain leading zeros.

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from typing import List

MOD = 1337

class Solution:
    def superPow(self, a: int, b: List[int]) -> int:
        def pow_mod(x: int, n: int) -> int:
            result = 1
            x %= MOD
            while n:
                if n & 1:
                    result = (result * x) % MOD
                x = (x * x) % MOD
                n >>= 1
            return result

        # b = d0 d1 ... dk  =>  b = d0*10^k + d1*10^(k-1) + ...
        # a^b = (a^10)^(d0) * (a^10^2)^(d1) * ...  — build exponent digit by digit
        result = 1
        a %= MOD
        for digit in b:
            result = pow_mod(result, 10)   # result = result^10
            result = (result * pow_mod(a, digit)) % MOD
        return result
Explanation:

  1. Exponent b is too large to store — process digit by digit using the identity a^(10·q + d) = (a^q)^10 · a^d.
  2. Maintain running result; for each digit d, square result 10 times (via pow_mod(result, 10)) then multiply by a^d.
  3. All arithmetic mod 1337 prevents overflow.

Time: O(k · log d · log MOD) where k = len(b)  |  Space: O(1)

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

MOD = 1337

class Solution:
    def superPow(self, a: int, b: List[int]) -> int:
        if not b:
            return 1
        last = b.pop()
        part = self.superPow(a, b)
        # a^(10*prev + last) = (a^prev)^10 * a^last
        return (self._pow(part, 10) * self._pow(a, last)) % MOD

    def _pow(self, x: int, n: int) -> int:
        result, x = 1, x % MOD
        while n:
            if n & 1:
                result = (result * x) % MOD
            x = (x * x) % MOD
            n >>= 1
        return result
Explanation:

  1. Recursively compute power for all but the last digit, then combine: (prev^10) · a^last_digit.
  2. Same mathematical decomposition as the iterative version; mutates b via pop().

Time: O(k · log 10 · log MOD)  |  Space: O(k) recursion depth

8. Valid Perfect Square (Leetcode:367)#

Problem Statement

Given a positive integer num, write a function which returns True if num is a perfect square else False.

Follow up: Do not use any built-in library function such as sqrt.

Example 1:

Input: num = 16
Output: true

Example 2:

Input: num = 14
Output: false

Constraints:

1 <= num <= 2^31 - 1

Code and Explanation 

1
2
3
4
5
6
class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        x = num
        while x * x > num:
            x = (x + num // x) // 2
        return x * x == num
Explanation:

  1. Newton's method for √num: iterate x ← (x + num/x) / 2 until convergence.
  2. Integer division keeps everything in integer arithmetic — no floating point.
  3. Check x * x == num at the end; classic math approach distinct from binary search (see Binary Search doc for Sqrt(x)).

Time: O(log num)  |  Space: O(1)

1
2
3
4
5
6
7
class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        i = 1
        while num > 0:
            num -= i
            i += 2
        return num == 0
Explanation:

  1. Perfect squares are sums of first k odd numbers: 1 = 1, 4 = 1+3, 9 = 1+3+5, …
  2. Subtract successive odd integers; if we hit exactly 0, num is a perfect square.
  3. O(√num) but elegant number-theory insight.

Time: O(√num)  |  Space: O(1)

9. Rectangle Overlap (Leetcode:836)#

Problem Statement

An axis-aligned rectangle is represented as its bottom-left corner (x1, y1) and top-right corner (x2, y2).

Given two axis-aligned rectangles rec1 and rec2, return true if they overlap.

Example 1:

Input: rec1 = [0,0,2,2], rec2 = [1,1,3,3]
Output: true

Example 2:

Input: rec1 = [0,0,1,1], rec2 = [1,0,2,1]
Output: false

Example 3:

Input: rec1 = [0,0,1,1], rec2 = [2,2,3,3]
Output: false

Constraints:

rec1.length == 4
rec2.length == 4
-10^9 <= x1, y1, x2, y2 <= 10^9
x2 >= x1 and y2 >= y1 for both rectangles.

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
from typing import List

class Solution:
    def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) -> bool:
        # No overlap if separated on x OR on y
        if rec1[2] <= rec2[0] or rec2[2] <= rec1[0]:
            return False
        if rec1[3] <= rec2[1] or rec2[3] <= rec1[1]:
            return False
        return True
Explanation:

  1. Two axis-aligned rectangles overlap ⟺ their x-intervals and y-intervals both overlap.
  2. rec = [x1, y1, x2, y2] — x-range is [x1, x2), y-range is [y1, y2) (touching edges = no overlap per problem).
  3. Check separation on either axis; if neither separated, they overlap.

Time: O(1)  |  Space: O(1)

1
2
3
4
5
6
7
from typing import List

class Solution:
    def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) -> bool:
        x_overlap = min(rec1[2], rec2[2]) - max(rec1[0], rec2[0])
        y_overlap = min(rec1[3], rec2[3]) - max(rec1[1], rec2[1])
        return x_overlap > 0 and y_overlap > 0
Explanation:

  1. Intersection width = min(right edges) − max(left edges); same for height.
  2. Positive width and height means positive-area overlap.
  3. Equivalent logic, often easier to extend to intersection area problems.

Time: O(1)  |  Space: O(1)

10. Detect Squares (Leetcode:2013)#

Problem Statement

You are given a stream of points on the X-Y plane. Design an algorithm that:

  • Adds new points from the stream into a data structure. Duplicate points are allowed to be added more than once.
  • Counts the number of ways to form axis-aligned squares such that the point (x, y) belongs to the square and has an edge parallel to the X-axis.

Implement the DetectSquares class:

  • DetectSquares() Initializes the object with an empty data structure.
  • void add(int[] point) Adds a new point point = [x, y] to the data structure.
  • int count(int[] point) Counts the number of ways to form axis-aligned squares p belongs to.

Example 1:

Input:
["DetectSquares", "add", "add", "add", "count", "count", "add", "count"]
[[], [[3, 10]], [[11, 2]], [[3, 2]], [[11, 10]], [[14, 8]], [[11, 2]], [[11, 10]]]
Output: [null, null, null, null, 1, 0, null, 2]

Constraints:

point.length == 2
0 <= x, y <= 1000
At most 3000 calls to add and count.

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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
        total = 0
        for (px, py), cnt in self.points.items():
            if px == x or py == y:
                continue  # not a diagonal partner
            if abs(px - x) != abs(py - y):
                continue  # not equal side lengths
            # Other two corners of the axis-aligned square
            c1 = (x, py)
            c2 = (px, y)
            total += cnt * self.points.get(c1, 0) * self.points.get(c2, 0)
        return total
Explanation:

  1. Fix query point (x, y) as one corner; iterate all stored points (px, py) as potential diagonal corner.
  2. Skip if same row/column (not diagonal) or if |px−x| ≠ |py−y| (not a square diagonal).
  3. The other two corners are (x, py) and (px, y) — multiply point counts for all four corners (handles duplicates via frequency map).

Time: O(n) per count, O(1) per add  |  Space: O(n) points stored

 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
from collections import defaultdict

class DetectSquares:
    def __init__(self):
        self.points = defaultdict(int)
        self.by_sum = defaultdict(list)  # (x+y) -> list of (x, count)

    def add(self, point: list[int]) -> None:
        t = tuple(point)
        self.points[t] += 1
        self.by_sum[point[0] + point[1]].append((point[0], 1))

    def count(self, point: list[int]) -> int:
        x, y = point
        total = 0
        target_sum = x + y
        for px, _ in self.by_sum.get(target_sum, []):
            side = abs(px - x)
            if side == 0:
                continue
            py = target_sum - px
            c1 = (x, py)
            c2 = (px, y)
            total += self.points.get((px, py), 0) * self.points.get(c1, 0) * self.points.get(c2, 0)
        return total
Explanation:

  1. Points on the same diagonal of a square with (x, y) share the same midpoint — filter by x + y sum (or difference).
  2. Prunes search space when many points exist; same corner-counting logic once diagonal partner found.
  3. Useful when count is called frequently on large point sets.

Time: O(k) per count where k = points sharing diagonal sum  |  Space: O(n)

Skipped (Covered Elsewhere)#

Problem Reason
Happy Number (LC 202) Primary pattern is Fast and Slow Pointers — see Pattern 02
Sqrt(x) (LC 69) Primary pattern is Binary Search on Answer — see Pattern 09