Recursion Longest Increasing Path in matrix

Question

I am implementing longest increasing path problem of leetcode.

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).

Example 1:

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

So Below is my implementation tries a lot on recursion, but not able to understand why it is not giving correct result why maxDist decreases from 4 to 3 to 2 in this example, as this variable is is global not local.

public class LongestIncreasingPath {

    private static final int[][] dirs = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
    private int m, n;
    int maxDist;

    public int longestIncreasingPath(int[][] matrix) {
        if (matrix.length == 0)
            return 0;
        m = matrix.length;
        n = matrix[0].length;
        int ans = 1;
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j) {
                dfs(matrix, i, j, 1);
                ans = Math.max(ans, maxDist);
            }
        return ans;
    }
    private int dfs(int[][] matrix, int i, int j, int dist) {
        for (int[] d : dirs) {
            int x = i + d[0], y = j + d[1];
            if (0 <= x && x < m && 0 <= y && y < n && matrix[x][y] > matrix[i][j]) {
                maxDist = Math.max(maxDist, dfs(matrix, x, y, dist+1));
            }
        }
        return dist;
    }

    public static void main(String[] args) {
        int[][] nums = { { 9, 9, 4 }, { 6, 6, 8 }, { 2, 1, 1 } };
        LongestIncreasingPath lIP = new LongestIncreasingPath();
        System.out.println(lIP.longestIncreasingPath(nums));
    }
}

Answer 1

The following is a working version, tested on 2 test cases (only). Please note the comments about bugs and some changes in structure:

public class LongestIncreasingPath {

    private static final int[][] dirs = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
    private int rows, cols;
    //avoid non-volatile class variable that may be updated by more than one thread
    //use local variables instead
    //private int maxDist;

    public int longestIncreasingPath(int[][] matrix) {
        if (matrix.length == 0) return 0;
        rows = matrix.length;
        cols = matrix[0].length;

        int maxDist = 0; //retain max found
        for (int row = 0; row < rows; ++row) {
            for (int col = 0; col < cols; ++col) {
                //bug fix: use distance (matrix[row][col]) instead of 1
                int  distance = dfs(matrix, row, col, matrix[row][col]);
                maxDist = Math.max(distance, maxDist);
            }
        }
        return maxDist;
    }

    private int dfs(int[][] matrix, int row, int newCol, int dist) {

        int maxDist = dist; 
        for (int[]dir : dirs) {
            int newRow = row + dir[0], y = newCol + dir[1];
            if (0 <= newRow && newRow < rows && 0 <= y && y < cols &&
                                        matrix[newRow][y] > matrix[row][newCol]) {
                //bug fix: //add new distance matrix[x][y] instead of 1
                maxDist = Math.max(maxDist, dfs(matrix, newRow, y, dist + matrix[newRow][y]));
            }
        }
        return maxDist;
    }

    public static void main(String[] args) {

        LongestIncreasingPath lIP = new LongestIncreasingPath();
        int[][] nums = { { 9, 9, 4 },
                         { 6, 6, 8 },
                         { 2, 2, 1 }
                        };
        //printout test case 1
        System.out.println(lIP.longestIncreasingPath(nums));
        nums = new int[][]{ { 5, 6, 7 },
                            { 4, 9, 8 },
                            { 3, 2, 1 }
                        };
        //printout test case 2
        System.out.println(lIP.longestIncreasingPath(nums));
    }
}