Longest Increasing Path in a Matrix

Problem: 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 are not allowed to move diagonally.

Example: (Taken from leetcode)

Input: nums = 
[
  [9,9,4],
  [6,6,8],
  [2,1,1]
] 
Output: 4 
Explanation: The longest increasing path is [1, 2, 6, 9].

Approach: A simple way to solve this problem is to use DFS by taking each and every cell as starting point, get the longest path for that cell and update the result if result is less than the recently found longest path but the time complexity will be very high (O(m^2 * n^2)). 

Let's see how we can make it better. We can use the dynamic programming. We can maintain a 2D Table where Table[i][j] will tell the longest increasing path if starting point of the DFS is (i, j), obviously Max of all the Table[i][j] is our answer. 

Now we can use this table while doing DFS. While doing DFS if we found at any cell (i, j), Table[i][j] is not 0 then we know that we have already processed this cell, now we can immediately return Table[i][j] and we don't need to traverse it further.

That's all!.

Implementation in C#:

        public int LongestIncreasingPathinMatrix(int[][] matrix)

        {

            if (matrix?.Length == 0)

            {

                return 0;

            }

            int[,] table = new int[matrix.Length, matrix[0].Length];

            int result = 0;

            // Do DFS by assuming every cell as starting node

            for (int i = 0; i < matrix.Length; ++i)

            {

                for (int j = 0; j < matrix[0].Length; ++j)

                {

                    // if table[i, j] is not 0 i.e. it is already processed

                    if (table[i, j] == 0)

                    {

                        this.Dfs(matrix, i, j, table, int.MinValue);

                        result = Math.Max(result, table[i, j]);

                    }

                }

            }

            return result;

        }

        private int Dfs(int[][] matrix, int row, int col, int[,] table, int prevValue)

        {

            // Boundary and increasing path condition 

            if (row < 0 || row >= matrix.Length || col < 0 || col >= matrix[0].Length || matrix[row][col] <= prevValue)

            {

                return 0;

            }

            // Already processed then return, no need to traverse further

            if (table[row, col] != 0)

            {

                return table[row, col];

            }

            // Take the longest increasing path at all 4 direction

            int leftValue = this.Dfs(matrix, row, col - 1, table, matrix[row][col]);

            int rightValue = this.Dfs(matrix, row, col + 1, table, matrix[row][col]);

            int upValue = this.Dfs(matrix, row - 1, col, table, matrix[row][col]);

            int downValue = this.Dfs(matrix, row + 1, col, table, matrix[row][col]);

            // Assign the maximum of all

            table[row, col] = Max(leftValue, rightValue, upValue, downValue) + 1;

            return table[row, col];

        }

        private static int Max(params int[] values)

        {

            return Enumerable.Max(values);

        }

Complexity: O(mn)