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]
];

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]
];

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];
    }
}

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];
  }
}

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];
  }
}

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));
    }
}