Skip to main content
3 of 3
deleted 22 characters in body
JavaDeveloper
  • 8.4k
  • 29
  • 92
  • 159

Path from source to destination, with increasing values

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));
    }
}
JavaDeveloper
  • 8.4k
  • 29
  • 92
  • 159