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


  • 6

    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);
            }
        }
    };
    

  • 0
    H

    @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?


  • 0

    @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)));
                                       ^
    

Log in to reply
 

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