Very concise solution also with nice performance in C, well-explained


  • 0

    The first sight of this problem, it's not a DFS problem but rather it's more like a DP or Memoization problem though there are some traversing to search. Okay, just save the crap, hit the road. Memoization is going to be an easy way to go:

    • use a 2-dimension array to store the states for each cell of the matrix;
    • traverse starting from each cell to complete the states - the max length end in this cell;
    • to avoid trying each direction using barehand-writing code, I choose to use an array to do that

    Directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    which can be replaced with more direct method to improve the performance but it will be ugly comparably.

    Bang! End of Story!

    • space cost O (n*m) the matrix used to store the states;
    • time cost O(n*m) since we are only required to fill all the states of the matrix of maxes;

    Readability can not always be hand in hand with performance, try to balance them.


    const int Directions[][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    bool inRange(int r, int c, int rSize, int cSize)
    {
        return r>=0 && r<rSize && c>=0 && c<cSize;
    }
    
    int traverse(int r, int c, int rSize, int cSize, int** matrix, int** maxes)
    {
        if(!inRange(r, c, rSize, cSize)) return 0;
        if(maxes[r][c] != -1) return maxes[r][c];
        int cur = matrix[r][c];
        int max = 1; //as long as it's valid, it will be at least 1;
        int t = 0;
        for(int i = 0; i < 4; i++) //check the cells around;
        {
            int r0 = r+Directions[i][0];
            int c0 = c+Directions[i][1];
            if(inRange(r0, c0, rSize, cSize) && cur > matrix[r0][c0])
            {
                t = traverse(r0, c0, rSize, cSize, matrix, maxes)+1;
                if(t > max)
                    max = t;
            }
        }
        return maxes[r][c] = max;//update the current cell;
    }
    
    int longestIncreasingPath(int** matrix, int rSize, int cSize)
    {
        int **maxes = (int**)malloc(sizeof(int*)*rSize);
        for(int i = 0; i < rSize; i++) //initialize the maxes states matrix;
        {
            maxes[i] = (int*)malloc(sizeof(int)*cSize);
            for(int j = 0; j < cSize; j++)
                maxes[i][j] = -1;
        }
        int max = 0;
        for(int r = 0; r < rSize; r++) //try to start the traversal from each cell;
        {
            for(int c = 0; c < cSize; c++)
            {
                int t = traverse(r, c, rSize, cSize, matrix, maxes);
                if(t > max)
                    max = t;
            }
        }
        return max;
    }

Log in to reply
 

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