Shortest Word Distance I, II & III

Word Distance I – Only called once

Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

For example,
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Given word1 = “coding”, word2 = “practice”, return 3.
Given word1 = "makes", word2 = "coding", return 1.

Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

Solution: One pass. O(n), Every time find an occurrence of word1 or word2, compare the distance of p1 and p2.

public int shortestDistance(String[] words, String word1, String word2) {
        int p1 = -1, p2 = -1, min = Integer.MAX_VALUE;
    
        for (int i = 0; i < words.length; i++) {
            if (words[i].equals(word1)) 
                p1 = i;
    
            if (words[i].equals(word2)) 
                p2 = i;
    
            if (p1 != -1 && p2 != -1)
                min = Math.min(min, Math.abs(p1 - p2));
        }
    
        return min;
    }

Shortest Word Distance II – API, will be called multiple times

This is a follow up of Shortest Word Distance. The only difference is now you are given the list of words and your method will be called repeatedly many times with different parameters. How would you optimize it?

Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and return the shortest distance between these two words in the list.

For example,
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Given word1 = “coding”, word2 = “practice”, return 3.
Given word1 = "makes", word2 = "coding", return 1.

Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

Solution: First preprocess the word to dict, which is a <word, list of index>map.

Then every time just get the word only check two list of indexes.

public class WordDistance {
    Map<String, List<Integer>> dict;
    public WordDistance(String[] words) {
        dict = new HashMap<>();
        for(int i=0;i<words.length;i++){
            if(dict.containsKey(words[i])){
                dict.get(words[i]).add(i);
            }else{
                List<Integer> indexes = new ArrayList<>();
                indexes.add(i);
                dict.put(words[i], indexes);
            }
        }
    }

    public int shortest(String word1, String word2) {
        if(dict==null||!dict.containsKey(word1)||!dict.containsKey(word2)){
            return 0;
        }
        int res = Integer.MAX_VALUE;
        List<Integer> indexes1 = dict.get(word1);
        List<Integer> indexes2 = dict.get(word2);
        int index1 = 0;
        int index2 = 0;
        while(index1<indexes1.size()&&index2<indexes2.size()){
            res = Math.min(res, Math.abs(indexes1.get(index1)-indexes2.get(index2)));
            if(indexes1.get(index1)<indexes2.get(index2)){
                index1++;
            }else{
                index2++;
            }
        }
        return res;
        
    }
}

Shortest Word Distance III – word1 could be the same as word2

This is a follow up of Shortest Word Distance. The only difference is now word1 could be the same as word2.

Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

word1 and word2 may be the same and they represent two individual words in the list.

For example,
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Given word1 = “makes”, word2 = “coding”, return 1.
Given word1 = "makes", word2 = "makes", return 3.

Note:
You may assume word1 and word2 are both in the list.

Solution: if word1==word2==words[], then p1=p2=i, and every time we update p1, we check the distance between p1 and p2.

public int shortestWordDistance(String[] words, String word1, String word2) {
    int p1 = -1, p2 = -1, min = Integer.MAX_VALUE;

    for (int i = 0; i < words.length; i++) {
        if (words[i].equals(word1)) {
            p1 = i;
            if (word1.equals(word2) && p1 != -1 && p2 != -1) {
                min = Math.min(min, Math.abs(p1 - p2));
            }
        }

        if (words[i].equals(word2)) {
            p2 = i;
        }

        if (!word1.equals(word2) && p1 != -1 && p2 != -1) {
            min = Math.min(min, Math.abs(p1 - p2));
        }
    }

    return min;
}
FacebookTwitterGoogle+Share

Longest Palindromic Substring

Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Example

Given the string = "abcdzdcab", return "cdzdc".

Challenge

O(n2) time is acceptable. Can you do it in O(n) time.

Solution1. DP O(n^2)

定义函数
P[i,j] = 字符串区间[i,j]是否为palindrome.

首先找个例子,比如S=”abccb”,
S=    a  b  c  c  b
Index = 0  1  2  3  4

P[0,0] =1  //each char is a palindrome
P[0,1] =S[0] == S[1]    , P[1,1] =1
P[0,2] = S[0] == S[2] && P[1,1], P[1,2] = S[1] == S[2] , P[2,2] = 1
P[0,3] = S[0] == S[3] && P[1,2], P[1,3] = S[1] == S[3] && P[2,2] , P[2,3] =S[2] ==S[3],  P[3,3]=1
………………….
由此就可以推导出规律

P[i,j] = 1  if i ==j
=  S[i] ==S[j]   if j = i+1
=  S[i] == S[j] && P[i+1][j-1]  if j>i+1

实现如下:

public String longestPalindrome(String s) {
    if (s == null) {
        return "";
    }
    String res = "";
    int n = s.length();
    boolean[][] dp = new boolean[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            if (i - j <= 2) {
                dp[j][i] = s.charAt(i) == s.charAt(j);
            } else {
                dp[j][i] = s.charAt(i) == s.charAt(j) && dp[j + 1][i - 1];
            }
            if (dp[j][i]) {
                if (i - j + 1 > res.length()) {
                    res = s.substring(j, i + 1);
                }
            }
        }
    }
    return res;
}

Solution2: Check both aba and abba 2 cases. O(n^2)

public String longestPalindrome(String s) {
    if (s == null || s.length() == 0) {
        return "";
    }
    String result = "";

    //1. if it is like 'aba'
    for (int i = 0; i < s.length(); i++) {
        int count = 0;
        while (i - count >= 0 && i + count < s.length() && s.charAt(i - count) == s.charAt(i + count)) {
            count++;
        }
        String palindrome = s.substring(i - count + 1, i + count);
        if (palindrome.length() > result.length()) {
            result = palindrome;
        }
    }

    //2. if it is like 'abba', the pivot would be the interval between i and i+1
    for (int i = 0; i < s.length() - 1; i++) {
        int count = 1;
        while (i - count + 1 >= 0 && i + count < s.length() && s.charAt(i - count + 1) == s.charAt(i + count)) {
            count++;
        }
        if (count > 1) {
            String palindrome = s.substring(i - count + 2, i + count);
            if (palindrome.length() > result.length()) {
                result = palindrome;
            }
        }
    }

    return result;
}

 

Best Time to Buy and Sell Stock III

Best Time to Buy and Sell Stock III

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Example

Given an example [4,4,6,1,1,4,2,5], return 6.

Note

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Solution: O(n) Time 先参考 Best Time to Buy and Sell Stock I 的做法

这次的不同点在与要做两次交易,所以我们要找一个分界点,分别算左右两边的一次交易利润和的最大值。所以我们可以做Best Time to Buy and Sell Stock I两次

第一次是从左到右扫[0-i]区间,也就是先确定buyDay,然后根据每个prices[i]来确定sellDay。

第二次是从右到左扫[i-end]区间,也就是先确定sellDay,然后根据每个prices[i]来确定buyDay。

所以这两个循环时间都是O(n)

最后我们要用一个循环来设分界点,然后取

max(maxProfitEndedAt[i]+maxProfitStartedFrom[i+1])

注意这个max不是最终答案,假设只有两天[1,2] 这种情况算下来是0,因为分界点两边都是1天不足以完成交易,而且有可能的情况是第一天买入,最后一天买进,这种情况按两次交易算也无法取到最大值,所以最后结果还要考虑到只做一次交易的情况,因为没有规定必须做两次交易

Math.max(maxWithTwoTransaction, maxProfitEndedAt[length - 1]);

这一部分的时间复杂度也是O(n)

所以整体的时间复杂度就是O(n)

public int maxProfit(int[] prices) {
    if (prices == null || prices.length <= 1) {
        return 0;
    }
    int length = prices.length;
    int[] maxProfitEndedAt = new int[length];
    int[] maxProfitStartedFrom = new int[length];

    //get the max profit from 0 to i with one transaction
    maxProfitEndedAt[0] = 0;
    int buyDay = 0;
    for (int i = 1; i < length; i++) {
        maxProfitEndedAt[i] = Math.max(maxProfitEndedAt[i - 1], prices[i] - prices[buyDay]);
        if (prices[i] < prices[buyDay]) {
            buyDay = i;
        }
    }
    //get the max profit form i to length-1 with one transaction
    maxProfitStartedFrom[length - 1] = 0;
    int sellDay = length - 1;
    for (int i = length - 2; i >= 0; i--) {
        maxProfitStartedFrom[i] = Math.max(maxProfitStartedFrom[i + 1], prices[sellDay] - prices[i]);
        if (prices[i] > prices[sellDay]) {
            sellDay = i;
        }
    }
    //to have two transactions
    //pick a pivot day i, to get the max(maxProfitEndedAt[i]+maxProfitStartedFrom[i+1])
    int maxWithTwoTransaction = 0;
    for (int i = 0; i < length - 2; i++) {
        maxWithTwoTransaction = Math.max(maxWithTwoTransaction,
                                         maxProfitEndedAt[i] + maxProfitStartedFrom[i + 1]);
    }
    return Math.max(maxWithTwoTransaction, maxProfitEndedAt[length - 1]);
}

 

Maximum Product Subarray

Maximum Product Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example

For example, given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest product = 6.

Solution: One Pass O(n) time.

So for each index i, max(i) = the maximum product ending at i, so we have

max(i) = max(max(i-1)*nums[i], nums[i]) //nums[i]>=0

since you can either append from the previous one, or just start a new contiguous subarray.

Be careful on negative nums, if nums[i] < 0, the equation now becomes:

max(i) = max(min(i-1)*nums[i], nums[i]) //nums[i]<0

public int maxProduct(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int maxProduct = Integer.MIN_VALUE;
    int preMax = 1;
    int preMin = 1;
    for (int i = 0; i < nums.length; i++) {
        int max, min;
        if (nums[i] >= 0) {
            max = Math.max(preMax * nums[i], nums[i]);
            min = Math.min(preMin * nums[i], nums[i]);
        } else {
            max = Math.max(preMin * nums[i], nums[i]);
            min = Math.min(preMax * nums[i], nums[i]);
        }
        maxProduct = Math.max(maxProduct, max);
        preMax = max;
        preMin = min;
    }
    return maxProduct;
}

Maximum Subarray I & II & III

Maximum Subarray I

Given an array of integers, find a contiguous subarray which has the largest sum.

Example

For example, given the array [−2,2,−3,4,−1,2,1,−5,3], the contiguous subarray [4,−1,2,1] has the largest sum = 6.

Note

The subarray should contain at least one number

Challenge

Can you do it in time complexity O(n)?

Solution: O(n) time O(1) space. one pass. Prefix Sum

 

public int maxSubArray(ArrayList<Integer> nums) {
    if (nums == null || nums.size() == 0) {
        return 0;
    }
    int maxSum = Integer.MIN_VALUE;
    int sum = 0;
    int minSum = 0;
    for (Integer num : nums) {
        sum += num;
        maxSum = Math.max(maxSum, sum - minSum);
        minSum = Math.min(minSum, sum);
    }
    return maxSum;
}

Minimum Subarray

Minimum Subarray

Given an array of integers, find the subarray with smallest sum.

Return the sum of the subarray.

Example

For [1, -1, -2, 1], return -3

Note

The subarray should contain at least one integer.

Solution: O(n) time O(1) space. one pass. Prefix Sum

 

public int minSubArray(ArrayList<Integer> nums) {
    if (nums == null || nums.size() == 0) {
        return 0;
    }
    int minSum = Integer.MAX_VALUE;
    int sum = 0;
    int maxSum = 0;
    for (Integer num : nums) {
        sum += num;
        minSum = Math.min(minSum, sum - maxSum);
        maxSum = Math.max(maxSum, sum);
    }
    return minSum;
}

Largest Rectangle in Histogram

Largest Rectangle in Histogram

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

histogram

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

histogram

The largest rectangle is shown in the shaded area, which has area = 10 unit.

Example

Given height = [2,1,5,6,2,3],
return 10.

Solution: max(the area of rectangle which height[i] is the shortest bar)

leftBound[i]: index of the first element less than height[i] starting from the left +1

rightBound[i]: index of the first element less than height[i] starting from the right -1

result = max(height[i]*(rightBound[i]-leftBound[i]))

注意:凡是求左边第一个比它小得数这类问题 用stack 存数组的index

策略是:

如果新来的数大于A[stack.peek()], 直接push i to stack, otherwise stack.pop()直到找到第一个比他小得数停下,push i to stack.

这样对一个array来说 只要走一遍就知道每一个数的左边第一个比它小的数是哪个。

O(n) time.

Solution 1. Straightforward Version

public int largestRectangleArea(int[] height) {
    if (height == null || height.length == 0) {
        return 0;
    }
    int[] leftBound = new int[height.length];
    int[] rightBound = new int[height.length];
    Stack<Integer> minStack = new Stack<>();
    for (int i = 0; i < height.length; i++) {
        while (!minStack.isEmpty() && height[i] <= height[minStack.peek()]) {
            minStack.pop();
        }
        if (minStack.isEmpty()) {
            leftBound[i] = 0;
        } else {
            leftBound[i] = minStack.peek() + 1;
        }
        minStack.push(i);
    }
    minStack = new Stack<>();
    for (int i = height.length - 1; i >= 0; i--) {
        while (!minStack.isEmpty() && height[i] <= height[minStack.peek()]) {
            minStack.pop();
        }
        if (minStack.isEmpty()) {
            rightBound[i] = height.length - 1;
        } else {
            rightBound[i] = minStack.peek() - 1;
        }
        minStack.push(i);
    }
    int maxArea = 0;
    for (int i = 0; i < height.length; i++) {
        int area = height[i] * (rightBound[i] - leftBound[i] + 1);
        maxArea = Math.max(maxArea, area);
    }
    return maxArea;
}

Solution 2. Fancy Version, One pass

public int largestRectangleArea(int[] height) {
    if (height == null || height.length == 0) {
        return 0;
    }
    Stack<Integer> minStack = new Stack<>();
    int maxArea = 0;
    for (int i = 0; i <= height.length; i++) {
        int curr = (i == height.length) ? -1 : height[i];
        while (!minStack.isEmpty() && curr <= height[minStack.peek()]) {
            int tmp = minStack.pop();
            int left = minStack.isEmpty() ? 0 : minStack.peek() + 1;
            int area = (i - left) * height[tmp];
            maxArea = Math.max(area, maxArea);
        }
        minStack.push(i);
    }
    return maxArea;
}

N-Queens I &&II

N-Queens I

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.

Example

There exist two distinct solutions to the 4-queens puzzle:

[

[“.Q..”, // Solution 1

“…Q”,

“Q…”,

“..Q.”],

[“..Q.”, // Solution 2

“Q…”,

“…Q”,

“.Q..”]

]

Solution1: Recursion DFS, Permutation模板,判断条件换一下

ArrayList<ArrayList<String>> solveNQueens(int n) {
    ArrayList<ArrayList<String>> result = new ArrayList<>();
    if (n <= 0) {
        return result;
    }
    int[][] chessBoard = new int[n][n];
    solveNQueensHelper(chessBoard, 0, result);
    return result;
}

//DFS
public void solveNQueensHelper(int[][] chessBoard, int row, ArrayList<ArrayList<String>> result) {
    if (row == chessBoard.length) {
        result.add(toStringList(chessBoard));
        return;
    }
    for (int col = 0; col < chessBoard[row].length; col++) {
        if (isValid(chessBoard, row, col)) {
            chessBoard[row][col] = 1;
            solveNQueensHelper(chessBoard, row + 1, result);
            chessBoard[row][col] = 0;
        }
    }
}

public boolean isValid(int[][] chessBoard, int row, int col) {
    for (int i = 1; i <= row; i++) {
        if ((col - i >= 0 && chessBoard[row - i][col - i] == 1) ||
                (col + i < chessBoard.length && chessBoard[row - i][col + i] == 1) ||
                chessBoard[row - i][col] == 1) {
            return false;
        }
    }
    return true;
}

public ArrayList<String> toStringList(int[][] chessBoard) {
    ArrayList<String> result = new ArrayList<>();
    for (int i = 0; i < chessBoard.length; i++) {
        StringBuilder row = new StringBuilder();
        for (int j = 0; j < chessBoard[i].length; j++) {
            if (chessBoard[i][j] == 0) {
                row.append('.');
            } else {
                row.append('Q');
            }
        }
        result.add(row.toString());
    }
    return result;
}

Solution 2. Non-Recursive

 

N-Queens II

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

Example

For n=4, there are 2 distinct solutions.

Solution 1. Recursive. DFS

这里要注意的是 因为java的int和Integer类型都是传值不传reference,所以不能直接把int传进递归方法里,还是需要用一个链表, 或者用一个static variable

Solution 1. Recursive

public int totalNQueens(int n) {
    ArrayList<Integer> result = new ArrayList<>();
    if (n <= 0) {
        return 0;
    }
    int[][] chessBoard = new int[n][n];
    solveNQueensHelper(chessBoard, 0, result);
    return result.size();
}

public void solveNQueensHelper(int[][] chessBoard, int row, ArrayList<Integer> result) {
    if (row == chessBoard.length) {
        result.add(result.size() + 1);
        return;
    }
    for (int col = 0; col < chessBoard[row].length; col++) {
        if (isValid(chessBoard, row, col)) {
            chessBoard[row][col] = 1;
            solveNQueensHelper(chessBoard, row + 1, result);
            chessBoard[row][col] = 0;
        }
    }
}

public boolean isValid(int[][] chessBoard, int row, int col) {
    for (int i = 1; i <= row; i++) {
        if ((col - i >= 0 && chessBoard[row - i][col - i] == 1) ||
                (col + i < chessBoard.length && chessBoard[row - i][col + i] == 1) ||
                chessBoard[row - i][col] == 1) {
            return false;
        }
    }
    return true;
}

Solution 2. Non-Recursive

Leetcode: Set Matrix Zeroes

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

click to show follow up.

Follow up:Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?1. O(m+n) space solutionAnalysis:
To achieve O(m+n) space, you need two array to store information while traversal the matrix for the first time checking if it is zero or not. You can also combine two arrays into one, but still cost O(m+n) space. So I just use two to store row and column information.
public class Solution {
    public void setZeroes(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return;
        }
        boolean[] zeroRows = new boolean[matrix.length];
        boolean[] zeroCols = new boolean[matrix[0].length];
        //traversal the entire matrix to check if it is zero or not
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] == 0) {
                    zeroRows[i] = true;
                    zeroCols[j] = true;
                }
            }
        }
        //now set matrix zero based on the two boolean arrays
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (zeroRows[i] || zeroCols[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}

2. *Optimal* O(1) space solution

Analysis:
To save space, we can just make use of the space inside the matrix. Which means, we use the first row and first column to store the information.
In the first traversal, we set the corresponding cell on the first row or first column to 0 if there is any cell which is zero in this row or column.
In the second traversal, we set the matrix to zeros based on the first row and first column.

 public void setZeroes(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return;
        }
        boolean firstRowHasZero = false;
        boolean firstColHasZero = false;
        //traversal the entire matrix to check if it is zero or not
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] == 0) {
                    if (i == 0) {
                        firstRowHasZero = true;
                    }
                    if (j == 0) {
                        firstColHasZero = true;
                    }
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }
        //now set matrix zero based on first row and first column
        for (int i = 1; i < matrix.length; i++) {
            for (int j = 1; j < matrix[i].length; j++) {
                if (matrix[0][j] == 0 || matrix[i][0] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
//deal with the first column
        if (firstColHasZero) {
            for (int i = 1; i < matrix.length; i++) {
                matrix[i][0] = 0;
            }
        }
//deal with the first row
        if (firstRowHasZero) {
            for (int i = 1; i < matrix[0].length; i++) {
                matrix[0][i] = 0;
            }
        }
    }

Note: The tricky part of this algorithm is, if without those two boolean variables to keep track of if there is any zero in the first row or first column , when matrix[0][0]==0, we have no idea if the first row contains zero, or it is the first column contains zero, or both. also, we should deal with the rest part first based on the first row and first column and then deal with the first row and first column based on the two boolean values.

Leetcode: Minimum Path Sum

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.

1. Recursive Solution

 public int minPathSum(int[][] grid) {
        if (grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int[][] resultMap = new int[grid.length][grid[0].length];
        return minPathSum(grid, resultMap, grid.length-1, grid[0].length-1);
    }

    public int minPathSum(int[][] grid, int[][] resultMap, int row, int col) {
        if (row < 0 || col < 0) {
            return Integer.MAX_VALUE;
        }
        if (row == 0 && col == 0) {
            return grid[0][0];
        }
        if (resultMap[row][col] == 0) {
            resultMap[row][col] = grid[row][col] + Math.min(minPathSum(grid, resultMap, row - 1, col), minPathSum(grid, resultMap, row, col - 1));
        }
        return resultMap[row][col];
    }

Note:

This is a very typical dp problem. where dp[i][j] = grid[i][j] + min( dp[i-1][j], dp[i][j-1] ); To prevent same cell being visited and calculated multiple times, we have a resultMap 2d array to store the result. We also need to check the edge carefully to ensure the index is not out of bounds of the given array.

2. Iterative Solution (O(m*n) space)

public class Solution {
     public int minPathSum(int[][] grid) {
        if(grid.length==0||grid[0].length==0){
            return 0;
        }
        //2D map -- O(m*n) space
        int[][] resultMap = new int[grid.length][grid[0].length];
        resultMap[0][0] = grid[0][0];
        //Calculate the first row
        for(int i = 1;i<grid[0].length;i++){
            resultMap[0][i] = grid[0][i] + resultMap[0][i-1];
        }
        //Calculate the first col
        for(int i = 1;i<grid.length;i++){
            resultMap[i][0] = grid[i][0] + resultMap[i-1][0];
        }
        //Calculate the rest
        for(int i=1;i<grid.length;i++){
            for(int j=1;j<grid[0].length;j++){
                resultMap[i][j] = grid[i][j]+Math.min(resultMap[i-1][j],resultMap[i][j-1]);
            }
        }
        return resultMap[grid.length-1][grid[0].length-1];
    }
}

Note: First calculate first row and first col which is there own grid value, then calculate other cells based on it.

3. *Optimal* Iterative Solution (O(n) space)

public class Solution {
    public int minPathSum(int[][] grid) {
        if (grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int rows = grid.length;
        int cols = grid[0].length;

        //1D map -- O(n) space, n is # of cols
        int[] resultMap = new int[cols];
        resultMap[0] = grid[0][0];

        //Calculate the first row
        for (int i = 1; i < grid[0].length; i++) {
            resultMap[i] = grid[0][i] + resultMap[i - 1];
        }

        for (int i = 1; i < rows; i++) {
            resultMap[0] = resultMap[0] + grid[i][0];
            for (int j = 1; j < cols; j++) {
                resultMap[j] = grid[i][j] + Math.min(resultMap[j], resultMap[j - 1]);
            }
        }
        return resultMap[cols - 1];
    }
}

Note: You don’t necessarily need a 2d map to store which cost O(n) space where n is the # of columns. You can just use one row to stored the result of previous row, and replace the value with the current row from left to right one by one. One thing worth mentioning is this code is more space efficient though, it has lower readability.

More information and further thoughts for minimum path sum questions can be found here.