w3resource

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:

Java Basic Exercises: Find a path from top left to bottom in right direction

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:

Flowchart: Java exercises: Find a path from top left to bottom in right direction.

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.



Become a Patron!

Follow us on Facebook and Twitter for latest update.

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