Finding the length of the number of paths in a matrix

Question

I found this problem from leetcode.com. We are asked to find the longest increasing path in a matrix. I finally came up with a recursion to achieve this but I found that when I increase the rows and columns to a large size then my program takes a long time to run.

I am wondering if there is any way I can optimize my code for speed, or perhaps if there is a better approach I can consider. I know that some have used dynamic programming and depth first search to achieve good speeds but to be honest I haven't really gotten there yet in my programming level.

#include <algorithm>
#include <cmath>
#include <vector>
#include <iostream>
#include <random>
using namespace std;
#define MATRIX_SIZE 1000
void printPath() {
}
int check(int i, int j, vector<vector<int> > matrix, vector<vector<int> > length) {
 if (length[i][j] == -1) {
 int currentValue = matrix[i][j];
 int len = 0;
 if ((i > 0) && (matrix[i-1][j] > currentValue)) { // check up
 len = max(len, check(i-1, j, matrix, length));
 }
 if ((i + 1 < matrix.size()) && (matrix[i+1][j] > currentValue)) { // check left
 len = max(len, check(i+1, j, matrix, length));
 }
 if ((j > 0) && (matrix[i][j-1] > currentValue)) { // check down
 len = max(len, check(i, j-1, matrix, length));
 }
 if ((j+1 < matrix[i].size()) && (matrix[i][j+1] > currentValue)) { // check right
 len = max(len, check(i, j+1, matrix, length));
 }
 length[i][j] = len + 1; // Include current cell
 }
 return length[i][j];
}
int longestPath(vector<vector<int> > matrix) {
 int n = matrix[0].size();
 int m = matrix.size();
 vector<vector<int> > length(m, vector<int>(n,-1));
 int len = 0;
 for (int i = 0; i < m; i++) {
 for (int j = 0; j < n; j++) {
 len = max(len, check(i, j, matrix, length));
 }
 }
 return len;
}
int main() {
 // Specify the number of rows and columns of the matrix
 int n = MATRIX_SIZE;
 int m = MATRIX_SIZE;
 // Declare random number generator
 mt19937 gen(10);
 uniform_int_distribution<> dis(1, 1000000);
 // Fill matrix
 vector<vector<int> > matrix;
 for(int i = 0; i < m; i++) {
 vector<int> row;
 for(int j = 0; j < n; j++) {
 row.push_back(0);
 }
 matrix.push_back(row);
 }
 // Apply random number generator to create matrix
 for(int i = 0; i < m; i++) {
 for(int j = 0; j < n; j++) {
 matrix[i][j] = dis(gen);
 }
 }
 // Print matrix to see contents
// for(int i = 0; i < m; i++) {
// for(int j = 0; j < n; j++) {
// cout << matrix[i][j] << " ";
// }
// cout << endl;
// }
// cout << endl;
 int result = longestPath(matrix);
 cout << result << endl;
}

• Cris Luengo: "a long time to compile" Do you mean it takes a long time to run? I don't think the army sizes would change compilation times?
• Cris Luengo: I think you should consider starting your search at each local minimum. There is no point in finding the longest path starting at any other point, because it won't be maximal by definition. Optimal would be to process these local minima in order of lowest value first. That way you'll do the least work. (Sorry, this is sort of a mini-review, I think it's too short to post as an answer, but I don't have anything else to add.)

Answer 1

Don't do using namespace std;.

---

void printPath() {
}

This empty function does not do anything, so better remove it to make the code cleaner.

---

// Print matrix to see contents
// for(int i = 0; i < m; i++) {
// for(int j = 0; j < n; j++) {
// cout << matrix[i][j] << " ";
// }
// cout << endl;
// }
// cout << endl;

Commented code clutters the code and can confuse the reader. "Is it still needed? Then why is it commented out? If not, why is it still there?". Apparently it is not used anymore, and it also tells the reader nothing about the code, so better delete it.

---

// Specify the number of rows and columns of the matrix
int n = MATRIX_SIZE;
int m = MATRIX_SIZE;

The comment here should not be needed, because the code explains itself. Maybe it would be even more explicit if you named the variables rows and columns. If n and m do not change, and you have MATRIX_SIZE defined anyways, you could just use MATRIX_SIZE instead of the variables.

---

// Declare random number generator
mt19937 gen(10);
uniform_int_distribution<> dis(1, 1000000);

A more explicit variable name would make this comment obsolete. Less comments means less to read and makes the code easier to understand. Comments should tell the reader why the code does something, but the code should explain what it does itself. rng would be short and is a well known acronym for random number generator.

• Snarfy: Thank you, those are good points. But I am still looking for something that will speed up the code.
• R zu: When you try to access a number in a vector of vectors, you need an extra indirection. The data is also scattered all over the memory and the cpu has to jump to all these spots in the memory. Better just use one vector to hold all the numbers if you care about speed. Or use a linear algebra library.
• R zu: Hmm.. Should reserve space before doing tons of push_back. Otherwise, the program often reallocates memory for the vectors during the loop. And allocation of memory is really really slow. Maybe if a z order curve representation of the matrix would make this faster. But I am not sure.

Answer 2

longest_path and check both take their vector parameters by value, which means the compiler will make copies of the vectors when calling the functions. This consume a lot of execution time since they are large two-dimensional matrices. Also, your caching of the calculated value for length will be lost since it is only stored in the local copy.

The vector parameters should be passed in by reference (const for matrix since it is not modified):

int check(int i, int j, const vector<vector<int> > &matrix, vector<vector<int> > &length)