# Anyway to increase the speed?

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

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