# Find biggest basin

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));
}

}


I find this a nice piece of code.

Still I found 1 minor and 1 bigger issue.

## Bigger issue :

You say in the javadoc that if more then 1 bassin is found the biggest must be returned.
You implement nice testing but this I don't find back in the testings.
All your testings have 1 lowest bassin.
I should add this to the test :

@Test
public void testSingleElementBasin() {
int[][] m4 = { {1, 0, 0, 1},
{1, 0, 3, 1},
{4, 5, 6, 0} };
assertEquals(new BasinData(0, 3), Basin.getMaxBasin(m4));
}


## Minor :

I should refactor the public static BasinData getMaxBasin(int[][] m)

public static BasinData getMaxBasin(int[][] m) {
final List<BasinCount> basinCountList = getBassinCountList(m);
return getMaxBassin(basinCountList);
}


You put the space because you know you are doing 2 different things, just do that extra step to refactor to 2 methods.

# private final

I think this is not the first time I'm telling you this. The ints in your enum really should be private final (At least final!)

int rowDelta;
int colDelta;


Consider the code: Direction.S.rowDelta = 42; // OOPS!

That said, I think your Direction enum is good enough to be public. This is not the first time I see you use this enum. You're not copying it each time I hope? If you need to use it in several projects, create a project where you keep the common classes and then add that project as a required project to your build path.

• good catch, didn't saw that. Commented May 6, 2014 at 12:12
• @Simon - you have very good points - and apologize for neglecting valuable comment ! Noted. Commented May 6, 2014 at 18:13

There a few minor, and one bigger issue others haven't mentioned yet.

## Simplifying BasinData

I have a feeling that BasinData is something closely tied to Basin, it will never be extended, and it will never be part of a public API. As such, I think it's safe to simplify like this:

• Drop the private qualifier on fields, as final already protects them
• Drop the getItem, getCount accessors, you're not using them anyway

More important, the equals method implementation is awkward and hard to read. This would be simpler and better:

@Override
public boolean equals(Object obj) {
if (obj instanceof BasinData) {
BasinData other = (BasinData) obj;
return count == other.count && item == other.item;
}
return false;
}


## Improving Direction

As others have pointed out, make the fields final. And as with BasinData, I think you can drop the accessors.

## Improving the main algorithm

• Find the minimum value in the elevation matrix and its coordinates
• Use a recursive flood-fill method to find its size:
• Check if the current position is valid (inside the matrix), otherwise return 0
• Check if the current position has the same elevation value, otherwise return 0
• Return 1 + the result of recursively calling the method for the positions up, down, left, right

Here's an implementation of that, shorter and simpler:

// A simple "struct", to hold a group of values describing a basin:
// - the i, j coordinates in the matrix
// - the elevation value, storing here for convenience
class BasinInfo {
final int i;
final int j;
final int elevation;

BasinInfo(int i, int j, int elevation) {
this.i = i;
this.j = j;
this.elevation = elevation;
}
}

class BasinFinder {
// A value to use as marker in the flood-fill technique
// used in the getBasinSize method.
// The value should be something unique, that cannot be in the input matrix.
private static final int FLOODFILL_MARKER = Integer.MIN_VALUE;

// Find an arbitrary point in the matrix that has the minimum
// elevation value and return its coordinates and the value
// in a BasinInfo instance.
private BasinInfo findMinElevation(int[][] matrix) {
int minI = 0;
int minJ = 0;
int minValue = matrix[0][0];

for (int i = 0; i < matrix.length; ++i) {
for (int j = 0; j < matrix[i].length; ++j) {
if (matrix[i][j] < minValue) {
minValue = matrix[i][j];
minI = i;
minJ = j;
}
}
}
return new BasinInfo(minI, minJ, minValue);
}

// A utility method to deep-clone a matrix,
// so we don't modify the original matrix with flood-fill
private int[][] cloneMatrix(int[][] matrix) {
int[][] newMatrix = new int[matrix.length][];
for (int i = 0; i < matrix.length; ++i) {
newMatrix[i] = matrix[i].clone();
}
return newMatrix;
}

// The flood-fill method, exploring the matrix from some starting point,
// marking visited positions, and spreading up to positions with matching value
private int getBasinSize(int[][] matrix, int i, int j, int value) {
if (isValidPosition(matrix, i, j)) {
if (matrix[i][j] == value) {
matrix[i][j] = FLOODFILL_MARKER;
return 1
+ getBasinSize(matrix, i + 1, j, value)
+ getBasinSize(matrix, i - 1, j, value)
+ getBasinSize(matrix, i, j + 1, value)
+ getBasinSize(matrix, i, j - 1, value)
;
}
}
return 0;
}

private boolean isValidPosition(int[][] matrix, int i, int j) {
return i >= 0 && j >= 0 && i < matrix.length && j < matrix[i].length;
}

private BasinData getBasinData(int[][] matrix, BasinInfo basinInfo) {
int size = getBasinSize(cloneMatrix(matrix), basinInfo.i, basinInfo.j, basinInfo.elevation);
return new BasinData(basinInfo.elevation, size);
}

// The main method, performing the task in 2 phases:
// 1. Find an arbitrary point with minimum elevation
// 2. Measure the extent of the basin and return as a BasinData instance
public BasinData findBasin(int[][] matrix) {
BasinInfo basinInfo = findMinElevation(matrix);
return getBasinData(matrix, basinInfo);
}
}