Math & Geometry Pattern

The Math & Geometry pattern uses mathematical equations and coordinate offsets to solve matrix transformations, grid navigation, and arithmetic optimization tasks in-place without allocating extra storage.

Recognition Signals

You should consider this pattern if you see any of the following cues in the problem description:

• The problem involves coordinate systems, points, lines, circles, or angles.
• The input is a 2D matrix representing an image, map, or grid that must be rotated, flipped, or navigated spirally.
• The task requires mathematical properties like divisibility, prime numbers, greatest common divisor (GCD), or fast exponentiation.

How It Works

Instead of storing states in extra structures, you use geometric properties:

• Matrix Transpose & Reverse: To rotate a square matrix by 90 degrees clockwise in-place, swap elements across the main diagonal (transpose), then reverse each row.
• Inward Boundary Shrinking: To traverse a matrix spirally, maintain four boundaries (top, bottom, left, right) and loop, shifting them inward.

For example, to transpose a 2D array:

1. Iterate r from 0 to n - 1.
2. Iterate c from r to n - 1.
3. Swap matrix[r][c] and matrix[c][r].

Complexity, With Caveats

• Time Complexity: O(n²) for 2D matrix transformations (where n is the dimension of the grid) as every cell is visited once. O(log N) for arithmetic operations like binary exponentiation or Euclidean GCD.
• Space Complexity: O(1) auxiliary space, as calculations are performed in-place.

Minimal Code Template

public class MathGeometryTemplate {
    // In-Place 90-Degree Clockwise Matrix Rotation
    public void rotate(int[][] matrix) {
        int n = matrix.length;

        // Step 1: Transpose
        for (int r = 0; r < n; r++) {
            for (int c = r; c < n; c++) {
                int temp = matrix[r][c];
                matrix[r][c] = matrix[c][r];
                matrix[c][r] = temp;
            }
        }

        // Step 2: Reverse Rows
        for (int r = 0; r < n; r++) {
            int left = 0;
            int right = n - 1;
            while (left < right) {
                int temp = matrix[r][left];
                matrix[r][left] = matrix[r][right];
                matrix[r][right] = temp;
                left++;
                right--;
            }
        }
    }
}

# In-Place 90-Degree Clockwise Matrix Rotation
def rotate(matrix: list[list[int]]) -> None:
    n = len(matrix)

    # Step 1: Transpose
    for r in range(n):
        for c in range(r, n):
            matrix[r][c], matrix[c][r] = matrix[c][r], matrix[r][c]

    # Step 2: Reverse Rows
    for r in range(n):
        matrix[r].reverse()

#include <vector>
#include <algorithm>

class MathGeometryTemplate {
public:
    // In-Place 90-Degree Clockwise Matrix Rotation
    void rotate(std::vector<std::vector<int>>& matrix) {
        int n = matrix.size();

        // Step 1: Transpose
        for (int r = 0; r < n; r++) {
            for (int c = r; c < n; c++) {
                std::swap(matrix[r][c], matrix[c][r]);
            }
        }

        // Step 2: Reverse Rows
        for (int r = 0; r < n; r++) {
            std::reverse(matrix[r].begin(), matrix[r].end());
        }
    }
};

Where This Pattern Falls Short

• Rectangular matrix constraints: The transpose and reverse method only works on square matrices (n x n). If the matrix is rectangular (m x n), transposing in-place requires complex index cycling or allocating a new output matrix.
• Float precision limitations: Geometric problems involving division (like slope calculation or intersection coordinates) can suffer from floating-point inaccuracies. You must use cross-multiplication or integer keys instead of floats in hash tables.

Related Patterns, Compared

• Arrays & Hashing: choose this instead when you need to match coordinates or check for duplicates, using a hash map to group points by a key (e.g. group points on the same line).
• Graphs: choose this instead when the grid traversal is not symmetric, requiring pathfinding with obstacles.

Frequently Asked Questions

Why does transposing and reversing rows result in a 90-degree clockwise rotation? Transposing swaps the rows and columns, turning row i into column i. Reversing the rows then flips the columns horizontally, completing the rotation.

How do we avoid float division issues when calculating lines? Instead of storing the slope as a float dy / dx, store it as a reduced fraction pair (dy / gcd(dy, dx), dx / gcd(dy, dx)) as a key in a hash map.

What does this pattern test in interviews? It tests your ability to visualize coordinate grids, manage indices, and implement in-place swaps without extra allocations.