Maximum path sum in matrix Editorial

Practice Problem Link: https://workat.tech/problem-solving/practice/max-path-sum-matrix

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a matrix M of size n*m, find the maximum path sum. A valid path starts from any element in the 1st row and ends at any element in the last row, with valid moves being down, diagonally to left, and diagonally to right.

Naive Approach

The naive approach will be to use a brute force recursion to try moving to all the possible cells, from the current cell, and calculating the sum that occurred in each path. Then, we return the maximum sum obtained out of all these path sums.

Analysis

• Time Complexity: O(3^m)
• Space Complexity: O(1)

Implementation

C++

int answer = 0;
void maxPath(int i, int j, int sum, vector<vector<int>>& M) {
	if(i == M.size() - 1) {
		answer = max(answer, sum + M[i][j]);
		return;
	}
	sum += M[i][j];
	maxPath(i + 1, j, sum, M);
	sum -= M[i][j];
	if(j > 0) {
		sum += M[i][j];
		maxPath(i + 1, j - 1, sum, M);
		sum -= M[i][j];
	}
	if(j < M[0].size() - 1) {
		sum += M[i][j];
		maxPath(i + 1, j + 1, sum, M);
		sum -= M[i][j];
	}
}
int findMaxPath(vector<vector<int>> &M) {
    answer = 0;
	for (int i = 0; i < M[0].size(); i++) {
		maxPath(0, i, 0, M);
	}
	return answer;
}

Java

class Solution {
	int answer = 0;
	void maxPath(int i, int j, int sum, int[][] M) {
		if(i == M.length - 1) {
			answer = Math.max(answer, sum + M[i][j]);
			return;
		}
		sum += M[i][j];
		maxPath(i + 1, j, sum, M);
		sum -= M[i][j];
		if(j > 0) {
			sum += M[i][j];
			maxPath(i + 1, j - 1, sum, M);
			sum -= M[i][j];
		}
		if(j < M[0].length - 1) {
			sum += M[i][j];
			maxPath(i + 1, j + 1, sum, M);
			sum -= M[i][j];
		}
	}
	int findMaxPath(int[][] M) {
		answer = 0;
		for (int i = 0; i < M[0].length; i++) {
			maxPath(0, i, 0, M);
		}
		return answer;
	}
}

Optimal Approach

We can start from the maximum value in the first row. Now for every element, we can update the result with the maximum value to be included in the maximum sum path. Finally if the path sum is greater than current result, we update our result. Finally we can return the result which stores the maximum path sum value.

Analysis

• Time Complexity: O(n * m)
• Space Complexity: O(n * m)

Implementation

C++

int findMaxPath(vector<vector<int>> &M) {
    int n = M.size();
	int m = M[0].size();
	int maxPathSum = INT_MIN;
	for (int i = 1; i < n; i++) {
		maxPathSum = INT_MIN;
		for (int j = 0; j < m; j++) {
			if(j > 0 && j < m - 1) {
				M[i][j] += max({M[i - 1][j], M[i - 1][j - 1], M[i - 1][j + 1]});
			}
			else if(j > 0) {
				M[i][j] += max(M[i - 1][j], M[i - 1][j - 1]);
			}
			else if(j < m - 1) {
				M[i][j] += max(M[i - 1][j], M[i - 1][j + 1]);
			}
			maxPathSum = max(maxPathSum, M[i][j]);
		}
	}
	return maxPathSum;
}

Java

class Solution {
	int max(int a, int b) {
		return (a > b ? a : b);
	}
	int findMaxPath(int[][] M) {
		int n = M.length;
		int m = M[0].length;
		int maxPathSum = Integer.MIN_VALUE;
		for (int i = 1; i < n; i++) {
			maxPathSum = Integer.MIN_VALUE;
			for (int j = 0; j < m; j++) {
				if(j > 0 && j < m - 1) {
					M[i][j] += max(max(M[i - 1][j], M[i - 1][j - 1]), M[i - 1][j + 1]);
				}
				else if(j > 0) {
					M[i][j] += max(M[i - 1][j], M[i - 1][j - 1]);
				}
				else if(j < m - 1) {
					M[i][j] += max(M[i - 1][j], M[i - 1][j + 1]);
				}
				maxPathSum = max(maxPathSum, M[i][j]);
			}
		}
		return maxPathSum;
	}
}