DFS algorithm too slow

Question

I am practicing my coding on leetcode, and my submission, although correct for small cases, is timing out for large ones. Could you please let me know how to improve my code?

The question is as follows (https://leetcode.com/problems/longest-increasing-path-in-a-matrix/):

Given an integer matrix, find the length of the longest increasing path. From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Here is my solution. I tried to use memoization, but it's just not fast enough: I think I'm missing something fundamental -- I do not have a CS background.

class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) 
    {
        //base case
        if (matrix.size() == 0 || matrix[0].size() == 0)
        return 0;

        //create hash matrix populated with -1
        int height = matrix.size();
        int length = matrix[0].size();
        vector<int> temp(length,-1);
        vector<vector<int>> hash(height,temp);

        int maximum;
        //run longestpathfrom on all node
        for(int i=0; i<height; i++)
        {
            for(int j = 0; j<length; j++)
            {
                longestpathfrom(matrix,i,j,hash,maximum);
            }
        }
        return maximum;
    }

    int longestpathfrom(vector<vector<int>> matrix, int i, int j, vector<vector<int>>& hash, int& maximum)
    {
        //Returns the longest path from your current position
        //Also uses memoization via hash.
        //also keeps track of the max...

        //If you already calculated this value, just return it.
        if (hash[i][j]!=-1)
        return hash[i][j];

        //directions
        vector<vector<int>> dirs {{-1,0},{1,0},{0,-1},{0,1}};

        //pathlength:
        int pathlen = 0;

        //Take the max of longestpathfrom over all valid neighbours:
        for (int I=0; I<4; I++)
        {
            //Generate indices of where you are checking path length from
            int x = i+dirs[I][0];
            int y = j+dirs[I][1];

            //Check index validity:
            if (x<0 || y<0 || x>matrix.size()-1 || y>matrix[0].size()-1)
            continue;

            if (matrix[i][j]<matrix[x][y])
            pathlen = max(pathlen, longestpathfrom(matrix, x, y, hash, maximum));
        }

        //add 1 for the square you're already on
        pathlen++;

        //update hash
        hash[i][j]=pathlen;

        //update max
        maximum = max(maximum,pathlen);

        return pathlen;
    }
};

Answer 1

Your bruteforce method seems correct, there might be better ones available (using heuristics for instance), but let's stick with what you have.

First thing, you pass the matrix by value in each longestpathfrom and not by reference, probably a mistake given you do it for the rest. Given how many times you use this function and how big the matrix can be, it can make a huge difference.

Second thing, you can reduce the search space.
For instance, you know that if start is "a" and stop is "b", the longest path possible is "b-a". If, instead of starting by [0][0] then [0][1] ..., you start by the lowest value then the second lowest ..., you know you can stop searching once the maximum value of the matrix minus the current start value is lower than the length of the current maximum path.

Just a few words on coding style if I may.
Try to keep the style of the name of variables constant. Leetcode seems to use camelCase, so it's best if you stick to it (so longestPathFrom instead), or switch everything to C style (lowest_path_from).
Try not to use capital letters at the start/for variable names (your I).
Try to keep spacing consistent either you use variable=value or variable = value, but not both. I'd say the later is much better and readable.