Minimum path in squares in Java

The challenge

You’re given a square consisting of random numbers, like so:

var square = [ [1,2,3], [4,8,2], [1,5,3] ];
Code language: JavaScript (javascript)

Your job is to calculate the minimum total cost when moving from the upper left corner to the coordinate given. You’re only allowed to move right or down.

In the above example the minimum path would be:

var square = [ [1,2,3], [_,_,2], [_,_,3] ];
Code language: JavaScript (javascript)

Giving a total of 11. Start and end position are included.

Note: Coordinates are marked as x horizontally and y vertically.

The solution in Java code

Option 1:

import java.util.Arrays; public class MinPathSquare { public static int minPath(int[][] grid, int x, int y) { int[] s = new int[x+2]; Arrays.fill(s, Integer.MAX_VALUE); s[1] = 0; for (int i = 0 ; i <= y ; i++) for (int j = 0 ; j <= x ; j++) s[j+1] = Math.min(s[j], s[j+1]) + grid[i][j]; return s[s.length-1]; } }
Code language: Java (java)

Option 2:

public class MinPathSquare { public static int minPath(int[][] grid, int x, int y) { int[] arr = new int[(x + 1)]; arr[0] = grid[0][0]; for (int j = 1; j <= x; j++) { arr[j] = grid[0][j] + arr[j - 1]; } for (int i = 1; i <= y; i++) { arr[0] = grid[i][0] + arr[0]; for (int j = 1; j <= x; j++) { arr[j] = Math.min(grid[i][j] + arr[j - 1], grid[i][j] + arr[j]); } } return arr[x]; } }
Code language: Java (java)

Option 3:

import java.util.*; public class MinPathSquare { public static int minPath(int[][] grid, int x, int y) { final int INF = Integer.MAX_VALUE; var board = new int[x + 1]; Arrays.fill(board, INF); board[0] = 0; for (int j = 0; j <= y; j++) for (int i = 0; i <= x; i++) board[i] = grid[j][i] + Math.min(board[i], i == 0 ? INF : board[i - 1]); return board[x]; } }
Code language: Java (java)

Test cases to validate our solution

import org.junit.Test; import static org.junit.Assert.assertEquals; import org.junit.runners.JUnit4; public class SolutionTest { private static int[][] smallSquare = new int[][] { { 1, 2, 3, 6, 2, 8, 1 }, { 4, 8, 2, 4, 3, 1, 9 }, { 1, 5, 3, 7, 9, 3, 1 }, { 4, 9, 2, 1, 6, 9, 5 }, { 7, 6, 8, 4, 7, 2, 6 }, { 2, 1, 6, 2, 4, 8, 7 }, { 8, 4, 3, 9, 2, 5, 8 } }; @Test public void smallTests() { assertEquals(1, MinPathSquare.minPath(smallSquare, 0, 0)); assertEquals(5, MinPathSquare.minPath(smallSquare, 0, 1)); assertEquals(11, MinPathSquare.minPath(smallSquare, 2, 2)); assertEquals(24, MinPathSquare.minPath(smallSquare, 4, 2)); assertEquals(39, MinPathSquare.minPath(smallSquare, 6, 6)); assertEquals(24, MinPathSquare.minPath(smallSquare, 4, 5)); } }
Code language: Java (java)
Tags:
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments