Time Complexity of finding a basin

Question

The following algorithm is used to find a basin in matrix. The whole question is as follows:

2-D matrix is given where each cell represents height of cell. Water can flow from cell with higher height to lower one. A basin is when there is no cell with lower height in the neighbours (left,right,up,down,diagonal). You have to find maximum size basin block.

I have implemented the code. I am looking for timeComplexity. In my opinion time complexity is O(n * m) where n and m is the row and column of the matrix. Please verify.

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

        private int rowDelta;
        private int colDelta;

        Direction(int rowDelta, int colDelta) {
            this.rowDelta = rowDelta;
            this.colDelta = colDelta;
        }

        public int getRowDelta() {
            return rowDelta;
        }

        public int getColDelta() {
            return colDelta;
        }
    }

    private static class BasinCount {
        private int count;
        private boolean isBasin;
        private int item;

        BasinCount(int count, boolean basin, int item) {
            this.count = count;
            this.isBasin = basin;
            this.item = item;
        }
    };

    /**
     * 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) {
        if (m.length == 0) { throw new IllegalArgumentException("The matrix should contain atleast one element."); }

        final boolean[][] visited = new boolean[m.length][m[0].length];
        final List<BasinCount> basinCountList = new ArrayList<>();

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

        return getMaxBasin(basinCountList);
    }


    private static BasinData getMaxBasin(List<BasinCount> basinCountList) {
        int maxCount = Integer.MIN_VALUE; 
        int item = 0;
        for (BasinCount c : basinCountList) {
            if (c.isBasin) {
                if (c.count > maxCount) {
                    maxCount = c.count;
                    item = c.item;
                }
            }
        }
        return new BasinData(item, maxCount);
    }



    private static BasinCount scan(int[][] m, boolean[][] visited, int row, int col, int item, BasinCount baseCount) {

        // array out of index
        if (row < 0 || row == m.length || col < 0 || col == m[0].length) return baseCount;

        // neighbor "m[row][col]" is lesser than me. now i cannot be the basin.
        if (m[row][col] < item) {
            baseCount.isBasin = false; 
            return baseCount; 
        }

        // my neighbor "m[row][col]" is greater than me, thus not to add it to the basin.
        if (m[row][col] > item) return baseCount;

        // my neighbor is equal to me, but i happen to have visited him already. thus simply return without adding count.
        // this is optimisitic recursion as described by rolf.
        if (visited[row][col]) { 
            return baseCount;
        }

        visited[row][col] = true;
        baseCount.count++;

        for (Direction dir : Direction.values()) {
            scan(m, visited, row + dir.getRowDelta(), col + dir.getColDelta(), item, baseCount);
            /**
             *  once we know that current 'item' is not the basin, we do "want" to explore other dimensions.
             *  With the commented out code - consider: m3
             *  If the first 1 to be picked up is "1 @ row2, col4." This hits zero, marks basin false and returns.
             *  Next time it starts with "1 @ row 0, col 0". This never encounters zero, because "1 @ row2, col4." is visited.
             *  this gives a false answer.
             */
//            if (!baseCount.basin) {
//                System.out.println(baseCount.item + "-:-:-");
//                return baseCount;
//            }
        }

        return baseCount;
    }

Answer 1

Yes, your code (assuming it works; I have not tested it) is O(n * m) in time, and O(n * m) in space.

Complexities cannot be lower than O(n * m), since any cell can be a part of a neighbouring max-basin in the general case, and all must therefore be (in general) examined. Your complexity is O(n * m) due to the two nested for-loops in getMaxBasin, and the fact that visited[i][j] can only be set at a single place (inside scan()), and prohibits later visits of the same cell.

Due to recursion, every time you chain a call scan(), you are adding to the stack. With a sufficiently-long chain of scan() calls, you could run into stack limits. The worst-case scenario is a zig-zag pattern so that the stack ends up containing a scan() call for each an every cell.