What's my solution's Time Complexity?


  • 0
    F

    This is a very very slower solution which even Time Exceed when I submit. But it tested it on my IDE and answers are correct.

    Is my solution standard backtracking? and is it O(2^(m+n))? can I use backtracking method like this but optimize it until it can pass the test?

       public class Solution {
            int min = Integer.MAX_VALUE;
            public int minPathSum(int[][] grid) {
                helper(grid,0,0,0); 
                return min;
            }
            public void helper(int[][] grid, int m, int n, int sum){
                sum += grid[m][n];
                if(m == grid.length-1 && n == grid[0].length-1){
                    if(sum < min)
                        min = sum;
                    return;
                }
                
                if(m < grid.length-1 && n < grid[0].length-1){
                    helper(grid,m+1,n,sum);
                    helper(grid,m,n+1,sum);
                }
                if(m < grid.length-1 && n == grid[0].length-1){
                    helper(grid,m+1,n,sum);
                }
                if(m == grid.length-1 && n < grid[0].length-1){
                    helper(grid,m,n+1,sum);
                }
            }
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.