Leetcode | Longest Increasing Path in a Matrix | Java

devstromo · devstromo · commit 4af8582d6fc3 · 2025-04-25T22:14:12.000-03:00
diff --git a/leetcode/src/main/java/com/devstromo/hard/p329/DESCRIPTION.md b/leetcode/src/main/java/com/devstromo/hard/p329/DESCRIPTION.md
@@ -0,0 +1,31 @@
+# 329. Longest Increasing Path in a Matrix
+
+Given an `m x n` integers `matrix`, return the length of the longest increasing path in `matrix`.
+
+From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (i.e., wrap-around is not allowed).
+
+Example 1:
+
+Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]
+Output: 4
+Explanation: The longest increasing path is [1, 2, 6, 9].
+
+Example 2:
+
+Input: matrix = [[3,4,5],[3,2,6],[2,2,1]]
+Output: 4
+Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.
+
+Example 3:
+
+Input: matrix = [[1]]
+Output: 1
+
+Constraints:
+
+- `m == matrix.length`
+- `n == matrix[i].length`
+- `1 <= m, n <= 200`
+- `0 <= matrix[i][j] <= 2^31 - 1`
+
+
diff --git a/leetcode/src/main/java/com/devstromo/hard/p329/Solution.java b/leetcode/src/main/java/com/devstromo/hard/p329/Solution.java
@@ -0,0 +1,41 @@
+package com.devstromo.hard.p329;
+
+public class Solution {
+    private final int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
+    private int rows, cols;
+
+    public int longestIncreasingPath(int[][] matrix) {
+        rows = matrix.length;
+        cols = matrix[0].length;
+        int[][] memo = new int[rows][cols];
+        int maxPath = 0;
+
+        for (int r = 0; r < rows; r++) {
+            for (int c = 0; c < cols; c++) {
+                maxPath = Math.max(maxPath, dfs(matrix, r, c, memo));
+            }
+        }
+
+        return maxPath;
+    }
+
+    private int dfs(int[][] matrix, int r, int c, int[][] memo) {
+        if (memo[r][c] != 0) return memo[r][c];
+
+        int maxLength = 1; // Start with 1 (itself)
+        for (int[] dir : directions) {
+            int newRow = r + dir[0];
+            int newCol = c + dir[1];
+
+            if (newRow >= 0 && newRow < rows &&
+                    newCol >= 0 && newCol < cols &&
+                    matrix[newRow][newCol] > matrix[r][c]) {
+                int length = 1 + dfs(matrix, newRow, newCol, memo);
+                maxLength = Math.max(maxLength, length);
+            }
+        }
+
+        memo[r][c] = maxLength;
+        return maxLength;
+    }
+}
diff --git a/leetcode/src/test/java/com/devstromo/hard/p329/SolutionUnitTest.java b/leetcode/src/test/java/com/devstromo/hard/p329/SolutionUnitTest.java
@@ -0,0 +1,24 @@
+package com.devstromo.hard.p329;
+
+import org.junit.jupiter.api.DisplayName;
+import org.junit.jupiter.api.Test;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+class SolutionUnitTest {
+    private final Solution solution = new Solution();
+
+    @Test
+    @DisplayName("Test Longest Increasing Path in a Matrix")
+    void testLongestIncreasingPath() {
+        assertEquals(4, solution.longestIncreasingPath(new int[][]{
+                {3, 4, 5},
+                {3, 2, 6},
+                {2, 2, 1}
+        }));
+        assertEquals(1, solution.longestIncreasingPath(new int[][]{
+                {1}
+        }));
+    }
+
+}
