Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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

}
share|improve this question

3 Answers 3

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.

share|improve this answer

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.

share|improve this answer
    
good catch, didn't saw that. –  chillworld May 6 at 12:12
    
@Simon - you have very good points - and apologize for neglecting valuable comment ! Noted. –  JavaDeveloper May 6 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

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);
    }
}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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