Prefix Sum of Matrix (Or 2D Array) in C++

In this problem, we are given a 2D array of integer values mat[][]. Our task is to print the prefix sum matrix of mat.

Prefix sum matrix: every element of the matrix is the sum elements above and left of it. i.e

prefixSum[i][j] = mat[i][j] + mat[i-1][j]...mat[0][j] + mat[i][j-1] +... mat[i][0].

Let’s take an example to understand the problem

Input: arr =[    [4   6   1]    [5   7   2]    [3   8   9] ] Output:[    [4   10   11]    [9   22   25]    [12   33   45] ]

To solve this problem, one simple solution is finding prefixSum by traversing all elements till i,j position and add them. But it is a bit complex for the system.

A more effective solution will be using the formula for finding the values of elements of prefixSum matrix.

The general formula for element at ij position is

prefixSum[i][j] = prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1] + a[i][j]

Some specail cases are

For i = j = 0, prefixSum[i][j] = a[i][j] For i = 0 and j > 0, prefixSum[i][j] = prefixSum[i][j-1] + a[i][j] For i > 0 and j = 0, prefixSum[i][j] = prefixSum[i-1][j] + a[i][j]

The code to show the implementation of our solution

Example

 Live Demo

#include <iostream> using namespace std; #define R 3 #define C 3 void printPrefixSum(int a[][C]) {    int prefixSum[R][C];    prefixSum[0][0] = a[0][0];    for (int i = 1; i < C; i++)    prefixSum[0][i] = prefixSum[0][i - 1] + a[0][i];    for (int i = 0; i < R; i++)    prefixSum[i][0] = prefixSum[i - 1][0] + a[i][0];    for (int i = 1; i < R; i++) {       for (int j = 1; j < C; j++)       prefixSum[i][j]=prefixSum[i- 1][j]+prefixSum[i][j- 1]-prefixSum[i- 1][j- 1]+a[i][j];    }    for (int i = 0; i < R; i++) {       for (int j = 0; j < C; j++)       cout<<prefixSum[i][j]<<"\t";       cout<<endl;    } } int main() {    int mat[R][C] = {       { 1, 2, 3},       { 4, 5, 6},       { 7, 8, 9}    };    cout<<"The prefix Sum Matrix is :\n";    printPrefixSum(mat);    return 0; }

Output

The prefix Sum Matrix is : 1   3   6 5   12   21 12   27   45