Calling this "Hard" is Unfair to Other Hard Questions


  • 0
    R

    It's pretty straightforward Dfs + memoization. You don't even need to mark cells as seen due to the nature of the problem.
    I think there are plenty of "Medium" rated questions out there that are a lot harder than this one :)


  • 0

    Can we start at (0,0) and do just one time DFS to solve this?


  • 0
    R

    No, you have to try starting from every node, because the longest path can be starting anywhere and the start point won't be reachable otherwise, since the start point will be the minimum number in the sequence, and in your search you don't go to the nodes that are smaller than the current.


  • 0

    @rmn But what if you continue the DFS procedure on the smaller nodes? For instance, let's do DFS for the greater neighbors first, so you can get the max path length for current node, then continue DFS for the smaller adjacent neighbors if there are any.


  • 0
    R

    Sure but that wouldn't mean better complexity. when you memorize the distance of the longest increasing path from each node, the complexity is already the best possible, which is O(N). The code is also pretty simple if you just try all start positions one-by-one.

    If you think you cam implement it in a simpler way with your approach, can you share your code? Here's mine:
    (Please note that I always favor readability over length, so I didn't make it as short as it can be)

    public class Solution {
        public int LongestIncreasingPath(int[,] matrix) 
        {
            int rowcnt = matrix.GetLength(0);
            int colcnt = matrix.GetLength(1);
            
            int[,] memo = new int[rowcnt,colcnt];
            int maxlen = 0;
            
            for(int row = 0; row < rowcnt; ++row)
                for(int col = 0; col < colcnt; ++col)
                {
                    maxlen = Math.Max(maxlen, Dfs(matrix, row, col, memo));
                }
                
            return maxlen;
        }
        
        private int Dfs(int[,] m, int row, int col, int[,] memo)
        {
            if(memo[row,col] != 0) 
                return memo[row,col];
            
            int up = 0, down = 0, left = 0, right = 0;
            int n = m[row,col];
            
            if(row > 0 && m[row - 1,col] > n)
                up = Dfs(m, row - 1, col, memo);
                
            if(row < m.GetLength(0) - 1 && m[row + 1,col] > n)
                down = Dfs(m, row + 1, col, memo);
                
            if(col > 0 && m[row,col - 1] > n)
                left = Dfs(m, row, col - 1, memo);
                
            if(col < m.GetLength(1) - 1 && m[row,col + 1] > n)
                right = Dfs(m, row, col + 1, memo);
                
            memo[row,col] = Math.Max(up, Math.Max(down, Math.Max(left, right))) + 1;
            return memo[row,col];
        }
    }
    

  • 0

    @rmn DFS usually means you start at a point to traverse the whole graph, to find out trying DFS with every node really needs good observation, I think that's the difficult part of this problem. Don't know how many ppl figured out this without any hint, I actually didn't recognize this at the very beginning, and started with the naive DFS way, the critical problem of this method is not the implementation difficulty, it's the subtle dependencies between the cells, which will give a wrong result in the end.


Log in to reply
 

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