Prefix Sum of Matrix (Or 2D Array)

19 June 2025

0

Given a matrix (or 2D array) a[][] of integers, find the prefix sum matrix for it. Let prefix sum matrix be psa[][]. The value of psa[i][j] contains the sum of all values which are above it or on the left of it.

Prerequisite: Prefix Sum – 1D

A simple solution is to find psa[i][j] by traversing and adding values from a[0][0] to a[i][j]. Time complexity of this solution is O(R * C * R * C).

An efficient solution is to use previously computed values to compute psa[i][j]. Unlike 1D array prefix sum, this is tricky, here if we simply add psa[i][j-1] and psa[i-1][j], we get sum of elements from a[0][0] to a[i-1][j-1] twice, so we subtract psa[i-1][j-1].

Example :

psa[3][3] = psa[2][3] + psa[3][2] -
            psa[2][2] + a[3][3]
          = 6 + 6 - 4 + 1
          = 9
The general formula: 
psa[i][j] = psa[i-1][j] + psa[i][j-1] - 
            psa[i-1][j-1] + a[i][j]

Corner Cases (First row and first column)
If i = 0 and j = 0
   psa[i][j] = a[i][j]
If i = 0 and j > 0
   psa[i][j] = psa[i][j-1] + a[i][j]
If i > 0 and j = 0
   psa[i][j] = psa[i-1][j] + a[i][j]

Below is the implementation of the above approach

C++

// C++ Program to find prefix sum of 2d array
#include <bits/stdc++.h>
using namespace std;
 
#define R 4
#define C 5
 
// calculating new array
void prefixSum2D(int a[][C])
{
    int psa[R][C];
    psa[0][0] = a[0][0];
 
    // Filling first row and first column
    for (int i = 1; i < C; i++)
        psa[0][i] = psa[0][i - 1] + a[0][i];
    for (int i = 1; i < R; i++)
        psa[i][0] = psa[i - 1][0] + a[i][0];
 
    // updating the values in the cells
    // as per the general formula
    for (int i = 1; i < R; i++) {
        for (int j = 1; j < C; j++)
 
            // values in the cells of new
            // array are updated
            psa[i][j] = psa[i - 1][j] + psa[i][j - 1]
                        - psa[i - 1][j - 1] + a[i][j];
    }
 
    // displaying the values of the new array
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++)
            cout << psa[i][j] << " ";
        cout << "\n";
    }
}
 
// driver code
int main()
{
    int a[R][C] = { { 1, 1, 1, 1, 1 },
                    { 1, 1, 1, 1, 1 },
                    { 1, 1, 1, 1, 1 },
                    { 1, 1, 1, 1, 1 } };
 
    prefixSum2D(a);
 
    return 0;
}

Java

// Java program to find prefix sum of 2D array
import java.util.*;
 
class GFG {
 
    // calculating new array
    public static void prefixSum2D(int a[][])
    {
        int R = a.length;
        int C = a[0].length;
 
        int psa[][] = new int[R][C];
 
        psa[0][0] = a[0][0];
 
        // Filling first row and first column
        for (int i = 1; i < C; i++)
            psa[0][i] = psa[0][i - 1] + a[0][i];
        for (int i = 1; i < R; i++)
            psa[i][0] = psa[i - 1][0] + a[i][0];
 
        // updating the values in the
        // cells as per the general formula.
        for (int i = 1; i < R; i++)
            for (int j = 1; j < C; j++)
 
                // values in the cells of new array
                // are updated
                psa[i][j] = psa[i - 1][j] + psa[i][j - 1]
                            - psa[i - 1][j - 1] + a[i][j];
 
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++)
                System.out.print(psa[i][j] + " ");
            System.out.println();
        }
    }
 
    // driver code
    public static void main(String[] args)
    {
        int a[][] = { { 1, 1, 1, 1, 1 },
                      { 1, 1, 1, 1, 1 },
                      { 1, 1, 1, 1, 1 },
                      { 1, 1, 1, 1, 1 } };
        prefixSum2D(a);
    }
}

Python3

# Python Program to find 
# prefix sum of 2d array
R = 4
C = 5
 
# calculating new array
def prefixSum2D(a) :
    global C, R
    psa = [[0 for x in range(C)] 
              for y in range(R)] 
    psa[0][0] = a[0][0]
 
    # Filling first row 
    # and first column
    for i in range(1, C) :
        psa[0][i] = (psa[0][i - 1] +
                       a[0][i])
    for i in range(0, R) :
        psa[i][0] = (psa[i - 1][0] +
                       a[i][0])
 
    # updating the values in 
    # the cells as per the 
    # general formula
    for i in range(1, R) :
        for j in range(1, C) :
 
            # values in the cells of 
            # new array are updated
            psa[i][j] = (psa[i - 1][j] +
                         psa[i][j - 1] -
                         psa[i - 1][j - 1] +
                           a[i][j])
 
    # displaying the values
    # of the new array
    for i in range(0, R) :
        for j in range(0, C) :
            print (psa[i][j], 
                   end = " ")
        print ()
 
# Driver Code
a = [[ 1, 1, 1, 1, 1 ],
     [ 1, 1, 1, 1, 1 ],
     [ 1, 1, 1, 1, 1 ],
     [ 1, 1, 1, 1, 1 ]]
 
prefixSum2D(a)
 
# This code is contributed by 
# Manish Shaw(manishshaw1)

C#

// C# program to find prefix
// sum of 2D array
using System;
 
class GFG 
{
 
    // calculating new array
    static void prefixSum2D(int [,]a)
    {
        int R = a.GetLength(0);
        int C = a.GetLength(1);
 
        int [,]psa = new int[R, C];
 
        psa[0, 0] = a[0, 0];
 
        // Filling first row
        // and first column
        for (int i = 1; i < C; i++)
            psa[0, i] = psa[0, i - 1] + 
                               a[0, i];
        for (int i = 1; i < R; i++)
            psa[i, 0] = psa[i - 1, 0] + 
                               a[i, 0];
  
        // updating the values in the
        // cells as per the general formula.
        for (int i = 1; i < R; i++)
            for (int j = 1; j < C; j++)
 
                // values in the cells of 
                // new array are updated
                psa[i, j] = psa[i - 1, j] + 
                            psa[i, j - 1] - 
                            psa[i - 1, j - 1] + 
                            a[i, j];
 
        for (int i = 0; i < R; i++) 
        {
            for (int j = 0; j < C; j++)
                Console.Write(psa[i, j] + " ");
            Console.WriteLine();
        }
    }
 
    // Driver Code
    static void Main()
    {
        int [,]a = new int[,]{{1, 1, 1, 1, 1},
                              {1, 1, 1, 1, 1},
                              {1, 1, 1, 1, 1},
                              {1, 1, 1, 1, 1}};
        prefixSum2D(a);
    }
}
 
// This code is contributed by manishshaw1

PHP

<?php
// PHP Program to find 
// prefix sum of 2d array
$R = 4;
$C = 5;
 
// calculating new array
function prefixSum2D($a)
{
    global $C, $R;
    $psa = array();
    $psa[0][0] = $a[0][0];
 
    // Filling first row 
    // and first column
    for ($i = 1; $i < $C; $i++)
        $psa[0][$i] = $psa[0][$i - 1] + 
                             $a[0][$i];
    for ($i = 0; $i < $R; $i++)
        $psa[$i][0] = $psa[$i - 1][0] + 
                             $a[$i][0];
 
    // updating the values in 
    // the cells as per the 
    // general formula
    for ($i = 1; $i < $R; $i++)
    {
        for ($j = 1; $j < $C; $j++)
 
            // values in the cells of 
            // new array are updated
            $psa[$i][$j] = $psa[$i - 1][$j] + 
                           $psa[$i][$j - 1] - 
                           $psa[$i - 1][$j - 1] + 
                           $a[$i][$j];
    }
 
    // displaying the values
    // of the new array
    for ($i = 0; $i < $R; $i++) 
    {
        for ($j = 0; $j < $C; $j++)
            echo ($psa[$i][$j]. " ");
        echo ("\n");
    }
}
 
// Driver Code
$a = array(array( 1, 1, 1, 1, 1 ),
           array( 1, 1, 1, 1, 1 ),
           array( 1, 1, 1, 1, 1 ),
           array( 1, 1, 1, 1, 1 ));
 
prefixSum2D($a);
 
// This code is contributed by 
// Manish Shaw(manishshaw1)
?>

Javascript

<script>
// Javascript program to find prefix sum of 2D array
 
// calculating new array
function prefixSum2D(a)
{
    let R = a.length;
        let C = a[0].length;
  
        let psa = new Array(R);
        for(let i = 0; i < R; i++)
        {
            psa[i] = new Array(C);
            for(let j = 0; j < C; j++)
                psa[i][j] = 0;
        }    
  
        psa[0][0] = a[0][0];
  
        // Filling first row and first column
        for (let i = 1; i < C; i++)
            psa[0][i] = psa[0][i - 1] + a[0][i];
        for (let i = 1; i < R; i++)
            psa[i][0] = psa[i - 1][0] + a[i][0];
  
        // updating the values in the
        // cells as per the general formula.
        for (let i = 1; i < R; i++)
            for (let j = 1; j < C; j++)
  
                // values in the cells of new array
                // are updated
                psa[i][j] = psa[i - 1][j] + psa[i][j - 1]
                            - psa[i - 1][j - 1] + a[i][j];
  
        for (let i = 0; i < R; i++) {
            for (let j = 0; j < C; j++)
                document.write(psa[i][j] + " ");
            document.write("<br>");
        }
}
 
// driver code
let a=[[ 1, 1, 1, 1, 1 ],
                      [ 1, 1, 1, 1, 1 ],
                      [ 1, 1, 1, 1, 1 ],
                      [ 1, 1, 1, 1, 1 ]];
prefixSum2D(a);
 
// This code is contributed by avanitrachhadiya2155
</script>

Output

1 2 3 4 5 
2 4 6 8 10 
3 6 9 12 15 
4 8 12 16 20

Time Complexity: O(R*C)
Auxiliary Space: O(R*C)

Another Efficient solution in which we also use the previously calculated sums in two main steps would be:

Calculate the vertical prefix sum for each column.
Calculate the horizontal prefix sum for each row.

Example

// c = the number of columns
// r = the number of rows
// a is the matrix

// calculating the vertical sum for each column in the Matrix 
for(column = 0 to column = c-1)
    for(row = 1 to row = r-1)
        a[row][column] += a[row-1][column];

// calculating the horizontal sum for each row in the Matrix 
for(row = 0 to row = r-1)
    for(column = 1 to column = c-1)
        a[row][column] += a[row][column -1];

Below is the Implementation of the above approach

C++

#include <iostream>
#include <iomanip>
using namespace std;
void prefixSum(int arr[3][3], int n);
void print(int arr[3][3], int n);
int main()
{
    int n = 3;
    int arr[3][3] = {{10,20,30},
                     {5, 10, 20},
                     {2, 4, 6}
                    };
    prefixSum(arr, n);
      print(arr, n);
 
}
void prefixSum(int arr[3][3], int n) {
    //vertical prefixsum
    for (int j = 0; j < n; j++) {
        for (int i = 1; i < n; i++) {
            arr[i][j] += arr[i-1][j];
        }
    }
    //horizontal prefixsum
    for (int i = 0; i < n; i++) {
        for (int j = 1; j < n; j++) {
            arr[i][j] += arr[i][j-1];
        }
    }
}
 
 
void print(int arr[3][3], int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << setw(3) << left << arr[i][j] << " ";
        }
        cout << '\n';
    }
}

Java

import java.io.*;
import java.lang.*;
import java.util.*;
public class GFG {
  public static void main(String[] args)
  {
    int n = 3;
    int arr[][] = new int[][] { { 10, 20, 30 },
                               { 5, 10, 20 },
                               { 2, 4, 6 } };
    prefixSum(arr, n);
    print(arr, n);
  }
  static void prefixSum(int arr[][], int n)
  {
     
    // vertical prefixsum
    for (int j = 0; j < n; j++) {
      for (int i = 1; i < n; i++) {
        arr[i][j] += arr[i - 1][j];
      }
    }
     
    // horizontal prefixsum
    for (int i = 0; i < n; i++) {
      for (int j = 1; j < n; j++) {
        arr[i][j] += arr[i][j - 1];
      }
    }
  }
  static void print(int arr[][], int n)
  {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        System.out.print(arr[i][j] + " ");
      }
      System.out.println();
    }
  }
}
 
// This code is contributed by ishankhandelwals.

Python3

def prefixsum(arr, n):
    # vertical prefixsum
    for j in range(n):
        for i in range(1, n):
            arr[i][j] += arr[i - 1][j]
             
    # horizontal prefixsum
    for i in  range(n):
        for j in range(1, n):
            arr[i][j] += arr[i][j - 1]
             
def printarr(arr, n):
    for i in range(n):
        for j in range(n):
            print(arr[i][j], end = " ")
        print()
         
# Driver Code
n = 3
arr = [[10,20,30],[5,10,20],[2,4,6]]
prefixsum(arr,n)
printarr(arr,n)  
 
# This code is contributed by
# Vibhu Karnwal

C#

// C# code for above approach
using System;
public class gfg
{
  public static void prefixSum(int[,] arr,int n){
    for (int j = 0; j < n; j++) {
      for (int i = 1; i < n; i++) {
        arr[i,j] += arr[i-1,j];
      }
    }
     
    //horizontal prefixsum
    for (int i = 0; i < n; i++) {
      for (int j = 1; j < n; j++) {
        arr[i,j] += arr[i,j-1];
      }
    }
  }
  public static void print(int[,] arr,int n){
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        Console.Write("{0} ",arr[i,j]);
      }
      Console.WriteLine();
    }
 
  }
 
  public static void Main(string[] args)
  {
    int n = 3;
    int[ , ] arr = new int[3,3] {{10,20,30},
                                 {5, 10, 20},
                                 {2, 4, 6}
                                } ;
    prefixSum(arr, n);
    print(arr, n);
  }
}
 
// This code is contributed by ishankhandelwals.

Javascript

// Js code for above approach
function prefixSum(arr, n) {
    //vertical prefixsum
    for (let j = 0; j < n; j++) {
        for (let i = 1; i < n; i++) {
            arr[i][j] += arr[i - 1][j];
        }
    }
    //horizontal prefixsum
    for (let i = 0; i < n; i++) {
        for (let j = 1; j < n; j++) {
            arr[i][j] += arr[i][j - 1];
        }
    }
}
function print(arr, n) {
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            console.log(arr[i][j]);
        }
    }
}
let n = 3;
let arr= [[ 10, 20, 30 ],
        [5, 10, 20 ],
        [ 2, 4, 6 ]];
prefixSum(arr, n);
print(arr, n);
 
// This code is contributed by ishankhandelwals.

Output

10  30  60  
15  45  95  
17  51  107

Time Complexity: O(R*C), where R and C are the Rows and Columns of the given matrix respectively.
Auxiliary Space: O(R*C)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Prefix Sum of Matrix (Or 2D Array)

C++

Java

Python3

C#

PHP

Javascript

C++

Java

Python3

C#

Javascript

Working with Titles and Heading – Python docx Module

Creating a Receipt Calculator using Python

One Liner for Python if-elif-else Statements

LEAVE A REPLY Cancel reply

Most Popular

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

Interviewed With Kyle Smith – Founder and CEO of Escalated by Shauli Zacks

EDITOR PICKS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR POSTS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR CATEGORY

ABOUT US

FOLLOW US