3
\$\begingroup\$

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));
    }
}
\$\endgroup\$
3
  • 4
    \$\begingroup\$ You've indicated that you are preparing for interviews, and indeed we've seen your coding skills improve over the last 88 questions. I think that if you try answering some other users' questions, you'll find it rewarding and educational as well. Part of being a good programmer is being able to work with other people's code and communicate your thoughts effectively. I humbly suggest that at this point, trying to answer questions may do more for your interview skills than cranking out yet another algorithm. \$\endgroup\$ Feb 21, 2014 at 10:20
  • \$\begingroup\$ I'd consider this question to have a self-contradiction. If the sequence is monotonically increasing, then each element is strictly greater than the previous. If the sequence is monotonically nondecreasing, then each element is greater than or equal to the previous. \$\endgroup\$ Feb 21, 2014 at 10:24
  • 2
    \$\begingroup\$ It is very much in my mind, it might be some while before I contribute, but I certainly would. \$\endgroup\$ Feb 21, 2014 at 17:25

2 Answers 2

4
\$\begingroup\$

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);
        }
    }
    
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Welcome to 2K! You've been around for a while, FYI you're welcome anytime in The 2nd Monitor! \$\endgroup\$ Feb 24, 2014 at 13:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.