patternjavaMinor
Path from source to destination, with increasing values
Viewed 0 times
destinationpathsourcewithincreasingvaluesfrom
Problem
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 i
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 i
Solution
Just two quick notes:
-
It's usually a good practice to make a copy of mutable input parameters. (
-
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:
-
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) -
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 = upperBound) {
throw new IllegalArgumentException(message);
}
}Code Snippets
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);
}
}Context
StackExchange Code Review Q#42396, answer score: 4
Revisions (0)
No revisions yet.