Time Difficulty finding a pool

Question

To find the pool in the matrix, the following algorithm is used. The whole question is as follows:

2-D matrix, where each cell represents the height of the cell. water can flow from a cell with a higher height to the bottom. There is a pool when there is no cell with a lower height in the neighbors (Left, Right, Up, Down, Diagonally). You should find the maximum pool unit size.

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

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.

Difficulties cannot be lower than O (n * m), since any cell can be part of a neighboring max-pool in the general case, and therefore all should be considered (in general). Your difficulty is O (n * m) due to two nested for-loops in getMaxBasin, and the fact that visited [i] [j] can be set in only one place (inside scan ()) and prevents later visits of the same cell.

Due to recursion, every time you bind call scanning (), you add to the stack. With a fairly long chain of calls to scan (), you may run into stack restrictions. In the worst case, this is a zigzag pattern, so the stack ends up with a scan () call for each cell.