# Clean Code - 8 Solutions (6 C++ & 2 java)

• ### Java

3D DP - space O(N.m.n)

``````public class Solution {
public int findPaths(int m, int n, int N, int i0, int j0) {
long limit = 1000000007;
long[][][] dp = new long[N + 1][m][n];
for (int k = 1; k <= N; k++) {
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
dp[k][i][j] += i == 0     ? 1 : dp[k - 1][i - 1][j];
dp[k][i][j] += i == m - 1 ? 1 : dp[k - 1][i + 1][j];
dp[k][i][j] += j == 0     ? 1 : dp[k - 1][i][j - 1];
dp[k][i][j] += j == n - 1 ? 1 : dp[k - 1][i][j + 1];
dp[k][i][j] %= limit;
}
}
}
return (int)dp[N][i0][j0];
}
}
``````

Rolling Matrix - space O(m.n)

``````public class Solution {
public int findPaths(int m, int n, int N, int i0, int j0) {
long limit = 1000000007;
long[][][] dp = new long[2][m][n];
for (int k = 1; k <= N; k++) {
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
dp[k % 2][i][j] =((i == 0     ? 1 : dp[(k - 1) % 2][i - 1][j])
+ (i == m - 1 ? 1 : dp[(k - 1) % 2][i + 1][j])
+ (j == 0     ? 1 : dp[(k - 1) % 2][i][j - 1])
+ (j == n - 1 ? 1 : dp[(k - 1) % 2][i][j + 1])) % limit;
}
}
}
return (int)dp[N % 2][i0][j0];
}
}
``````

### C++

1. 3D DP

``````class Solution {
public:
int findPaths(int m, int n, int N, int i, int j) {
size_t limit = 1000000007;
vector<vector<vector<size_t>>> dp(N + 1, vector<vector<size_t>>(m, vector<size_t>(n, 0)));
for (int k = 1; k <= N; k++) {
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
dp[k][i][j] += i == 0     ? 1 : dp[k - 1][i - 1][j];
dp[k][i][j] += i == m - 1 ? 1 : dp[k - 1][i + 1][j];
dp[k][i][j] += j == 0     ? 1 : dp[k - 1][i][j - 1];
dp[k][i][j] += j == n - 1 ? 1 : dp[k - 1][i][j + 1];
dp[k][i][j] %= limit;
}
}
}
return dp[N][i][j];
}
};
``````

2. Functor

``````class Solution {
public:
int findPaths(int m, int n, int N, int i0, int j0) {
vector<vector<vector<uint>>> dp(N + 1, vector<vector<uint>>(m, vector<uint>(n, 0)));
auto paths = [&](int k, int i, int j) { return (i < 0 || i >= m || j < 0 || j >= n) ? 1 : dp[k][i][j]; };
for (int k = 1; k <= N; k++) {
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
dp[k][i][j] = paths(k - 1, i - 1, j) + paths(k - 1, i + 1, j) + paths(k - 1, i, j - 1) + paths(k - 1, i, j + 1);
dp[k][i][j] %= 1000000007;
}
}
}
return dp[N][i0][j0];
}
};
``````

3. Functor & Rolling Matrix

``````class Solution {
public:
int findPaths(int m, int n, int N, int i0, int j0) {
vector<vector<vector<uint>>> dp(N + 1, vector<vector<uint>>(m, vector<uint>(n, 0)));
auto paths = [&](int k, int i, int j) { return (i < 0 || i >= m || j < 0 || j >= n) ? 1 : dp[k % 2][i][j]; };
for (int k = 1; k <= N; k++) {
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
dp[k % 2][i][j] = paths(k - 1, i - 1, j) + paths(k - 1, i + 1, j) + paths(k - 1, i, j - 1) + paths(k - 1, i, j + 1);
dp[k % 2][i][j] %= 1000000007;
}
}
}
return dp[N % 2][i0][j0];
}
};
``````

4. Use Functor for Rolling

``````class Solution {
public:
int findPaths(int m, int n, int N, int i0, int j0) {
vector<vector<vector<uint>>> dp(2, vector<vector<uint>>(m, vector<uint>(n, 0)));
auto paths = [&](int k, int i, int j) ->uint& { uint one = 1; return (i < 0 || i >= m || j < 0 || j >= n) ? one : dp[k % 2][i][j]; };
for (int k = 1; k <= N; k++) {
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
paths(k, i, j) = paths(k - 1, i - 1, j) + paths(k - 1, i + 1, j) + paths(k - 1, i, j - 1) + paths(k - 1, i, j + 1);
paths(k, i, j) %= 1000000007;
}
}
}
return paths(N, i0, j0);
}
};
``````

5. Functor Rolling Array & Delta Sequence

``````class Solution {
public:
int findPaths(int m, int n, int N, int i0, int j0) {
vector<vector<vector<uint>>> dp(2, vector<vector<uint>>(m, vector<uint>(n, 0)));
auto paths = [&](int k, int i, int j) ->uint& { uint one = 1; return (i < 0 || i >= m || j < 0 || j >= n) ? one : dp[k % 2][i][j]; };
int delta[4][2] = {-1, 0, 1, 0, 0, -1, 0, 1};
for (int k = 1; k <= N; k++) {
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
paths(k, i, j) = 0; // reset before reuse
for (int d = 0; d < 4; d++) {
paths(k, i, j) += paths(k - 1, i + delta[d][0], j + delta[d][1]);
}
paths(k, i, j) %= 1000000007;
}
}
}
return paths(N, i0, j0);
}
};
``````

6. DFS - TLE :(

``````class Solution {
public:
int findPaths(int m, int n, int N, int i, int j) {
int limit = 1000000007;
int paths = 0;
dfs(m, n, N, i, j, paths, limit);
return paths;
}

private:
void dfs(int m, int n, int N, int i, int j, int& paths, int limit) {
if (N > 0 && paths < limit && i >= 0 && i < m && j >= 0 && j < n) {
if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
paths += i == 0;
paths += i == m - 1;
paths += j == 0;
paths += j == n - 1;
if (N == 0 || paths >= limit)
return;
}

dfs(m, n, N - 1, i + 1, j, paths, limit);
dfs(m, n, N - 1, i - 1, j, paths, limit);
dfs(m, n, N - 1, i, j + 1, paths, limit);
dfs(m, n, N - 1, i, j - 1, paths, limit);
}
}
};
``````

• @alexander great solutions!
I just have a question about `5. Functor Rolling Array & Delta Sequence` solution.
Why do you need to set `paths(k, i, j) = 0;` and do not this in solution 4?

• @hash3r Because the 3D cache is made of only 2 rolling matrix, each cell is re-used a lot of times and they are not `0` anymore once `k > 2`. Thank you for your patience to read these code :)

``````   vector<vector<vector<uint>>> dp(2, vector<vector<uint>>(m, vector<uint>(n, 0)));
^
``````

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