Compute the Matrix Prefix Sum


Given a two-dimensional integer matrix, return a new matrix A of the same dimensions where each element is set to A[i][j] = sum(matrix[r][c]) for all r ≤ i, c ≤ j.

Constraints
n, m ≤ 250 where n and m are the number of rows and columns in matrix
matrix[i][j] ≤ 2**12

Example 1
Input

1
2
3
4
matrix = [
    [2, 3],
    [5, 7]
]
matrix = [
    [2, 3],
    [5, 7]
]

Output

1
2
3
4
[
    [2, 5],
    [7, 17]
]
[
    [2, 5],
    [7, 17]
]

Matrix Prefix Sum Algorithm

We can do this two steps. First step is to iterate all rows and make each row a prefix sum so it contains the sum between the begining of the row till current element. Similarly, we can iterate again, and then this time update each element in the matrix the prefix column sum. The complexity is O(NM) where N is the number of the rows and M is the number of the columns of the matrix.

The C++ matrix prefix sum implementation is:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<vector<int>> matrixPrefixSum(vector<vector<int>>& matrix) {
    if (matrix.empty()) return matrix;
    int rows = matrix.size();
    int cols = matrix[0].size();
    for (int r = 0; r < rows; ++ r) {
        for (int c = 1; c < cols; ++ c) {
            matrix[r][c] += matrix[r][c - 1];
        }
    }
    for (int r = 1; r < rows; ++ r) {
        for (int c = 0; c < cols; ++ c) {
            matrix[r][c] += matrix[r - 1][c];
        }
    }
    return matrix;
}
vector<vector<int>> matrixPrefixSum(vector<vector<int>>& matrix) {
    if (matrix.empty()) return matrix;
    int rows = matrix.size();
    int cols = matrix[0].size();
    for (int r = 0; r < rows; ++ r) {
        for (int c = 1; c < cols; ++ c) {
            matrix[r][c] += matrix[r][c - 1];
        }
    }
    for (int r = 1; r < rows; ++ r) {
        for (int c = 0; c < cols; ++ c) {
            matrix[r][c] += matrix[r - 1][c];
        }
    }
    return matrix;
}

See also: How to Compute the Product of Last K elements in Array using the Prefix Product Algorithm?

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
348 words
Last Post: Teaching Kids Programming - Dynamic Programming Algorithms to Compute the Number of Derangement Permutations
Next Post: Teaching Kids Programming - Is Subsequence Algorithm via Two Pointer

The Permanent URL is: Compute the Matrix Prefix Sum

Leave a Reply