Anyway to increase the speed?


  • 0
    Z

    My C++ code is based on the idea suggested by yavinci https://leetcode.com/discuss/81389/15ms-concise-java-solution

    However, it took 88ms to finish compared to yavinci's 15ms JAVA code. Can anyone give some suggestion on how to improve the speed?

    Thanks.

    private:
        vector<pair<int, int>> dirs{ make_pair(0,1), make_pair(1,0), make_pair(0,-1), make_pair(-1,0) };
        vector<vector<int>> cache;
    
    public:
    int dfs(vector<vector<int>>& matrix, int i, int j) {
        // Case 1: i or j is out of range
        if ( (i >= matrix.size()) || (j >= matrix[i].size()) ) {
            return 0;
        }
        
        // Case 2: cell already visited
        if (cache[i][j] != 0) {
            return cache[i][j];
        }
    
        // initiate onpath max
        int onpathMax = 1;
    
        // loop 4 directions
        for (auto dir : dirs) {
            // Step 1: change to next neighbor
            int r = i + dir.first;
            int c = j + dir.second;
            // Step 2: check if next neighbor is out of range, or new element is no larger than current element
            if ( (r < 0) || (r >= matrix.size()) || (c < 0) || (c > matrix[0].size()) || (matrix[r][c] <= matrix[i][j]) ) {
                continue;
            }
            // Step 3: update onpath length by recursively call dfs() function
            int onpathLen = 1 + dfs(matrix, r, c);
            // Step 4: update onpathMax
            onpathMax = max(onpathMax, onpathLen);
        }// end for
    
        // save onpathMax to cache[i][j] and return
        cache[i][j] = onpathMax;
        return onpathMax;
    }
    
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        // Case 1: empty matrix
        if (matrix.empty()) {
            return 0;
        }
        // Case 2: non-empty matrix
        else {
            // Step 1: resize cache matrix
            cache.resize(matrix.size(), vector<int>(matrix[0].size()));
    
            // Step 2: initialize globalMax to 1
            int globalMax = 1;
    
            // Step 3: DFS on every cell
            for (int i=0; i<matrix.size(); i++) {
                for (int j=0; j<matrix[i].size(); j++) {
                    // compare all 4 directions
                    // skip cells with: 1) smaller max; 2) out of boundary
                    int localMax = dfs(matrix, i, j);
                    // update larger globalMax
                    globalMax = max(localMax, globalMax);
                }
            }
            
            return globalMax;
        }// end else
    }
    

    I tried to pass (i, j) by pair, but it's even slower (92 ms)...

    public:
    int dfs(vector<vector<int>>& matrix, pair<int, int> position) {
        // Case 1: i or j is out of range
        if ( (position.first >= matrix.size()) || (position.second >= matrix[position.first].size()) ) {
            return 0;
        }
        
        // Case 2: cell already visited
        if (cache[position.first][position.second] != 0) {
            return cache[position.first][position.second];
        }
    
        // initiate onpath max
        int onpathMax = 1;
    
        // loop 4 directions
        for (auto dir : dirs) {
            // Step 1: change to next neighbor
            int r = position.first + dir.first;
            int c = position.second + dir.second;
            // Step 2: check if next neighbor is out of range, or new element is no larger than current element
            if ( (r < 0) || (r >= matrix.size()) || (c < 0) || (c > matrix[position.first].size()) || (matrix[r][c] <= matrix[position.first][position.second]) ) {
                continue;
            }
            // Step 3: update onpath length by recursively call dfs() function
            int onpathLen = 1 + dfs(matrix, make_pair(r, c));
            // Step 4: update onpathMax
            onpathMax = max(onpathMax, onpathLen);
        }// end for
    
        // save onpathMax to cache[i][j] and return
        cache[position.first][position.second] = onpathMax;
        return onpathMax;
    }
    
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        // Case 1: empty matrix
        if (matrix.empty()) {
            return 0;
        }
        // Case 2: non-empty matrix
        else {
            // Step 1: resize cache matrix
            cache.resize(matrix.size(), vector<int>(matrix[0].size()));
    
            // Step 2: initialize globalMax to 1
            int globalMax = 1;
    
            // Step 3: DFS on every cell
            for (int i=0; i<matrix.size(); i++) {
                for (int j=0; j<matrix[i].size(); j++) {
                    // compare all 4 directions
                    // skip cells with: 1) smaller max; 2) out of boundary
                    int localMax = dfs(matrix, make_pair(i, j));
                    // update larger globalMax
                    globalMax = max(localMax, globalMax);
                }
            }
            
            return globalMax;
        }// end else
    }

Log in to reply
 

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