Leet Code 329. Longest Increasing Path in a Matrix

                                                         

package pep.Day44;

import java.util.LinkedList;
import java.util.Queue;

public class LeetCode_329_Longest_Increasing_Path_in_Matrix {
    // can be done by DP, DFS  - kahn's algo
    public static int longestIncreasingPath(int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;

        int[][] indegree = new int[n][m];

        int[][] dirns = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {

                for (int[] dir : dirns) {
                    int x = dir[0] + i;
                    int y = dir[1] + j;

                    if (x >= 0 && y >= 0 && x < n && y < m)
                        // merakoi bhi nbr bada milta hai toh indegree +1 kr denge
                        if (matrix[i][j] < matrix[x][y])
                            indegree[x][y]++;
                }
            }
        }

        Queue<Integer> queue = new LinkedList<>();
        // firse traverse krenge yeh dhundhne ke lea kiski indegree 0 hai
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (indegree[i][j] == 0)
                    queue.add(i * m + j);
            }
        }

        int level = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();

            while (size-- > 0) {
                int rem = queue.remove();
                int i = rem / m;
                int j = rem % m;

                for (int[] dir : dirns) {
                    int x = dir[0] + i;
                    int y = dir[1] + j;

                    if (x >= 0 && y >= 0 && x < n && y < m) {
                        if (matrix[i][j] < matrix[x][y]) {
                            if (--indegree[x][y] == 0)
                                queue.add(x * m + y);
                        }
                    }

                }
            }
            level++;
        }

        return level + 1;
    }
}