0 ms, DP solution with lesser space complexity = O(min(m,n))


  • 0
    I

    Many DP solutions here use a 2D array, but we only need to record the last row in the DP array - so an array of size= number of columns should be sufficient. Additionally, the problem remains the same even if we swap the rows with columns, so if the number of columns is greater than the number of rows, we can swap the number of rows and number of columns.
    Space Complexity= O(min(m,n))
    Time Complexity remains O(m*n)
    Here's my code for doing this:

    class Solution {
        public int uniquePaths(int rows, int cols) {
            if(rows == 0 || cols == 0) {
                return 0;
            }
            
            // Reduce space complexity by swapping rows and cols if cols>rows
            if(cols > rows) {
                int temp = rows;
                rows = cols;
                cols = temp;
            }
            
            int[] numWays = new int[cols];
            //Initialize 1st row with 1s
            numWays[0] = 1;
            for(int j = 1; j < cols; j++) {
                numWays[j] = numWays[j - 1];
            }
            
            for(int i = 1; i < rows; i++) {
                // numWays[0] should remain the same as previous row (1)
                for(int j = 1; j < cols; j++) {
                    numWays[j] += numWays[j - 1];
                }
            }
            
            return numWays[cols - 1];   
        }
    }
    

Log in to reply
 

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