Posted on by Kalkicode
Code Matrix

# Maximum prefix sum in 2d array

The problem is to find the maximum prefix sum in a 2D array, where the prefix sum of an element is the sum of all the elements in the submatrix formed by the top-left corner of the array and the current element. In other words, we need to modify the given 2D matrix in such a way that each element represents the sum of the submatrix formed by the top-left corner of the array and the current element. The maximum prefix sum is the maximum value among all the elements in the modified matrix.

## Example

Consider the following 2D matrix:

``````1 4 3 7 2
2 4 3 8 3
4 1 6 7 1
5 4 3 7 12
1 5 10 1 2``````

After modifying the matrix to represent the prefix sum of each element, the new matrix will be:

``````1 5 8 15 17
3 11 17 32 37
7 16 28 50 56
12 25 40 69 87
13 31 56 86 106``````

The maximum prefix sum in this modified matrix is 106.

## Idea to Solve the Problem

To find the maximum prefix sum in a 2D array, we can use the concept of prefix sums. The prefix sum of each element in the 2D matrix can be calculated by following these steps:

1. First, we calculate the prefix sum for the first row and the first column separately. The prefix sum for the first row is calculated by adding the current element with the previous element in the same row. The prefix sum for the first column is calculated by adding the current element with the previous element in the same column.
2. Then, for the remaining elements in the matrix (excluding the first row and first column), the prefix sum is calculated by adding the current element with the previous element in the same row and the previous element in the same column. To avoid double-counting, we subtract the prefix sum of the previous element in the same row and column.

## Pseudocode

``````changeByPrefixSum(matrix):
row = number of rows in matrix
col = number of columns in matrix
for i from 1 to row-1:
matrix[i][0] = matrix[i-1][0] + matrix[i][0]
for i from 1 to col-1:
matrix[0][i] = matrix[0][i-1] + matrix[0][i]
for i from 1 to row-1:
for j from 1 to col-1:
matrix[i][j] = matrix[i-1][j] + matrix[i][j-1] - matrix[i-1][j-1] + matrix[i][j]``````

## Algorithm Explanation

1. The `changeByPrefixSum` function takes a 2D matrix 'matrix' as input.
2. It first gets the number of rows and columns in the matrix.
3. It calculates the prefix sum for the first row by adding each element with its previous element in the same row.
4. It calculates the prefix sum for the first column by adding each element with its previous element in the same column.
5. Then, it calculates the prefix sum for the remaining elements (excluding the first row and first column) by adding each element with its previous element in the same row and the previous element in the same column. To avoid double-counting, it subtracts the prefix sum of the previous element in the same row and column.
6. The modified matrix now represents the prefix sum of each element.
7. The function updates the matrix in place.

## Code Solution

``````/*
Java program for
Maximum prefix sum in 2d array
*/
public class PrefixSum
{
// Display matrix elements
public void printMatrix(int[][] matrix)
{
int row = matrix.length;
int col = matrix[0].length;
for (int i = 0; i < row; i++)
{
for (int j = 0; j < col; j++)
{
System.out.print(" " + matrix[i][j]);
}
System.out.print("\n");
}
}
public void changeByPrefixSum(int[][] matrix)
{
int row = matrix.length;
int col = matrix[0].length;
// Change element of first row
// By sum of previous element
for (int i = 1; i < row; ++i)
{
matrix[i][0] = matrix[i - 1][0] + matrix[i][0];
}
// Change element of first column
// By sum of previous element
for (int i = 1; i < col; ++i)
{
matrix[0][i] = matrix[0][i - 1] + matrix[0][i];
}
// Change remaining elements
for (int i = 1; i < row; ++i)
{
for (int j = 1; j < col; ++j)
{
matrix[i][j] = matrix[i - 1][j] + matrix[i][j - 1] -
matrix[i - 1][j - 1] + matrix[i][j];
}
}
}
public static void main(String[] args)
{
int[][] matrix = {
{
1 , 4 , 3 , 7 , 2
},
{
2 , 4 , 3 , 8 , 3
},
{
4 , 1 , 6 , 7 , 1
},
{
5 , 4 , 3 , 7 , 12
},
{
1 , 5 , 10 , 1 , 2
}
};
System.out.print("\n ");
}
}``````

#### Output

`````` 1 4 3 7 2
2 4 3 8 3
4 1 6 7 1
5 4 3 7 12
1 5 10 1 2

1 5 8 15 17
3 11 17 32 37
7 16 28 50 56
12 25 40 69 87
13 31 56 86 106``````
``````// Include header file
#include <iostream>
#define R 5
#define C 5
using namespace std;
/*
C++ program for
Maximum prefix sum in 2d array
*/
class PrefixSum
{
public:
// Display matrix elements
void printMatrix(int matrix[R][C])
{

for (int i = 0; i < R; i++)
{
for (int j = 0; j < C; j++)
{
cout << " " << matrix[i][j];
}
cout << "\n";
}
}
void changeByPrefixSum(int matrix[R][C])
{

// Change element of first row
// By sum of previous element
for (int i = 1; i < R; ++i)
{
matrix[i][0] = matrix[i - 1][0] + matrix[i][0];
}
// Change element of first column
// By sum of previous element
for (int i = 1; i < C; ++i)
{
matrix[0][i] = matrix[0][i - 1] + matrix[0][i];
}
// Change remaining elements
for (int i = 1; i < R; ++i)
{
for (int j = 1; j < C; ++j)
{
matrix[i][j] = matrix[i - 1][j] + matrix[i][j - 1] -
matrix[i - 1][j - 1] + matrix[i][j];
}
}
}
};
int main()
{
int matrix[R][C] = {
{1, 4, 3,  7, 2},
{2, 4, 3,  8, 3},
{4, 1, 6,  7, 1},
{5, 4, 3,  7, 12},
{1, 5, 10, 1, 2}
};

cout << "\n ";
return 0;
}``````

#### Output

`````` 1 4 3 7 2
2 4 3 8 3
4 1 6 7 1
5 4 3 7 12
1 5 10 1 2

1 5 8 15 17
3 11 17 32 37
7 16 28 50 56
12 25 40 69 87
13 31 56 86 106``````
``````// Include namespace system
using System;
/*
Csharp program for
Maximum prefix sum in 2d array
*/
public class PrefixSum
{
// Display matrix elements
public void printMatrix(int[,] matrix)
{
int row = matrix.GetLength(0);
int col = matrix.GetLength(1);
for (int i = 0; i < row; i++)
{
for (int j = 0; j < col; j++)
{
Console.Write(" " + matrix[i,j]);
}
Console.Write("\n");
}
}
public void changeByPrefixSum(int[,] matrix)
{
int row = matrix.GetLength(0);
int col = matrix.GetLength(1);
// Change element of first row
// By sum of previous element
for (int i = 1; i < row; ++i)
{
matrix[i,0] = matrix[i - 1,0] + matrix[i,0];
}
// Change element of first column
// By sum of previous element
for (int i = 1; i < col; ++i)
{
matrix[0,i] = matrix[0,i - 1] + matrix[0,i];
}
// Change remaining elements
for (int i = 1; i < col; ++i)
{
for (int j = 1; j < col; ++j)
{
matrix[i,j] = matrix[i - 1,j] + matrix[i,j - 1] -
matrix[i - 1,j - 1] + matrix[i,j];
}
}
}
public static void Main(String[] args)
{
int[,] matrix = {
{
1 , 4 , 3 , 7 , 2
},
{
2 , 4 , 3 , 8 , 3
},
{
4 , 1 , 6 , 7 , 1
},
{
5 , 4 , 3 , 7 , 12
},
{
1 , 5 , 10 , 1 , 2
}
};
Console.Write("\n ");
}
}``````

#### Output

`````` 1 4 3 7 2
2 4 3 8 3
4 1 6 7 1
5 4 3 7 12
1 5 10 1 2

1 5 8 15 17
3 11 17 32 37
7 16 28 50 56
12 25 40 69 87
13 31 56 86 106``````
``````package main
import "fmt"
/*
Go program for
Maximum prefix sum in 2d array
*/

// Display matrix elements
func printMatrix(matrix[][] int) {
var row int = len(matrix)
var col int = len(matrix[0])
for i := 0 ; i < row ; i++ {
for j := 0 ; j < col ; j++ {
fmt.Print(" ", matrix[i][j])
}
fmt.Print("\n")
}
}
func changeByPrefixSum(matrix[][] int) {
var row int = len(matrix)
var col int = len(matrix[0])
// Change element of first row
// By sum of previous element
for i := 1 ; i < row ; i++ {
matrix[i][0] = matrix[i - 1][0] + matrix[i][0]
}
// Change element of first column
// By sum of previous element
for i := 1 ; i < col ; i++ {
matrix[0][i] = matrix[0][i - 1] + matrix[0][i]
}
// Change remaining elements
for i := 1 ; i < col ; i++ {
for j := 1 ; j < col ; j++ {
matrix[i][j] = matrix[i - 1][j] + matrix[i][j - 1] -
matrix[i - 1][j - 1] + matrix[i][j]
}
}
}
func main() {

var matrix = [][] int {
{1, 4, 3,  7, 2},
{2, 4, 3,  8, 3},
{4, 1, 6,  7, 1},
{5, 4, 3,  7, 12},
{1, 5, 10, 1, 2}}
printMatrix(matrix)
changeByPrefixSum(matrix)
fmt.Print("\n ")
printMatrix(matrix)
}``````

#### Output

`````` 1 4 3 7 2
2 4 3 8 3
4 1 6 7 1
5 4 3 7 12
1 5 10 1 2

1 5 8 15 17
3 11 17 32 37
7 16 28 50 56
12 25 40 69 87
13 31 56 86 106``````
``````<?php
/*
Php program for
Maximum prefix sum in 2d array
*/
class PrefixSum
{
// Display matrix elements
public	function printMatrix(\$matrix)
{
\$row = count(\$matrix);
\$col = count(\$matrix[0]);
for (\$i = 0; \$i < \$row; \$i++)
{
for (\$j = 0; \$j < \$col; \$j++)
{
echo(" ".\$matrix[\$i][\$j]);
}
echo("\n");
}
}
public	function changeByPrefixSum(&\$matrix)
{
\$row = count(\$matrix);
\$col = count(\$matrix[0]);
// Change element of first row
// By sum of previous element
for (\$i = 1; \$i < \$row; ++\$i)
{
\$matrix[\$i][0] = \$matrix[\$i - 1][0] + \$matrix[\$i][0];
}
// Change element of first column
// By sum of previous element
for (\$i = 1; \$i < \$col; ++\$i)
{
\$matrix[0][\$i] = \$matrix[0][\$i - 1] + \$matrix[0][\$i];
}
// Change remaining elements
for (\$i = 1; \$i < \$col; ++\$i)
{
for (\$j = 1; \$j < \$col; ++\$j)
{
\$matrix[\$i][\$j] = \$matrix[\$i - 1][\$j] + \$matrix[\$i][\$j - 1] -
\$matrix[\$i - 1][\$j - 1] + \$matrix[\$i][\$j];
}
}
}
}

function main()
{
\$matrix = array(
array(1, 4, 3, 7, 2),
array(2, 4, 3, 8, 3),
array(4, 1, 6, 7, 1),
array(5, 4, 3, 7, 12),
array(1, 5, 10, 1, 2)
);
echo("\n ");
}
main();``````

#### Output

`````` 1 4 3 7 2
2 4 3 8 3
4 1 6 7 1
5 4 3 7 12
1 5 10 1 2

1 5 8 15 17
3 11 17 32 37
7 16 28 50 56
12 25 40 69 87
13 31 56 86 106``````
``````/*
Node JS program for
Maximum prefix sum in 2d array
*/
class PrefixSum
{
// Display matrix elements
printMatrix(matrix)
{
var row = matrix.length;
var col = matrix[0].length;
for (var i = 0; i < row; i++)
{
for (var j = 0; j < col; j++)
{
process.stdout.write(" " + matrix[i][j]);
}
process.stdout.write("\n");
}
}
changeByPrefixSum(matrix)
{
var row = matrix.length;
var col = matrix[0].length;
// Change element of first row
// By sum of previous element
for (var i = 1; i < row; ++i)
{
matrix[i][0] = matrix[i - 1][0] + matrix[i][0];
}
// Change element of first column
// By sum of previous element
for (var i = 1; i < col; ++i)
{
matrix[0][i] = matrix[0][i - 1] + matrix[0][i];
}
// Change remaining elements
for (var i = 1; i < col; ++i)
{
for (var j = 1; j < col; ++j)
{
matrix[i][j] = matrix[i - 1][j] + matrix[i][j - 1] -
matrix[i - 1][j - 1] + matrix[i][j];
}
}
}
}

function main()
{
var matrix = [
[1, 4, 3, 7, 2],
[2, 4, 3, 8, 3],
[4, 1, 6, 7, 1],
[5, 4, 3, 7, 12],
[1, 5, 10, 1, 2]
];
process.stdout.write("\n ");
}
main();``````

#### Output

`````` 1 4 3 7 2
2 4 3 8 3
4 1 6 7 1
5 4 3 7 12
1 5 10 1 2

1 5 8 15 17
3 11 17 32 37
7 16 28 50 56
12 25 40 69 87
13 31 56 86 106``````
``````#    Python 3 program for
#    Maximum prefix sum in 2d array
class PrefixSum :
#  Display matrix elements
def printMatrix(self, matrix) :
row = len(matrix)
col = len(matrix[0])
i = 0
while (i < row) :
j = 0
while (j < col) :
print(" ", matrix[i][j], end = "")
j += 1

print(end = "\n")
i += 1

def changeByPrefixSum(self, matrix) :
row = len(matrix)
col = len(matrix[0])
i = 1
#  Change element of first row
#  By sum of previous element
while (i < row) :
matrix[i][0] = matrix[i - 1][0] + matrix[i][0]
i += 1

i = 1
#  Change element of first column
#  By sum of previous element
while (i < col) :
matrix[0][i] = matrix[0][i - 1] + matrix[0][i]
i += 1

i = 1
#  Change remaining elements
while (i < col) :
j = 1
while (j < col) :
matrix[i][j] = matrix[i - 1][j] + matrix[i][j - 1] - matrix[i - 1][j - 1] + matrix[i][j]
j += 1

i += 1

def main() :
matrix = [
[1, 4, 3, 7, 2],
[2, 4, 3, 8, 3],
[4, 1, 6, 7, 1],
[5, 4, 3, 7, 12],
[1, 5, 10, 1, 2]
]
print("\n ", end = "")

if __name__ == "__main__": main()``````

#### Output

``````  1  4  3  7  2
2  4  3  8  3
4  1  6  7  1
5  4  3  7  12
1  5  10  1  2

1  5  8  15  17
3  11  17  32  37
7  16  28  50  56
12  25  40  69  87
13  31  56  86  106``````
``````#    Ruby program for
#    Maximum prefix sum in 2d array
class PrefixSum
#  Display matrix elements
def printMatrix(matrix)
row = matrix.length
col = matrix[0].length
i = 0
while (i < row)
j = 0
while (j < col)
print(" ", matrix[i][j])
j += 1
end

print("\n")
i += 1
end

end

def changeByPrefixSum(matrix)
row = matrix.length
col = matrix[0].length
i = 1
#  Change element of first row
#  By sum of previous element
while (i < row)
matrix[i][0] = matrix[i - 1][0] + matrix[i][0]
i += 1
end

i = 1
#  Change element of first column
#  By sum of previous element
while (i < col)
matrix[0][i] = matrix[0][i - 1] + matrix[0][i]
i += 1
end

i = 1
#  Change remaining elements
while (i < col)
j = 1
while (j < col)
matrix[i][j] = matrix[i - 1][j] + matrix[i][j - 1] -
matrix[i - 1][j - 1] + matrix[i][j]
j += 1
end

i += 1
end

end

end

def main()
matrix = [
[1, 4, 3, 7, 2],
[2, 4, 3, 8, 3],
[4, 1, 6, 7, 1],
[5, 4, 3, 7, 12],
[1, 5, 10, 1, 2]
]
print("\n ")
end

main()``````

#### Output

`````` 1 4 3 7 2
2 4 3 8 3
4 1 6 7 1
5 4 3 7 12
1 5 10 1 2

1 5 8 15 17
3 11 17 32 37
7 16 28 50 56
12 25 40 69 87
13 31 56 86 106
``````
``````/*
Scala program for
Maximum prefix sum in 2d array
*/
class PrefixSum()
{
// Display matrix elements
def printMatrix(matrix: Array[Array[Int]]): Unit = {
var row: Int = matrix.length;
var col: Int = matrix(0).length;
var i: Int = 0;
while (i < row)
{
var j: Int = 0;
while (j < col)
{
print(" " + matrix(i)(j));
j += 1;
}
print("\n");
i += 1;
}
}
def changeByPrefixSum(matrix: Array[Array[Int]]): Unit = {
var row: Int = matrix.length;
var col: Int = matrix(0).length;
var i: Int = 1;
// Change element of first row
// By sum of previous element
while (i < row)
{
matrix(i)(0) = matrix(i - 1)(0) + matrix(i)(0);
i += 1;
}
i = 1;
// Change element of first column
// By sum of previous element
while (i < col)
{
matrix(0)(i) = matrix(0)(i - 1) + matrix(0)(i);
i += 1;
}
i = 1;
// Change remaining elements
while (i < col)
{
var j: Int = 1;
while (j < col)
{
matrix(i)(j) = matrix(i - 1)(j) + matrix(i)(j - 1) -
matrix(i - 1)(j - 1) + matrix(i)(j);
j += 1;
}
i += 1;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: PrefixSum = new PrefixSum();
var matrix: Array[Array[Int]] = Array(
Array(1, 4, 3, 7, 2),
Array(2, 4, 3, 8, 3),
Array(4, 1, 6, 7, 1),
Array(5, 4, 3, 7, 12),
Array(1, 5, 10, 1, 2)
);
print("\n ");
}
}``````

#### Output

`````` 1 4 3 7 2
2 4 3 8 3
4 1 6 7 1
5 4 3 7 12
1 5 10 1 2

1 5 8 15 17
3 11 17 32 37
7 16 28 50 56
12 25 40 69 87
13 31 56 86 106``````
``````import Foundation;
/*
Swift 4 program for
Maximum prefix sum in 2d array
*/
class PrefixSum
{
// Display matrix elements
func printMatrix(_ matrix: [
[Int]
])
{
let row: Int = matrix.count;
let col: Int = matrix[0].count;
var i: Int = 0;
while (i < row)
{
var j: Int = 0;
while (j < col)
{
print(" ", matrix[i][j], terminator: "");
j += 1;
}
print(terminator: "\n");
i += 1;
}
}
func changeByPrefixSum(_ matrix: inout[
[Int]
])
{
let row: Int = matrix.count;
let col: Int = matrix[0].count;
var i: Int = 1;
// Change element of first row
// By sum of previous element
while (i < row)
{
matrix[i][0] = matrix[i - 1][0] + matrix[i][0];
i += 1;
}
i = 1;
// Change element of first column
// By sum of previous element
while (i < col)
{
matrix[0][i] = matrix[0][i - 1] + matrix[0][i];
i += 1;
}
i = 1;
// Change remaining elements
while (i < col)
{
var j: Int = 1;
while (j < col)
{
matrix[i][j] = matrix[i - 1][j] + matrix[i][j - 1] -
matrix[i - 1][j - 1] + matrix[i][j];
j += 1;
}
i += 1;
}
}
}
func main()
{
var matrix: [
[Int]
] = [
[1, 4, 3, 7, 2],
[2, 4, 3, 8, 3],
[4, 1, 6, 7, 1],
[5, 4, 3, 7, 12],
[1, 5, 10, 1, 2]
];
print("\n ", terminator: "");
}
main();``````

#### Output

``````  1  4  3  7  2
2  4  3  8  3
4  1  6  7  1
5  4  3  7  12
1  5  10  1  2

1  5  8  15  17
3  11  17  32  37
7  16  28  50  56
12  25  40  69  87
13  31  56  86  106``````
``````/*
Kotlin program for
Maximum prefix sum in 2d array
*/
class PrefixSum
{
// Display matrix elements
fun printMatrix(matrix: Array < Array < Int >> ): Unit
{
val row: Int = matrix.count();
val col: Int = matrix[0].count();
var i: Int = 0;
while (i < row)
{
var j: Int = 0;
while (j < col)
{
print(" " + matrix[i][j]);
j += 1;
}
print("\n");
i += 1;
}
}
fun changeByPrefixSum(matrix: Array < Array < Int >> ): Unit
{
val row: Int = matrix.count();
val col: Int = matrix[0].count();
var i: Int = 1;
// Change element of first row
// By sum of previous element
while (i < row)
{
matrix[i][0] = matrix[i - 1][0] + matrix[i][0];
i += 1;
}
i = 1;
// Change element of first column
// By sum of previous element
while (i < col)
{
matrix[0][i] = matrix[0][i - 1] + matrix[0][i];
i += 1;
}
i = 1;
// Change remaining elements
while (i < col)
{
var j: Int = 1;
while (j < col)
{
matrix[i][j] = matrix[i - 1][j] + matrix[i][j - 1] -
matrix[i - 1][j - 1] + matrix[i][j];
j += 1;
}
i += 1;
}
}
}
fun main(args: Array < String > ): Unit
{
val matrix: Array < Array < Int >> = arrayOf(
arrayOf(1, 4, 3, 7, 2),
arrayOf(2, 4, 3, 8, 3),
arrayOf(4, 1, 6, 7, 1),
arrayOf(5, 4, 3, 7, 12),
arrayOf(1, 5, 10, 1, 2)
);
print("\n ");
}``````

#### Output

`````` 1 4 3 7 2
2 4 3 8 3
4 1 6 7 1
5 4 3 7 12
1 5 10 1 2

1 5 8 15 17
3 11 17 32 37
7 16 28 50 56
12 25 40 69 87
13 31 56 86 106``````

## Output Explanation

The given Java code defines a `PrefixSum` class that calculates and displays the maximum prefix sum of a 2D matrix. The output displays the matrix before and after the prefix sum modification as follows:

Original Matrix:

``````1 4 3 7 2
2 4 3 8 3
4 1 6 7 1
5 4 3 7 12
1 5 10 1 2``````

Matrix after calculating the prefix sum:

``````1 5 8 15 17
3 11 17 32 37
7 16 28 50 56
12 25 40 69 87
13 31 56 86 106``````

The maximum prefix sum in this modified matrix is 106.

## Time Complexity

The time complexity of the provided solution is O(m * n), where 'm' is the number of rows and 'n' is the number of columns in the 2D matrix. The function iterates through each element in the matrix once to calculate the prefix sum. Since each operation takes constant time, the overall time complexity

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post