# Java DP with O(n) space

• 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];
}
}``````

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

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

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

• 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];
}
}``````

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