Module 2.3 ⏱ 35 min read ⚡ Matrices & Precomputation

Prefix Sums & Matrix Manipulation

Transform costly range-sum queries into instant $O(1)$ lookups using precomputed cumulative sums and master multi-directional 2D grid traversals.

1. 1D and 2D Prefix Sum Arrays

A prefix sum array precomputes cumulative totals so that the sum of any subarray between indices $L$ and $R$ can be found in constant time: `sum(L, R) = prefix[R + 1] - prefix[L]`.

In 2D matrices, this concept expands into a 2D prefix sum grid. By tracking cumulative subgrid areas, you can compute the sum of any arbitrary subrectangle defined by coordinates $(r_1, c_1)$ and $(r_2, c_2)$ in $O(1)$ time by using inclusion-exclusion principles across overlapping areas.

2. Matrix Traversal & Spiral Layouts

Two-dimensional grids require deliberate navigation strategies. Beyond standard row-major and column-major traversals, problems like spiral matrix layouts require dynamic boundary contraction (top, bottom, left, right pointers) to peel outer rings layer by layer.

3. Matrix Rotation & In-Place Transformations

Many interview problems require transforming 2D matrices in-place (without allocating extra $O(n^2)$ space). For instance, rotating a square matrix by 90 degrees clockwise can be elegantly achieved by first executing a matrix transpose (swapping elements across the main diagonal) followed by reversing each individual row.

// C++ Solution: Rotate Image by 90 Degrees Clockwise In-Place
#include <vector>
#include <algorithm>

class Solution {
public:
    void rotate(std::vector<std::vector<int>>& matrix) {
        int n = matrix.size();
        // Step 1: Transpose the matrix
        for (int i = 0; i < n; ++i) {
            for (int j = i; j < n; ++j) {
                std::swap(matrix[i][j], matrix[j][i]);
            }
        }
        // Step 2: Reverse each row
        for (int i = 0; i < n; ++i) {
            std::reverse(matrix[i].begin(), matrix[i].end());
        }
    }
};
            

# Python Solution: Rotate Image by 90 Degrees Clockwise In-Place
class Solution:
    def rotate(self, matrix: list[list[int]]) -> None:
        n = len(matrix)
        # Step 1: Transpose matrix
        for i in range(n):
            for j in range(i, n):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        # Step 2: Reverse each row
        for i in range(n):
            matrix[i].reverse()
            

// Java Solution: Rotate Image by 90 Degrees Clockwise In-Place
class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        // Step 1: Transpose
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
        // Step 2: Reverse rows
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n / 2; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[i][n - 1 - j];
                matrix[i][n - 1 - j] = temp;
            }
        }
    }
}
            

4. Homework & Quiz Overview

To secure your understanding, practice coding range sum query implementations using precomputed prefix arrays and dry-run boundary updates for matrix rotations and spiral traversals.

Quick Check: Test Your Intuition

What is the time complexity required to answer a range sum query on a 1D array after the prefix sum array has been precomputed?