Java DP with O(n) space


  • 17
    C

    We only need to store the previous row/column to perform the calculation for the next one. So an 1-d array would suffice. You could also choose to iterate through m or n depending on which direction you choose to go (by row or by column). Note that the first element of the array will always be 1.

    public class Solution {
        public int uniquePaths(int m, int n) {
            int[] arr = new int[m];
            for (int i = 0; i < m; i++) {
                arr[i] = 1;
            }
            for (int i = 1; i < n; i++) {
                for (int j = 1; j < m; j++) {
                    arr[j] = arr[j] + arr[j-1];
                }
            }
            return arr[m-1];
        }
    }

  • 0
    K

    Isn't this still O(n*m) or did I make a mistake?


  • 0
    C

    This is O(m*n) runtime, but I stated that it is O(n) space as it only uses a single int array.


  • 0
    K

    Sorry, misread as O(n) time and space ;)


  • 0
    F

    Observe that uniquePaths(m, n) == uniquePaths(n, m)

    So swap m and n if m is bigger than n

    then we do not have to do (m^2)/2 iterations, save some time, still O(mn) complexity though

    public class Solution {
        public int uniquePaths(int m, int n) {
            if (m == 1 || n == 1) {
                return 1;
            }
            if (m > n) {
                int tmp = m;
                m = n;
                n = tmp;
            }
            int[] paths = new int[n];
            for (int i = 0; i < m; i++) {
                for (int j = i; j < n; j++) {
                    if (j == 0) {
                        paths[j] = 1;
                    } else if (i == j) {
                        paths[j] <<= 1;
                    } else {
                        paths[j] += paths[j-1];
                    }
                }
            }
            return paths[n-1];
        }
    }

Log in to reply
 

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