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)
	{
		PrefixSum task = new PrefixSum();
		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
			}
		};
		task.printMatrix(matrix);
		task.changeByPrefixSum(matrix);
		System.out.print("\n ");
		task.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
// 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()
{
    PrefixSum *task = new PrefixSum();
    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}
    };

    task->printMatrix(matrix);
    task->changeByPrefixSum(matrix);
    cout << "\n ";
    task->printMatrix(matrix);
    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)
	{
		PrefixSum task = new PrefixSum();
		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
			}
		};
		task.printMatrix(matrix);
		task.changeByPrefixSum(matrix);
		Console.Write("\n ");
		task.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
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()
{
	$task = new PrefixSum();
	$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)
    );
	$task->printMatrix($matrix);
	$task->changeByPrefixSum($matrix);
	echo("\n ");
	$task->printMatrix($matrix);
}
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 task = new PrefixSum();
	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]
	];
	task.printMatrix(matrix);
	task.changeByPrefixSum(matrix);
	process.stdout.write("\n ");
	task.printMatrix(matrix);
}
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() :
    task = PrefixSum()
    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]
    ]
    task.printMatrix(matrix)
    task.changeByPrefixSum(matrix)
    print("\n ", end = "")
    task.printMatrix(matrix)

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() 
	task = PrefixSum.new()
	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]
	]
	task.printMatrix(matrix)
	task.changeByPrefixSum(matrix)
	print("\n ")
	task.printMatrix(matrix)
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)
        );
		task.printMatrix(matrix);
		task.changeByPrefixSum(matrix);
		print("\n ");
		task.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
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()
{
	let task: PrefixSum = PrefixSum();
	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]
	];
	task.printMatrix(matrix);
	task.changeByPrefixSum(&matrix);
	print("\n ", terminator: "");
	task.printMatrix(matrix);
}
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 task: PrefixSum = PrefixSum();
	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)
    );
	task.printMatrix(matrix);
	task.changeByPrefixSum(matrix);
	print("\n ");
	task.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

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.

New Comment