Easy understand Java O(n) space DP rolling array technique


  • 2

    1st solution is O(m*n) space and can be optimized to the 2nd O(n) space using rolling array technique.
    Is there a way to further optimize it to O(1) space dp ?

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

  • 1
    Y

    I don't know if it could be further optimized to O(1) space, but it can be optimized to O(1n) space (i.e. not need O(2n) space)
    The idea is like this:
    Since we only need to know N[m-1][n-1] for a m*n grid, it is a waste of space to keep the whole 2-dimensional array. And we also know that N[i][j] = N[i-1][j] + N[i][j-1], so if we use only a one dimensional array and let N[i] = N[i] + N[i-1]. i.e. the N[i] at the left side of the equation and N[i-1] actually stores the number of path at the next row in a 2-dimensional array, and N[i] at the right side of the equation stores the number of paths at the current row in a 2-dimensional array. So in general, every element on the left side of N[i] in the 1 dimensional array is actually the value at the next row if in a 2-dimensional array.
    By filling the array from left to right, we will never rewrite a value before we making use of it.

    public class Solution {
    public int uniquePaths(int m, int n) {
        /*
        Dynamic Programming
        Bottom-up approach
        If we use Num[n] to denote the number of paths and we fill this form from left to right, we will never rewrite a value before we make use of it.
        O(mn) time and O(n) space
        */
        if (m == 0 || n == 0){
            return 0;
        }
        
        int[] Num = new int[n];
        for (int i = 0; i < m; i ++){
            for (int j = 0; j < n; j++){
                if (i == 0 || j == 0){
                    Num[j] = 1;
                }
                
                else {
                    Num[j] += Num[j-1];
                }
            }
        }
        
        return Num[n-1];
    }
    

    }


  • 0
    R

    @YaokaiYang your solution is great it would be helpful if you can add some explanation.


  • 0
    Y

    @mayuririmjha Thanks for your reminding. I have added the explanation.


Log in to reply
 

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