Time O(mn), space O(n) javascript solution


  • 0
    H

    The DP formula is map[m, n] = map[m - 1, n] + map[m, n - 1]

    Based on this, we will have a top-down solution via the formula, however it's too time-consuming

    So, we later come up with a bottom-top idea for this question.

    besides, we can only use one single array and override it repeatedly, that's how we can reduce space complexity from O(mn) to O(n)

    var uniquePaths = function(m, n) {
      if (m === 1 || n === 1) return 1;
    
      var arr = [];
      var i, j;
    
      for (i = 1; i < m; i++) {
        for (j = 1; j < n; j++) {
          arr[j] = (arr[j] || 1) + (arr[j - 1] || 1);
        }
      }
    
      return arr[n - 1];
    };

Log in to reply
 

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