Update Longest Increasing Path in a Matrix.java

varunu28 · web-flow · commit be9503e25581 · 2022-05-19T06:51:28.000+05:30
diff --git a/Hard/Longest Increasing Path in a Matrix.java b/Hard/Longest Increasing Path in a Matrix.java
@@ -1,36 +1,30 @@
 class Solution {
-    int[][] dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
-    public int longestIncreasingPath(int[][] matrix) {
-        if (matrix.length == 0 || matrix[0].length == 0) {
-            return 0;
-        }
-        
-        int[][] dp = new int[matrix.length][matrix[0].length];
-        int max = 0;
-        for (int i = 0; i < matrix.length; i++) {
-            for (int j = 0; j < matrix[0].length; j++) {
-                max = Math.max(max, dfs(matrix, i, j, dp, Integer.MIN_VALUE));
-            }
-        }
-        
-        return max;
+  private final int[][] DIRS = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
+
+  public int longestIncreasingPath(int[][] matrix) {
+    int numRows = matrix.length;
+    int numCols = matrix[0].length;
+    int maxPathLength = 0;
+    int[][] cache = new int[numRows][numCols];
+    for (int i = 0; i < numRows; i++) {
+      for (int j = 0; j < numCols; j++) {
+        maxPathLength = Math.max(maxPathLength, helper(matrix, numRows, numCols, i, j, cache));
+      }
     }
-    
-    private int dfs(int[][] matrix, int x, int y, int[][] dp, int prevVal) {
-        if (x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length || matrix[x][y] <= prevVal) {
-            return 0;
-        }
-        
-        if (dp[x][y] != 0) {
-            return dp[x][y];
-        }
-        
-        int temp = 0;
-        for (int[] dir : dirs) {
-            temp = Math.max(temp, dfs(matrix, x + dir[0], y + dir[1], dp, matrix[x][y]));
-        }
-        
-        dp[x][y] = temp + 1;
-        return dp[x][y];
+    return maxPathLength;
+  }
+
+  private int helper(int[][] matrix, int numRows, int numCols, int i, int j, int[][] cache) {
+    if (cache[i][j] != 0) {
+      return cache[i][j];
     }
+    for (int[] dir : DIRS) {
+      int x = i + dir[0];
+      int y = j + dir[1];
+      if (x >= 0 && y >= 0 && x < numRows && y < numCols && matrix[x][y] > matrix[i][j]) {
+        cache[i][j] = Math.max(cache[i][j], helper(matrix, numRows, numCols, x, y, cache));
+      }
+    }
+    return ++cache[i][j];
+  }
 }
