Title:

Find Minimum Sum Path

Link to LeetCode:

https://leetcode.com/problems/minimum-path-sum/

Specification:

Given a m x n grid filled with non-negative numbers,
find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.

Examples:

Example 1:

Input:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
Output: 7

Explanation: Because the path 1->3->1->1->1 minimizes the sum.

Example 2:

Initial Code and Signature: 

public interface MinimumPathFinder {
	
	public int minPathSum(int[][] grid);

}

Algorithm:

  1. Start from the destination and move upward over the diameter of the m*n matrix.
  2. Calculate the minimum path from that cell to the destination.
  3. Minimum path = minimum (minimum path from the right neighbor, minimum path from the bottom neighbor) + cost of the cell.
  4. Calculate the minimum path for all the cells in the same row with the cell.
  5. Calculate the minimum path for all the cells in the same column with the cell.
  6. Go the next cell on the diameter of the m*n matrix.
  7. Return the minimum path for cell [0,0].

Run-Time Analysis:

GitHub Project:

Code: 


import java.util.Arrays;
/**
 * 
 * @author Mahsa Sadi
 * 
 * @since 2020 - 03 - 31
 * 
 * License: Creative Commons
 * 
 * Copyright by Mahsa Sadi
 *
 */

public class MinimumPathFinderV2 implements MinimumPathFinder {
	
	/**
	 * 
	 * Problem: Minimum Sum Path
	 * 
	 * 
	 * Description:
	 * 
	 * Given a m x n grid filled with non-negative numbers, 
	 * find a path from top left to bottom right which minimizes the sum of all numbers along its path.
	 * Note: You can only move either down or right at any point in time.
	 * 
	 * 
	 * 
	 * Solution:
	 * 
	 * 1- Start from the destination and move over the diameter of the m*n matrix.
	 * 2- Calculate the minimum path from that cell to the destination.
	 *    Minimum path = minimum (minimum path from the right neighbor, minimum path from the bottom neighbor) + cost of the cell
	 * 3- Calculate the minimum path for all the cells in the same row with the cell.
	 * 4- Calculate the minimum path for all the cells in the same column with the cell.
	 * 5- Go the next cell on the diameter of the m*n matrix.
	 * 6- Return the minimum path for cell [0,0].
	 * 
	 * 
	 */

	int[][] localMinPath;
	

	@Override
	public int minPathSum(int[][] grid) 
	{

		localMinPath = new int[grid.length][grid[0].length];

		/* 
		 * 1- Start from the destination.
		 */
		int x = grid.length - 1;
		int y = grid[0].length - 1;

		/*
		 * Move over the diameter of the m * n matrix
		 */

		while (x >= 0 && y >= 0) 
		{
			/*
			 * 2- Calculate localMinPath for all the elements on the same row with x.
			 */
			for (int i = x; i >= 0; i--)
				updateLocalMinPath(grid, i, y);

			/*
			 * 3- Calculate localMinPath for all the elements on the same column with y.
			 */
			for (int j = y - 1; j >= 0; j--)
				updateLocalMinPath(grid, x, j);

			/*
			 * 4- Go to the next element on the diameter of the m*n matrix.
			 */
			x --;
			y --;
		}

		return localMinPath[0][0];
	}



	void updateLocalMinPath(int[][] grid, int x, int y) 
	{
		if (x == grid.length - 1)

		{ 
			if (y == grid[0].length - 1 )
				localMinPath [x][y] = grid [x][y];


			else 
				localMinPath [x][y] = localMinPath [x][y+1] + grid [x][y] ;
		}


		else if (y == grid[0].length - 1)
			localMinPath [x][y] = localMinPath [x+1][y] + grid [x][y] ;



		else 
			localMinPath [x][y] = Math.min(localMinPath [x][y+1], localMinPath [x+1][y]) + grid [x][y] ;
	}

}