329. Longest Increasing Path in a Matrix | My discuss post

Here is the link. 

C# | DFS + memorization | Editorial

Nov. 2, 2023

Intuition

I like to write a solution based on the solution provided by Editorial.

Approach

Naive DFS algorithm will have time-out issue, so DFS + memoization should work with TLE.

Complexity

• Time complexity:

O(mn).
Each vertex/cell will be calculated once and only once, and each edge will be visited once and only once. The total time complexity is then O(V+E). V is the total number of vertices and E is the total number of edges. In our problem, O(V)=O(mn), O(E)=O(4V)=O(mn).

• Space complexity:

O(mn). The cache dominates the space complexity.

Code

public class Solution {
     private static int[][] dirs = new int[][] {new int[]{0, 1}, new int[]{1, 0}, new int[]{0, -1}, new int[]{-1, 0}};
        private int m, n;
        
    public int LongestIncreasingPath(int[][] matrix)
        {
            if (matrix.Length == 0){
                return 0;
            }

            m = matrix.Length; 
            n = matrix[0].Length;

            var cache = new int[m][];
            for (int row = 0; row < m; row++)
            {
                cache[row] = new int[n];
            }

            int ans = 0;
            for (int i = 0; i < m; ++i)
            {
                for (int j = 0; j < n; ++j)
                {
                    ans = Math.Max(ans, dfs(matrix, i, j, cache));
                }
            }

            return ans;
        }

        /// <summary>
        /// What I learned on Nov. 6, 2023:
        /// 1. There is no loop - increasing order - no need to check visited or not
        /// 2. Every node will be visited once - save into cache
        /// 3. Every edge will be checked - each node has four neighbors - 4 * rows * columns
        /// 4. Understand how DFS works for this problem
        /// </summary>
        /// <param name="matrix"></param>
        /// <param name="i"></param>
        /// <param name="j"></param>
        /// <param name="cache"></param>
        /// <returns></returns>
        private int dfs(int[][] matrix, int i, int j, int[][] cache) {
            if (cache[i][j] != 0)
            {
                return cache[i][j];
            }

            foreach (var d in dirs) 
            {
                var x = i + d[0];
                var y = j + d[1];

                if (0 <= x && x < m && 0 <= y && y < n && matrix[x][y] > matrix[i][j])
                {
                    cache[i][j] = Math.Max(cache[i][j], dfs(matrix, x, y, cache));
                }
            }

            return ++cache[i][j];
        }
}