Find biggest basin

Question

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

}

Answer 1

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.

Answer 2

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.

Answer 3

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

Most important of all, your algorithm is unnecessarily complicated and hard to read. How about something like this instead:

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