Problem Statement
A group of farmers has some elevation data, and we’re going to help them understand how rainfall flows over their farmland.
We’ll represent the land as a two-dimensional array of altitudes and use the following model, based on the idea that water flows downhill:
If a cell’s eight neighboring cells all have higher altitudes, we call this cell a basin; water collects in basin.
Otherwise, water will flow to the neighboring cell with the lowest altitude.
Cells that drain into the same sink – directly or indirectly – are said to be part of the same basin.
A few examples are below:
----------------------------------------- Input: Output: 1 1 2 1 4 ( basin is 1, and size is 4) 1 1 7 3 6 9
Looking for code review optimizations and best practices. Complexity - both time and space is O(n*m)
final class BasinData {
private final int item;
private final int count;
public BasinData(int item, int count) {
this.item = item;
this.count = count;
}
public int getItem() {
return item;
}
public int getCount() {
return count;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + count;
result = prime * result + item;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
BasinData other = (BasinData) obj;
if (count != other.count)
return false;
if (item != other.item)
return false;
return true;
}
}
/**
* References:
* http://www.geeksforgeeks.org/flipkart-interview-set-2-for-sde-1/
*
* Complexity:
* O(n2)
*/
public final class Basin {
private Basin() {}
private static enum Direction {
NW(-1, -1), N(0, -1), NE(-1, 1), E(0, 1), SE(1, 1), S(1, 0), SW(1, -1), W(-1, 0);
int rowDelta;
int colDelta;
Direction(int rowDelta, int colDelta) {
this.rowDelta = rowDelta;
this.colDelta = colDelta;
}
public int getRowDelta() {
return rowDelta;
}
public int getColDelta() {
return colDelta;
}
}
/**
* Returns the minimum basin.
* If more than a single minimum basin exists then returns any arbitrary basin.
*
* @param m : the input matrix
* @return : returns the basin item and its size.
*/
public static BasinData getMaxBasin(int[][] m) {
final List<BasinCount> basinCountList = new ArrayList<BasinCount>();
final boolean[][] visited = new boolean[m.length][m[0].length];
for (int i = 0; i < m.length; i++) {
for (int j = 0; j < m[0].length; j++) {
if (!visited[i][j]) {
basinCountList.add(scan(m, visited, i, j, m[i][j], new BasinCount(0, true, m[i][j])));
}
}
}
int maxCount = Integer.MIN_VALUE;
int item = 0;
for (BasinCount c : basinCountList) {
if (c.basin) {
if (c.count > maxCount) {
maxCount = c.count;
item = c.item;
}
}
}
return new BasinData(item, maxCount);
}
private static class BasinCount {
int count;
boolean basin;
int item;
BasinCount(int count, boolean basin, int item) {
this.count = count;
this.basin = basin;
this.item = item;
}
};
private static BasinCount scan(int[][] m, boolean[][] visited, int row, int col, int val, BasinCount baseCount) {
if (row < 0 || row == m.length || col < 0 || col == m[0].length) return baseCount;
if (m[row][col] < val) {
baseCount.basin = false;
return baseCount;
}
if (visited[row][col]) {
return baseCount;
}
if (m[row][col] > val) return baseCount;
visited[row][col] = true;
baseCount.count++;
for (Direction dir : Direction.values()) {
scan(m, visited, row + dir.getRowDelta(), col + dir.getColDelta(), val, baseCount);
}
return baseCount;
}
}
public class BasinTest {
@Test
public void testBlock() {
int[][] m1 = { {1, 1, 2},
{1, 1, 3},
{4, 5, 6}, };
assertEquals(new BasinData(1, 4), Basin.getMaxBasin(m1));
}
@Test
public void testRandomlyShapedBasin() {
int[][] m2 = { {1, 1, 1, 1},
{1, 1, 3, 1},
{4, 5, 6, 2} };
assertEquals(new BasinData(1, 7), Basin.getMaxBasin(m2));
}
@Test
public void testSingleElementBasin() {
int[][] m3 = { {1, 1, 1, 1},
{1, 1, 3, 1},
{4, 5, 6, 0} };
assertEquals(new BasinData(0, 1), Basin.getMaxBasin(m3));
}
}