Solve Leetcode Problems and Get Offers From Your Dream Companies||Minimum Path Sum
Tags: algorithms, programming, java
Published: 2021-03-17 19:03:16


## Leetcode Problem 64: Minimum Path Sum



![](https://cdn-images-1.medium.com/max/2560/1*FwiDnKdjuB0HAB3IGzYyEg.png)

In this series, I am going to solve Leetcode medium problems live with my friends, which you can see on our youtube channel. Today we will do Problem Leetcode: 64. Minimum Path Sum

A little bit about me, I have offers from **Uber** **India** and **Amazon** **India** in the past, and I am currently working for **Booking.com** in Amsterdam.

## Motivation to learn algorithms
[**Solve Leetcode Problems and Get Offers From Your Dream Companies**](https://medium.com/leetcode-simplified/solve-leetcode-problems-and-get-offers-from-your-dream-companies-2786415be0b7)

## Problem Statement

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

### **Example 1:**

![](https://cdn-images-1.medium.com/max/2000/1*FwpRxGUmjzjlhWZ6OQ_sWQ.png)

    Input: grid = [[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:

    Input: grid = [[1,2,3],[4,5,6]]
    Output: 12

### **Constraints:**

* m == grid.length

* n == grid[i].length

* 1 <= m, n <= 200

* 0 <= grid[i][j] <= 100

## Youtube Discussion
{% youtube bRb1uMqq41U %}
## Solution

### Approach 1: Brute Force

The Brute Force approach involves recursion. For each element, we consider two paths, rightwards and downwards, and find the minimum sum out of those two. It specifies whether we need to take the right step or a downward step to minimize the sum.

**cost(i, j) = grid[i][j] + min(cost(i+1, j), cost(i, j+1))**

The following code implements this algorithm:

## C++ Solution
{% gist https://gist.github.com/SudhanshuGulhane/feae2dc6662c13c4a31d612f55ffc838.js %}
## Java Solution
{% gist https://gist.github.com/SudhanshuGulhane/0354eeda66a8d80fa96cb101f98f2fd1.js %}
### Complexity Analysis

**The time complexity is O(2^(m+n))**

The time complexity is O(m+n)

## We can solve this problem in O(n*m) time complexity.

The idea is to calculate, for each index(i, j) find the min path from the top left to the index (i, j).

**First Row and Column Cases**

In the first row, we can move only right, and hence to reach any index in the first row the min path sum is the sum of all elements from the top left to that index.

For the first column, we can move only down, and hence to reach any index in the first row the min path sum is the sum of all elements from the top left to that index.

**Any other Case**

Now to reach index (i, j) we have two options

 1. we reach from the index (i-1,j)

 2. or we reach from the index (i, j-1)

We will choose the minimum of these two indexes. If we apply the same intuition for the rest of the grid we will find the min path sum from the top left to right bottom.

## C++ Solution
{% gist https://gist.github.com/SudhanshuGulhane/e06a224179312899c4c3fce158696f55.js %}
## Java Solution
{% gist https://gist.github.com/SudhanshuGulhane/909cacb6f78e91f7c5e26f164bfe028b.js %}
## Complexity Analysis

**The time complexity is O(n*m)**

The space complexity is O(1)

## Thank You for reading and Follow this publication for more LeetCode problems!😃
[**LeetCode Simplified**](https://medium.com/leetcode-simplified)