Open Frantch opened 4 years ago
Hello @Frantch,
As you're traversing through the whole grid it's simply O(n*m)
and space complexity is O(n*m)
. For the recursive approach, always you have to consider 2 paths to calculate and as you're not using a memoization technique, there are overlapping sub problems. So the time complexity is O(2^n)
.
Furthermore you can further improve the solution by reducing space complexity only to O(n)
like,
public int uniquePaths(int m, int n) {
int[] arr=new int[n];
for(int i=0; i<m; i++) {
for(int j=0; j<n; j++) {
if(i==0 || j==0) {
arr[j]=1;
continue;
}
arr[j]+=arr[j-1];
}
}
return arr[n-1];
}
Hello,
I'm trying to figure out the Big O complexity of both of the algorithm writtne in https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/NumberOfPathsInMxNMatrix.java
Is it correct to say for countPaths O(countPaths) = n + m + n*m
And what would it be for the recursive approach ?
thank you!