Java: Find a path from top left to bottom in right direction
Java Basic: Exercise-133 with Solution
Write a Java program to find a path from top left to bottom in the right direction which minimizes the sum of all numbers along its path.
Note: Move either down or right at any point in time.
Pictorial Presentation:
Sample Solution:
Java Code:
import java.util.*
public class Solution {
// Static method to find the minimum path sum in a 2D grid
public static int minPathSum(int[][] grid) {
// Check for invalid or empty input grid
if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {
return 0;
}
int m = grid.length; // Number of rows in the grid
int n = grid[0].length; // Number of columns in the grid
int[][] temp = new int[m][n]; // Temporary array to store minimum path sum
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 && j == 0) {
temp[i][j] = grid[i][j]; // Initialize the starting point
continue;
}
// Calculate the minimum path sum from either the cell above or the cell on the left
int from_up = i == 0 ? Integer.MAX_VALUE : temp[i - 1][j];
int from_left = j == 0 ? Integer.MAX_VALUE : temp[i][j - 1];
temp[i][j] = Math.min(from_up, from_left) + grid[i][j]; // Update the temporary array
}
}
// Return the minimum path sum for the last cell
return temp[m - 1][n - 1];
}
public static void main(String[] args) {
// Example grid
int[][] grid = new int[][] {{7, 4, 2},
{0, 5, 6},
{3, 1, 2}};
System.out.println("Sum of all numbers along its path: " + minPathSum(grid));
}
}
Sample Output:
Sum of all numbers along its path: 13
Flowchart:
Java Code Editor:
Previous: Write a Java program to find the updated length of a given sorted array where duplicate elements appear at most twice.
Next: Write a Java program to find distinct ways to climb to the top (n steps to reach the top) of stairs.
What is the difficulty level of this exercise?
Test your Programming skills with w3resource's quiz.
It will be nice if you may share this link in any developer community or anywhere else, from where other developers may find this content. Thanks.
https://www.w3resource.com/java-exercises/basic/java-basic-exercise-133.php
- Weekly Trends and Language Statistics
- Weekly Trends and Language Statistics