Prefix Sum For 2D Array (Prefix Sum Of Matrix)

Prefix Sum For 2D Array - Compute Prefix Sum For two Dimensional Array(Prefix Sum Of Matrix).

Given a 2-Dimensional array of integers array[R][C], where R and C are dimensions of the array (Row and Column). Find prefix sum 2d array for it.

Let Prefix sum 3d array be prefix[R][C]. Here prefix[i][j]  gives sum of all integers between  prefix[0][0] and prefix[i][j] (including both).

Example:

Input:

array[R][C] = {{2, 2, 2, 2},

               {2, 2, 2, 2},

               {2, 2, 2, 2},

               {2, 2, 2, 2}};

given 4x4 size 2-Dimensional  array

Output:

prefix sum is:

2 4 6 8

4 8 12 16

6 12 18 24

8 16 24 32

Image for formula creation.

Explanation:

Explanation of formula:

Consider the above image for the formula explanation. if we want to find prefix sum value in a white cell, we have to add the prefix sum of neighbor orange cells and subtract red cells to remove overlappings.

Step 0: 

Fill array[0] = prefix[0]

Step 1:

Fill first row and column using prefix sum for 1d array.

check this here for 1d prefix sum: prefix sum for 1d array

Step 2:

Fill all remaining cells using the formula discussed above.

Formula:

prefix[i][j] = array[i][j]

             + prefix[i - 1][j] 

             + prefix[i][j - 1] 

             - prefix[i - 1][j - 1];

Implementation:

C++ Implementation:

// C++ Program to find prefix sum of 2d array

#include <bits/stdc++.h>

using namespace std;

// Declaring size of the array

#define R 4 // Rows

#define C 4 // Columns

// Calculating prefix sum

void prefixSum2d(int array[R][C])

{

    int prefix[R][C];

    // Step 0:

    prefix[0][0] = array[0][0];

    // Step 1: Filling the first row and column

    // using prefix sum for 1d array

    for (int i = 1; i < C; i++)

        prefix[0][i] = prefix[0][i - 1] + array[0][i];

    for (int i = 1; i < R; i++)

        prefix[i][0] = prefix[i - 1][0] + array[i][0];

    // Step 2: Filling value in remaining cells

    // using formula

    for (int i = 1; i < R; i++)

    {

        for (int j = 1; j < C; j++)

        {

            prefix[i][j] = array[i][j]

                         + prefix[i - 1][j] 

                         + prefix[i][j - 1] 

                         - prefix[i - 1][j - 1];

        }

    }

    // Displaying final prefix sum of array

    cout << "prefix sum is:" << endl;

    for (int i = 0; i < R; i++)

    {

        for (int j = 0; j < C; j++)

            cout << prefix[i][j] << " ";

        cout << "\n";

    }

}

// Driver program to test above function

int main()

{

    int array[R][C] = {{2, 2, 2, 2},

                       {2, 2, 2, 2},

                       {2, 2, 2, 2},

                       {2, 2, 2, 2}};

    prefixSum2d(array);

    return 0;

}

Python Implementation:

# python Program to find prefix sum of 2d array

# Declaring size of the array

R = 4 # Rows

C = 4 # Columns

# Calculating prefix sum

def prefixSum2d(array):

    prefix = [[0 for a in range(R)] 

                for b in range(C)]

    # Step 0:

    prefix[0][0] = array[0][0]

    # Step 1: Filling the first row and column

    # using prefix sum for 1d array

    for i in range(1,C):

        prefix[0][i] = prefix[0][i - 1] + array[0][i]

    for i in range(1,R):

        prefix[i][0] = prefix[i - 1][0] + array[i][0]

    # Step 2: Filling value in remaining cells

    # using formula

    for i in range(1,R):

        for j in range(1,C):

            prefix[i][j] = (array[i][j]

                         + prefix[i - 1][j] 

                         + prefix[i][j - 1] 

                         - prefix[i - 1][j - 1])

    # Displaying final prefix sum of array

    print("prefix sum is:")

    for i in range(R):

        for j in range(C): 

            print(prefix[i][j], end=' ')

        print()

# Driver program to test above function

array = [

    [2,2,2,2],

    [2,2,2,2],

    [2,2,2,2],

    [2,2,2,2]

]

prefixSum2d(array)

Output:

prefix sum is:

2 4 6 8

4 8 12 16

6 12 18 24

8 16 24 32

Time Complexity: O(R*C)  

Auxiliary Space: O(R*C)

Read more:

check this here for 3D prefix sum: prefix sum for 3D array

Find the type of Quadrilateral with given 4 points of the quadrilateral here.

Hangman game in cpp and python

Prove numpy is faster than normal list