Posted on by Kalkicode
Code Matrix

# Minimum sum path in a Matrix

The problem is to find the minimum sum path in a given matrix, where you can only move right or down. Starting from the top-left corner of the matrix, you need to reach the bottom-right corner while minimizing the sum of values along the path.

## Example

Consider the following matrix:

``````1  3  4  6  8  2  4  15
2  10 1  4  5  7  7  2
13 3  1  3  1  7  4  12
5  8  1  7  2  7  4  2
7  9  3  13 5  10 3  2``````

The minimum sum path in this matrix would be: `1 -> 3 -> 1 -> 1 -> 3 -> 1 -> 2 -> 7 -> 4 -> 2 -> 2`. The sum of the values along this path is 31.

## Idea to Solve the Problem

To solve this problem, we can use a recursive approach that explores all possible paths from the top-left corner to the bottom-right corner of the matrix. At each step, we have two choices: move down or move right. We keep track of the current row, current column, and the sum of values along the path. We continue recursively exploring both choices until we reach the bottom-right corner.

## Algorithm

1. Start from the top-left corner of the matrix `(0, 0)` with initial sum as 0.
2. If the current position is the bottom-right corner `(R-1, C-1)`, update the output if the current sum is less than the current output.
3. If the current position is within the matrix boundaries, explore the two choices: a. Move down: Call the function with updated row, column, count+1, k, and sum+current value. b. Move right: Call the function with updated row, column, count+1, k, and sum+current value.
4. At the end of the recursive process, the output will contain the minimum sum path.

## Pseudocode

``````path_sum(matrix, output, i, j, count, k, sum):
if count == k and output > sum:
output = sum
else if i < R and j < C:
path_sum(matrix, output, i+1, j, count+1, k, sum+matrix[i][j])
path_sum(matrix, output, i, j+1, count+1, k, sum+matrix[i][j])

minimum_path_sum(matrix):
output = INT_MAX
path_sum(matrix, &output, 0, 0, 0, R+C-1, 0)
print output

main:
matrix = ...  // Define the matrix
minimum_path_sum(matrix)``````

## Code Solution

``````// C Program
// Minimum sum path in a Matrix
#include <stdio.h>
#include <limits.h>

#define R 5
#define C 8

// Find the path sum of (0,0) to Matrix (R-1,C-1)
void path_sum(int matrix[R][C],int *output,int i ,int j,int count,int k,int sum)
{

if(count==k && *output > sum)
{
// When get a new result
*output = sum;
}
else if(i < R && j < C)
{
//Recursive execute method with new parameters
path_sum(matrix,output,i+1,j,count+1,k,sum+matrix[i][j]);
path_sum(matrix,output,i,j+1,count+1,k,sum+matrix[i][j]);
}
}

// Handles the request to find minimum path sum in a matrix
void minimum_path_sum(int matrix[R][C])
{
// Set initially max value
int output = INT_MAX;

// Calculate max path sum
path_sum(matrix,&output,0,0,0,R+C-1,0);

// Display find result
printf(" %d \n",output);
}

int main()
{
// Define element of matrix
int matrix[R][C] =
{
{1,  3,  4, 6,  8, 2,  4, 15 },
{2,  10, 1, 4,  5, 7,  7, 2  },
{13, 3,  1, 3,  1, 7,  4, 12 },
{5,  8,  1, 7,  2, 7,  4, 2  },
{7,  9,  3, 13, 5, 10, 3, 2  }
};
// 1 -> 3 -> 4 -> 1 -> 1 -> 3 -> 1 -> 2 -> 7 -> 4 -> 2 -> 2
minimum_path_sum(matrix);

return 0;
}``````

#### Output

`` 31``
``````/*
Java program
Minimum sum path in a Matrix
*/
// Define TreeNode
public class MyMatrix
{
public int output;
// Find the path sum of (0,0) to Matrix (R-1,C-1)
public void path_sum(int[][] matrix,
int i, int j,
int count, int k,
int sum,
int rows, int cols)
{
if (count == k && this.output > sum)
{
// When get a new result
this.output = sum;
}
else if (i < rows && j < cols)
{
//Recursive execute method with new parameters
path_sum(matrix, i + 1, j, count + 1, k, sum + matrix[i][j],rows,cols);
path_sum(matrix, i, j + 1, count + 1, k, sum + matrix[i][j],rows,cols);
}
}
// Handles the request to find max path sum in a matrix
public void minimum_path_sum(int[][] matrix)
{
int r = matrix.length;
int c = matrix[0].length;
// Set initially max value
this.output = Integer.MAX_VALUE;
// Calculate max path sum
path_sum(matrix, 0, 0, 0, r + c - 1, 0, r, c);
// Display find result
System.out.print("  " + this.output + " \n");
}
public static void main(String[] args)
{
MyMatrix obj = new MyMatrix();
int[][] matrix =
{
{1,  3,  4, 6,  8, 2,  4, 15 },
{2,  10, 1, 4,  5, 7,  7, 2  },
{13, 3,  1, 3,  1, 7,  4, 12 },
{5,  8,  1, 7,  2, 7,  4, 2  },
{7,  9,  3, 13, 5, 10, 3, 2  }
};
// 1 -> 3 -> 4 -> 1 -> 1 -> 3 -> 1 -> 2 -> 7 -> 4 -> 2 -> 2
obj.minimum_path_sum(matrix);
}
}``````

#### Output

``  31``
``````// Include header file
#include <iostream>
#include<limits.h>
#define R 5
#define C 8

using namespace std;
/*
C++ program
Minimum sum path in a Matrix
*/
//  Define TreeNode
class MyMatrix
{
public: int output;
//  Find the path sum of (0,0) to Matrix (R-1,C-1)
void path_sum(int matrix[R][C], int i, int j, int count, int k, int sum)
{
if (count == k && this->output > sum)
{
//  When get a new result
this->output = sum;
}
else if (i < R && j < C)
{
// Recursive execute method with new parameters
this->path_sum(matrix, i + 1, j, count + 1, k, sum + matrix[i][j]);
this->path_sum(matrix, i, j + 1, count + 1, k, sum + matrix[i][j]);
}
}
//  Handles the request to find max path sum in a matrix
void minimum_path_sum(int matrix[R][C])
{

//  Set initially max value
this->output = INT_MAX;
//  Calculate max path sum
this->path_sum(matrix, 0, 0, 0, R + C - 1, 0);
//  Display find result
cout << "  " << this->output << " \n";
}
};
int main()
{
MyMatrix obj = MyMatrix();
int matrix[R][C] =
{
{1,  3,  4, 6,  8, 2,  4, 15 },
{2,  10, 1, 4,  5, 7,  7, 2  },
{13, 3,  1, 3,  1, 7,  4, 12 },
{5,  8,  1, 7,  2, 7,  4, 2  },
{7,  9,  3, 13, 5, 10, 3, 2  }
};
//  1->3->4->1->1->3->1->2->7->4->2->2
obj.minimum_path_sum(matrix);
return 0;
}``````

#### Output

``  31``
``````// Include namespace system
using System;
/*
C# program
Minimum sum path in a Matrix
*/
//  Define TreeNode
public class MyMatrix
{
public int output;
//  Find the path sum of (0,0) to Matrix (R-1,C-1)
public void path_sum(int[,] matrix, int i, int j, int count, int k, int sum, int rows, int cols)
{
if (count == k && this.output > sum)
{
//  When get a new result
this.output = sum;
}
else if (i < rows && j < cols)
{
// Recursive execute method with new parameters
path_sum(matrix, i + 1, j, count + 1, k, sum + matrix[i,j], rows, cols);
path_sum(matrix, i, j + 1, count + 1, k, sum + matrix[i,j], rows, cols);
}
}
//  Handles the request to find max path sum in a matrix
public void minimum_path_sum(int[,] matrix)
{
int r = matrix.GetLength(0);
int c = matrix.GetLength(1);
//  Set initially max value
this.output = int.MaxValue;
//  Calculate max path sum
path_sum(matrix, 0, 0, 0, r + c - 1, 0, r, c);
//  Display find result
Console.Write("  " + this.output + " \n");
}
public static void Main(String[] args)
{
MyMatrix obj = new MyMatrix();
int[,] matrix =
{
{1,  3,  4, 6,  8, 2,  4, 15 },
{2,  10, 1, 4,  5, 7,  7, 2  },
{13, 3,  1, 3,  1, 7,  4, 12 },
{5,  8,  1, 7,  2, 7,  4, 2  },
{7,  9,  3, 13, 5, 10, 3, 2  }
};
//  1->3->4->1->1->3->1->2->7->4->2->2
obj.minimum_path_sum(matrix);
}
}``````

#### Output

``  31``
``````<?php
/*
Php program
Minimum sum path in a Matrix
*/
//  Define TreeNode
class MyMatrix
{
public \$output;
//  Find the path sum of (0,0) to Matrix (R-1,C-1)
public	function path_sum( & \$matrix, \$i, \$j, \$count, \$k, \$sum, \$rows, \$cols)
{
if (\$count == \$k && \$this->output > \$sum)
{
//  When get a new result
\$this->output = \$sum;
}
else if (\$i < \$rows && \$j < \$cols)
{
// Recursive execute method with new parameters
\$this->path_sum(\$matrix, \$i + 1, \$j, \$count + 1, \$k, \$sum + \$matrix[\$i][\$j], \$rows, \$cols);
\$this->path_sum(\$matrix, \$i, \$j + 1, \$count + 1, \$k, \$sum + \$matrix[\$i][\$j], \$rows, \$cols);
}
}
//  Handles the request to find max path sum in a matrix
public	function minimum_path_sum( & \$matrix)
{
\$r = count(\$matrix);
\$c = count(\$matrix[0]);
//  Set initially max value
\$this->output = PHP_INT_MAX;
//  Calculate max path sum
\$this->path_sum(\$matrix, 0, 0, 0, \$r + \$c - 1, 0, \$r, \$c);
//  Display find result
echo "  ". \$this->output ." \n";
}
}

function main()
{
\$obj = new MyMatrix();
\$matrix = array(
array(1, 3, 4, 6, 8, 2, 4, 15),
array(2, 10, 1, 4, 5, 7, 7, 2),
array(13, 3, 1, 3, 1, 7, 4, 12),
array(5, 8, 1, 7, 2, 7, 4, 2),
array(7, 9, 3, 13, 5, 10, 3, 2)
);
//  1->3->4->1->1->3->1->2->7->4->2->2
\$obj->minimum_path_sum(\$matrix);
}
main();``````

#### Output

``  31``
``````/*
Node Js program
Minimum sum path in a Matrix
*/
//  Define TreeNode
class MyMatrix
{
//  Find the path sum of (0,0) to Matrix (R-1,C-1)
path_sum(matrix, i, j, count, k, sum, rows, cols)
{
if (count == k && this.output > sum)
{
//  When get a new result
this.output = sum;
}
else if (i < rows && j < cols)
{
// Recursive execute method with new parameters
this.path_sum(matrix, i + 1, j, count + 1, k, sum + matrix[i][j], rows, cols);
this.path_sum(matrix, i, j + 1, count + 1, k, sum + matrix[i][j], rows, cols);
}
}
//  Handles the request to find max path sum in a matrix
minimum_path_sum(matrix)
{
var r = matrix.length;
var c = matrix[0].length;
//  Set initially max value
this.output = Number.MAX_VALUE;
//  Calculate max path sum
this.path_sum(matrix, 0, 0, 0, r + c - 1, 0, r, c);
//  Display find result
process.stdout.write("  " + this.output + " \n");
}
}

function main()
{
var obj = new MyMatrix();
var matrix =
[
[1, 3, 4, 6, 8, 2, 4, 15] ,
[2, 10, 1, 4, 5, 7, 7, 2] ,
[13, 3, 1, 3, 1, 7, 4, 12] ,
[5, 8, 1, 7, 2, 7, 4, 2] ,
[7, 9, 3, 13, 5, 10, 3, 2]
];
//  1->3->4->1->1->3->1->2->7->4->2->2
obj.minimum_path_sum(matrix);
}
main();``````

#### Output

``  31``
``````import sys

#  Python 3 program
#  Minimum sum path in a Matrix

#  Define TreeNode
class MyMatrix :

#  Find the path sum of (0,0) to Matrix (R-1,C-1)
def path_sum(self, matrix, i, j, count, k, sum, rows, cols) :
if (count == k and self.output > sum) :
#  When get a new result
self.output = sum

elif(i < rows and j < cols) :
# Recursive execute method with new parameters
self.path_sum(matrix, i + 1, j, count + 1, k, sum + matrix[i][j], rows, cols)
self.path_sum(matrix, i, j + 1, count + 1, k, sum + matrix[i][j], rows, cols)

#  Handles the request to find max path sum in a matrix
def minimum_path_sum(self, matrix) :
r = len(matrix)
c = len(matrix[0])
#  Set initially max value
self.output = sys.maxsize
#  Calculate max path sum
self.path_sum(matrix, 0, 0, 0, r + c - 1, 0, r, c)
#  Display find result
print("  ", self.output ," ")

def main() :
obj = MyMatrix()
matrix = [
[1, 3, 4, 6, 8, 2, 4, 15] ,
[2, 10, 1, 4, 5, 7, 7, 2] ,
[13, 3, 1, 3, 1, 7, 4, 12] ,
[5, 8, 1, 7, 2, 7, 4, 2] ,
[7, 9, 3, 13, 5, 10, 3, 2]
]
#  1->3->4->1->1->3->1->2->7->4->2->2
obj.minimum_path_sum(matrix)

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

#### Output

``   31``
``````#  Ruby program
#  Minimum sum path in a Matrix

#  Define TreeNode
class MyMatrix
# Define the accessor and reader of class MyMatrix
attr_accessor :output

#  Find the path sum of (0,0) to Matrix (R-1,C-1)
def path_sum(matrix, i, j, count, k, sum, rows, cols)
if (count == k && self.output > sum)
#  When get a new result
self.output = sum
elsif(i < rows && j < cols)
# Recursive execute method with new parameters
self.path_sum(matrix, i + 1, j, count + 1, k, sum + matrix[i][j], rows, cols)
self.path_sum(matrix, i, j + 1, count + 1, k, sum + matrix[i][j], rows, cols)
end

end

#  Handles the request to find max path sum in a matrix
def minimum_path_sum(matrix)
r = matrix.length
c = matrix[0].length
#  Set initially max value
self.output = (2 ** (0. size * 8 - 2))
#  Calculate max path sum
self.path_sum(matrix, 0, 0, 0, r + c - 1, 0, r, c)
#  Display find result
print("  ", self.output ," \n")
end

end

def main()
obj = MyMatrix.new()
matrix = [
[1, 3, 4, 6, 8, 2, 4, 15] ,
[2, 10, 1, 4, 5, 7, 7, 2] ,
[13, 3, 1, 3, 1, 7, 4, 12] ,
[5, 8, 1, 7, 2, 7, 4, 2] ,
[7, 9, 3, 13, 5, 10, 3, 2]
]
#  1->3->4->1->1->3->1->2->7->4->2->2
obj.minimum_path_sum(matrix)
end

main()``````

#### Output

``````  31
``````
``````/*
Scala program
Minimum sum path in a Matrix
*/
//  Define TreeNode
class MyMatrix(var output: Int)
{
def this()
{
this(Int.MaxValue)
}
//  Find the path sum of (0,0) to Matrix (R-1,C-1)
def path_sum(matrix: Array[Array[Int]], i: Int, j: Int, count: Int, k: Int, sum: Int, rows: Int, cols: Int): Unit = {
if (count == k && this.output > sum)
{
//  When get a new result
this.output = sum;
}
else if (i < rows && j < cols)
{
// Recursive execute method with new parameters
this.path_sum(matrix, i + 1, j, count + 1, k, sum + matrix(i)(j), rows, cols);
this.path_sum(matrix, i, j + 1, count + 1, k, sum + matrix(i)(j), rows, cols);
}
}
//  Handles the request to find max path sum in a matrix
def minimum_path_sum(matrix: Array[Array[Int]]): Unit = {
var r: Int = matrix.length;
var c: Int = matrix(0).length;
//  Set initially max value
this.output = Int.MaxValue;
//  Calculate max path sum
this.path_sum(matrix, 0, 0, 0, r + c - 1, 0, r, c);
//  Display find result
print("  " + this.output + " \n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: MyMatrix = new MyMatrix();
var matrix: Array[Array[Int]] = Array(
Array(1, 3, 4, 6, 8, 2, 4, 15),
Array(2, 10, 1, 4, 5, 7, 7, 2),
Array(13, 3, 1, 3, 1, 7, 4, 12),
Array(5, 8, 1, 7, 2, 7, 4, 2),
Array(7, 9, 3, 13, 5, 10, 3, 2)
);
//  1->3->4->1->1->3->1->2->7->4->2->2
obj.minimum_path_sum(matrix);
}
}``````

#### Output

``  31``
``````/*
Swift 4 program
Minimum sum path in a Matrix
*/
//  Define TreeNode
class MyMatrix
{
var output: Int;
init()
{
self.output = Int.max;
}
//  Find the path sum of (0,0) to Matrix (R-1,C-1)
func path_sum(_ matrix: [[Int]], _ i: Int, _ j: Int, _ count: Int, _ k: Int, _ sum: Int, _ rows: Int, _ cols: Int)
{
if (count == k && self.output > sum)
{
//  When get a new result
self.output = sum;
}
else if (i < rows && j < cols)
{
// Recursive execute method with new parameters
self.path_sum(matrix, i + 1, j, count + 1, k, sum + matrix[i][j], rows, cols);
self.path_sum(matrix, i, j + 1, count + 1, k, sum + matrix[i][j], rows, cols);
}
}
//  Handles the request to find max path sum in a matrix
func minimum_path_sum(_ matrix: [[Int]])
{
let r: Int = matrix.count;
let c: Int = matrix[0].count;
//  Set initially max value
self.output = Int.max;
//  Calculate max path sum
self.path_sum(matrix, 0, 0, 0, r + c - 1, 0, r, c);
//  Display find result
print("  ", self.output ," ");
}
}
func main()
{
let obj: MyMatrix = MyMatrix();
let matrix: [[Int]] =
[
[1, 3, 4, 6, 8, 2, 4, 15] ,
[2, 10, 1, 4, 5, 7, 7, 2] ,
[13, 3, 1, 3, 1, 7, 4, 12] ,
[5, 8, 1, 7, 2, 7, 4, 2] ,
[7, 9, 3, 13, 5, 10, 3, 2]
];
//  1->3->4->1->1->3->1->2->7->4->2->2
obj.minimum_path_sum(matrix);
}
main();``````

#### Output

``   31``
``````/*
Kotlin program
Minimum sum path in a Matrix
*/
//  Define TreeNode
class MyMatrix
{
var output: Int;
constructor()
{
this.output = Int.MAX_VALUE;
}
//  Find the path sum of (0,0) to Matrix (R-1,C-1)
fun path_sum(matrix: Array<Array<Int>> , i: Int, j: Int, count: Int, k: Int, sum: Int, rows: Int, cols: Int): Unit
{
if (count == k && this.output>sum)
{
//  When get a new result
this.output = sum;
}
else
if (i<rows && j<cols)
{
// Recursive execute method with new parameters
this.path_sum(matrix, i + 1, j, count + 1, k, sum + matrix[i][j], rows, cols);
this.path_sum(matrix, i, j + 1, count + 1, k, sum + matrix[i][j], rows, cols);
}
}
//  Handles the request to find max path sum in a matrix
fun minimum_path_sum(matrix: Array<Array<Int>> ): Unit
{
var r: Int = matrix.count();
var c: Int = matrix[0].count();
//  Set initially max value
this.output = Int.MAX_VALUE;
//  Calculate max path sum
this.path_sum(matrix, 0, 0, 0, r + c - 1, 0, r, c);
//  Display find result
print("  " + this.output + " \n");
}
}
fun main(args: Array<String>): Unit
{
var obj: MyMatrix = MyMatrix();
var matrix: Array<Array<Int>> = arrayOf(
arrayOf(1, 3, 4, 6, 8, 2, 4, 15),
arrayOf(2, 10, 1, 4, 5, 7, 7, 2),
arrayOf(13, 3, 1, 3, 1, 7, 4, 12),
arrayOf(5, 8, 1, 7, 2, 7, 4, 2),
arrayOf(7, 9, 3, 13, 5, 10, 3, 2)
);
//  1->3->4->1->1->3->1->2->7->4->2->2
obj.minimum_path_sum(matrix);
}``````

#### Output

``  31``

## Output Explanation

The mentioned C code implements the above recursive approach to find the minimum sum path in the matrix. It explores all possible paths and updates the output with the minimum sum. The output matches the expected minimum sum path in the matrix, which is `1 -> 3 -> 1 -> 1 -> 3 -> 1 -> 2 -> 7 -> 4 -> 2 -> 2`, and the sum is 31.

## Time Complexity

The time complexity of the mentioned solution is exponential, as it explores all possible paths from the top-left corner to the bottom-right corner. In the worst case, the time complexity is O(2^(R+C)), where R is the number of rows and C is the number of columns in the matrix.

## 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