Path from source to destination, with increasing values

Question

Given a source and destination, in an integer matrix, find path, such that the next position in the path has a greater than or equal to value than the previous position. In other words monotonically increasing. In event of multiple paths, a non-optimal solution may be returned.

I'm looking for code review, best practices, optimizations etc. Verifying complexity to be O (n * m) where n is row and m is column count.

final class Point {
    private final int row;
    private final int col;

    public Point(int i, int j) {
        this.row = i;
        this.col = j;
    }

    public int getI() {
        return row;
    }

    public int getJ() {
        return col;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null) return false;
        if (getClass() != o.getClass()) return false;
        final Point c = (Point)o;
        return row == c.row && col == c.col;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + row;
        result = prime * result + col;
        return result;
    }
}



public class IncreasingPath {

    private int[][] m;

    public IncreasingPath(int[][] m) {
        if (m == null) throw new NullPointerException("The matrix cannot be null");
        if (m.length == 0) throw new IllegalArgumentException("The matrix should not be empty");
        this.m = m;
    }

    /**
 * Given a start and end position in matrix returns the path of continously increasing numbers.
 * If multiple paths exists then any one of the path would be returned.
 * If no such path exists then empty list is returned.
 * 
 * 
 * 
 * @param startRow          the row index of the start position
 * @param startColumn       the col index of the start position     
 * @param endRow            the row index of the end position
 * @param endCol            the col index of the end position
 * @return                  the increasing path from source to destination if it exists.
 */
    public List<Point> increasingPath(int startRow, int startColumn, int endRow, int endCol) {
        validate(startRow, startColumn, endRow, endCol);

        final List<Point> pointPath = new ArrayList<Point>();
        pathFind(startRow, startColumn, endRow, endCol, pointPath);
        return pointPath;
    }

    private void validate (int startRow, int startColumn, int endRow, int endCol) {
        if (startRow < 0 || startRow >= m.length)
            throw new IllegalArgumentException("The start row " + startRow + " out of bounds." );

        if (startColumn < 0 || startColumn >= m[0].length) 
            throw new IllegalArgumentException("The start col " + startColumn + " out of bounds." );

        if (endRow < 0 || endRow >= m.length)
            throw new IllegalArgumentException("The end row " + endRow + " out of bounds." );

        if (endCol < 0 || endCol >= m[0].length) 
            throw new IllegalArgumentException("The end col " + endCol + " out of bounds." );
    }

    private boolean pathFind(int row, int col, int endRow, int endCol, List<Point> pointPath) {
        final Point coordinate = new Point(row, col);

        if (row == endRow && col == endCol) {
            pointPath.add(coordinate); 
            return true; 
        }

        if (pointPath.contains(coordinate)) {
            return false;
        } else {
            pointPath.add(coordinate);
        }

        for (int i = Math.max(0, row - 1); i < Math.min(m.length, row + 2); i++) {
            for (int j = Math.max(0, col - 1); j < Math.min(m[0].length, col + 2); j++) {

                // Skip the tile (i, j) itself
                if (i == row && j == col)
                    continue;

                if (m[row][col] <= m[i][j]  && m[i][j] <= m[endRow][endCol]) {
                    if (pathFind(i, j, endRow, endCol, pointPath)) return true;
                }
            }
        }
        pointPath.remove(coordinate);
        return false;
    }


    public static void main(String[] args) {

        int[][] m = { {1,  2,  3,  4 },
                      {5,  6,  7,  8 },
                      {9, 10, 11, 12 } };

        IncreasingPath lip = new IncreasingPath(m);

        List<Point> points1 = new ArrayList<Point>();
        points1.add(new Point(0, 0));
        points1.add(new Point(0, 1));
        points1.add(new Point(0, 2));
        points1.add(new Point(0, 3));
        points1.add(new Point(1, 2));
        points1.add(new Point(1, 3));
        points1.add(new Point(2, 2));
        points1.add(new Point(2, 3));

        Assert.assertEquals(points1, lip.increasingPath(0, 0, 2, 3));

        List<Point> points2 = new ArrayList<Point>();
        points2.add(new Point(0, 2));
        points2.add(new Point(1, 1));
        points2.add(new Point(2, 0)); 

        Assert.assertEquals(points2, lip.increasingPath(0, 2, 2, 0));

        Assert.assertEquals(new ArrayList<Point>(), lip.increasingPath(2, 0, 0, 2));
    }
}

Answer 1

Just two quick notes:

1. It's usually a good practice to make a copy of mutable input parameters. (int[][] m array in this case.) It prohibits malicious clients to modify the internal structure of the class or it could save you from a few hours of debugging. (Effective Java, 2nd Edition, Item 39: Make defensive copies when needed)

2. There is some duplication is the validate method. Every condition is the same with different variable names. You could move that to a helper function:

   private void validate (int startRow, int startColumn, int endRow, int endCol) {
       checkInRange(startRow, 0, m.length, "The start row " + startRow + " out of bounds.");
       checkInRange(startColumn, 0, m[0].length), "The start col " + startColumn + " out of bounds.");
       checkInRange(endRow, 0, m.length, "The end row " + endRow + " out of bounds.");
       checkInRange(endCol, 0, m[0].length, "The end col " + endCol + " out of bounds.");
   }
   
   private void checkInRange(int value, int lowerBound, int upperBound, String message) {
       if (value < lowerBound || value >= upperBound) {
           throw new IllegalArgumentException(message);
       }
   }
   

Answer 2

In event of multiple paths, a non-optimal solution may be returned.

Problem description clearly states there may be multiple solutions.

But in the test:

    List<Point> points1 = new ArrayList<Point>();
    points1.add(new Point(0, 0));
    //....more points........
    points1.add(new Point(2, 3));

    Assert.assertEquals(points1, lip.increasingPath(0, 0, 2, 3));

You compare the found solution (which is suboptimal) to itself after the fact. Instead you should verify that the solution is correct using the definition given in the question. e.g.

• first element is the solution is the given start point,
• last element is the given end point,
• each point in the path is the neighbor to another.
• and the values in the matrix corresponding to those points are non-decreasing.

I also don't like empty list as failure. I would prefer guava's Optional or something equivalent.