Solve one question per week - 11.16.2021

Coding keep your coding sharp
1

How it works

  1. Every Monday we will post a question.
  2. Community will solve the question and then post their solutions.
  3. You will get community feedback on your solutions
2

Today’s question https://leetcode.com/problems/unique-paths/

1 Like
3 
class Solution {
    public int uniquePaths(int m, int n) {
        if (m == 1 || n == 1) return 1; 
        
        return uniquePaths(m-1,n) + uniquePaths(m,n-1);
    }
}

Runtime Complexity: 2^(m + n)
Space : m+n

1 Like
4 
   class Solution {
        public int uniquePaths(int m, int n) {
            if (m == 1 || n == 1) return 1; 
            Map<String,Integer> memo= new HashMap<>();
            if (memo.containsKey(m +"#" + n)) {
                return memo.get(m +"#" + n);
            }
            int ways =  uniquePaths(m-1,n) + uniquePaths(m,n-1);
            memo.put(m+"#"+n, ways);
            return ways;
        }
    }
5

What is the complexity of this solution?

6

Can you solve it using DP?

7

Another alternative (in C#)

public class Solution {
    
    public int UniquePaths(int m, int n) {
        
        return (int)((factorial(m+n-2) / (factorial(m-1) * factorial(n-1))));
    }
    
    private Dictionary<int, BigInteger> memo = new Dictionary<int, BigInteger>();
    
    private BigInteger factorial(int n)
    {
        if (memo.ContainsKey(n))    return memo[n];
        memo[n] = (n == 0 || n == 1) ? 1 : n * factorial(n-1);
        return memo[n];
    }
}

Time Complexity: O(m+n)
Space Complexity: O(m+n)

2 Likes
8

DP solution -

public class Solution {

public int UniquePaths(int m, int n) {
    
    int[][] dp = new int[m][];
    for (int i=0; i<m; i++) dp[i] = new int[n];
        
    
    for (int i=m-1; i>=0; i--)  dp[i][n-1] = 1;
    for (int j=n-1; j>=0; j--)  dp[m-1][j] = 1;
    
    for (int i=m-2; i>=0; i--)
    for (int j=n-2; j>=0; j--)
        dp[i][j] = dp[i+1][j] + dp[i][j+1];
    
    return dp[0][0];
}

}

Time Complexity = Space Complexity = O(mn)

Critique most welcome !

1 Like