Optimize MinimumPathSum (TheAlgorithms#4400)

Manan-09 · web-flow · commit 9d8a0f36cfa4 · 2023-09-25T14:25:16.000Z
diff --git a/src/main/java/com/thealgorithms/dynamicprogramming/MinimumPathSum.java b/src/main/java/com/thealgorithms/dynamicprogramming/MinimumPathSum.java
@@ -12,9 +12,8 @@
 (m)
 Find the path where its sum is the smallest.
 
-All numbers given are positive.
 The Time Complexity of your algorithm should be smaller than or equal to O(mn).
-The Space Complexity of your algorithm should be smaller than or equal to O(mn).
+The Space Complexity of your algorithm should be smaller than or equal to O(n).
 You can only move from the top left corner to the down right corner.
 You can only move one step down or right.
 
@@ -25,46 +24,41 @@ The Space Complexity of your algorithm should be smaller than or equal to O(mn).
 
 For more information see https://www.geeksforgeeks.org/maximum-path-sum-matrix/
  */
-public class MinimumPathSum {
+public final class MinimumPathSum {
 
-    public void testRegular() {
-        int[][] grid = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
-        System.out.println(minimumPathSum(grid));
+    private MinimumPathSum() {
     }
 
-    public void testLessColumns() {
-        int[][] grid = {{1, 2}, {5, 6}, {1, 1}};
-        System.out.println(minimumPathSum(grid));
-    }
-
-    public void testLessRows() {
-        int[][] grid = {{2, 3, 3}, {7, 2, 1}};
-        System.out.println(minimumPathSum(grid));
-    }
+    public static int minimumPathSum(final int[][] grid) {
+        int numRows = grid.length;
+        int numCols = grid[0].length;
 
-    public void testOneRowOneColumn() {
-        int[][] grid = {{2}};
-        System.out.println(minimumPathSum(grid));
-    }
-
-    public static int minimumPathSum(int[][] grid) {
-        int m = grid.length, n = grid[0].length;
-        if (n == 0) {
+        if (numCols == 0) {
             return 0;
         }
-        int[][] dp = new int[m][n];
-        dp[0][0] = grid[0][0];
-        for (int i = 0; i < n - 1; i++) {
-            dp[0][i + 1] = dp[0][i] + grid[0][i + 1];
-        }
-        for (int i = 0; i < m - 1; i++) {
-            dp[i + 1][0] = dp[i][0] + grid[i + 1][0];
+
+        int[] dp = new int[numCols];
+
+        // Initialize the first element of the dp array
+        dp[0] = grid[0][0];
+
+        // Calculate the minimum path sums for the first row
+        for (int col = 1; col < numCols; col++) {
+            dp[col] = dp[col - 1] + grid[0][col];
         }
-        for (int i = 1; i < m; i++) {
-            for (int j = 1; j < n; j++) {
-                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
+
+        // Calculate the minimum path sums for the remaining rows
+        for (int row = 1; row < numRows; row++) {
+            // Update the minimum path sum for the first column
+            dp[0] += grid[row][0];
+
+            for (int col = 1; col < numCols; col++) {
+                // Choose the minimum path sum from the left or above
+                dp[col] = Math.min(dp[col - 1], dp[col]) + grid[row][col];
             }
         }
-        return dp[m - 1][n - 1];
+
+        // Return the minimum path sum for the last cell in the grid
+        return dp[numCols - 1];
     }
 }
diff --git a/src/test/java/com/thealgorithms/dynamicprogramming/MinimumPathSumTest.java b/src/test/java/com/thealgorithms/dynamicprogramming/MinimumPathSumTest.java
@@ -1,6 +1,6 @@
 package com.thealgorithms.dynamicprogramming;
 
-import static org.junit.jupiter.api.Assertions.*;
+import static org.junit.jupiter.api.Assertions.assertEquals;
 
 import org.junit.jupiter.api.Test;
 
@@ -41,4 +41,10 @@ public void testMinimumPathSumWithDiffRowAndColumnGrid() {
         int[][] grid = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}};
         assertEquals(30, MinimumPathSum.minimumPathSum(grid));
     }
+
+    @Test
+    public void testMinimumPathSumWithNegativeNumberGrid() {
+        int[][] grid = {{1, 3, 1}, {3, 4, 1}, {4, -3, 1}};
+        assertEquals(6, MinimumPathSum.minimumPathSum(grid));
+    }
 }
