Find the largest pool size in a given matrix

Question

Problem:

This is an interview question.

A group of farmers has some elevation data and was about to help them understand how rainfall flows on their farmland.

Well imagine the earth as a two-dimensional array of heights and use the following model based on the idea that water flows downhill:

If the cells of eight neighboring cells are large, we call this cell a basin; water is collected in the pool.

Otherwise, water will flow into the next cell with the lowest height.

Cells that drain into the same sink - directly or indirectly - are considered part of the same pool.

Below are a few examples:

Entrance:

1 1 2
1 1 7
3 6 9

size 4

9 9 9 8 7 7
8 8 7 7 7 8
8 8 8 7 7 7
8 8 8 9 9 9
8 8 8 7 7 7
4 4 5 5 5 5
5 5 5 6 6 7
5 5 5 8 8 6

size 8

9 9 9 8 8 8
8 8 8 7 7 7
7 7 7 7 7 7
8 8 8 8 9 9
5 5 5 5 6 3
5 5 5 3 3 3

size 9

the highlighted values ​​form a pool of maximum size.

So the problem is

Break the map into pools. In particular, given the height map, your code should split the map into pools and display the dimensions of the largest pool. We need to allocate a pool of maximum size.

IF the problem had this assumption

"If the cell is not a receiver, you can assume that it has a unique low neighbor and that this neighbor will be smaller than the cell"

then I can think of this decision

Each array element is a node in a graph. Construct the graph adding edges between the nodes: 1 If node A is the smallest among all of its own neighbors, don't add an edge (it a sink) 2 There is an edge between two neighbors A and B iff A is the smallest of all neighbors of B. 3 Finally traverse the graph using BFS or DFS and count the elements in the connected components. 

uptill now i have implemented the third part of the algorithm

 #include<iostream> #include<vector> #include<string.h> #include<cstdio> #include<algorithm> #include<queue> using namespace std; int cv[1000]; // array stores number of nodes in each connected components int main() { queue<int>q; bool visited[100000]; int t,i,j,x,y,cvindex=0; int n,e; cin>>t; while(t--) { scanf("%d%d",&n,&e); vector< vector<int> >G(n); memset(visited,0,sizeof(visited)); for(i=0;i<e;i++) { scanf("%d%d",&x,&y); G[x].push_back(y); G[y].push_back(x); } int ans=0; for(i=0;i<n;i++) { if(!visited[i]) { q.push(i); visited[i]=1; cv[cvindex]++; while(!q.empty()) { int p=q.front(); q.pop(); for(j=0;j<G[p].size();j++) { if(!visited[G[p][j]]) { visited[G[p][j]]=1; q.push(G[p][j]); cv[cvindex]++; } } } ans++; cvindex++; } } printf("%d\n",ans); sort(cv,cv+cvindex); for(int zz=0;zz<cvindex;zz++) printf("%d ",cv[zz]); } } 

Time complexity O (n * m)

But how to approach the above problem without speculating? I want an almost similar approach with a few changes.

Other algorithms are welcome.

Also, is there a better algorithm in terms of time complexity?

Answer 1

This is my working code. I also commented on each step for your understanding. If you still find some help, you may ask.

Algorithm

• The first store index in accordance with their heights.
• Then iterate from minimum height to largest.
• If the current index has not yet been visited, make it the surface of the pool (where water can collect) and make all the neighbors whose height is greater than the surface of the non-pool.
• Repeat step 3 until all indexes are visited.
• Then, after changing the states of each index. We need to find the largest pool surface. This can be found using DFS.

Difficulty of time: O (ROWS * COLUMNS)

 #include<iostream> #include<vector> #include<string.h> #include<climits> #define BASIN 1 #define NOT_BASIN 2 #define NOT_DEFINED_YET 3 #define ROW 1000 #define COLUMN 1000 #define MAXIMUM_HEIGHT_POSSIBLE 1000 using namespace std; int heights[ROW][COLUMN]; // It stores the height int maximumBasin[ROW][COLUMN]; // It stores the state of each index, Total 3 states possible, ( BASIN, NOT_BASIN, NOT_DEFINED_YET ) bool alreadyVisited[ROW][COLUMN]; // True, if currect index visited, otherwise false. vector< pair<int, int> > heightsCoordinates[MAXIMUM_HEIGHT_POSSIBLE]; // It stores all the indexs of given height. int N, M, maxHeightPossible; int dx[] = {0, 1, 1, 1, 0, -1, -1, -1}; int dy[] = {1, 1, 0, -1, -1, -1, 0, 1}; bool isValidLocation(int x, int y) { if(x < 0 || x > M || y < 0 || y > N || alreadyVisited[x][y] == true) return false; return true; } void DFS_FOR_MARKING_WITH_GIVEN_VALUE(int value, int x, int y) { maximumBasin[x][y] = value; alreadyVisited[x][y] = true; for(int i = 0; i < 8; i++) if( isValidLocation(x + dx[i], y + dy[i]) && heights[x + dx[i]][y + dy[i]] >= heights[x][y] ) DFS_FOR_MARKING_WITH_GIVEN_VALUE(value, x + dx[i], y + dy[i]); } void DFS_FOR_COUNTING_BASINS_TOGETHER(int &cnt, int x, int y) { cnt++; alreadyVisited[x][y] = true; for(int i = 0; i < 8; i++) if( isValidLocation(x+dx[i], y+dy[i]) && maximumBasin[x + dx[i]][y + dy[i]] == BASIN ) DFS_FOR_COUNTING_BASINS_TOGETHER(cnt, x + dx[i], y + dy[i]); } void printBasin() { for(int i = 0; i < M; i++) { for(int j = 0; j < N; j++) cout << maximumBasin[i][j] << " "; cout << endl; } } main() { cin >> M >> N >> maxHeightPossible; int x, y; int maximumCounts = INT_MIN; int cntTemp = 0; /** Take input and set NOT_DEFINED_YET for maximumBasin. **/ for(int i = 0; i < M; i++) { for(int j = 0; j < N; j++) { cin >> heights[i][j]; maximumBasin[i][j] = NOT_DEFINED_YET; heightsCoordinates[ heights[i][j] ].push_back(pair<int, int>(i, j)); } } /** Iterate from smallest to largest height. If current index is "NOT_DEFINED_YET" (means it is the candidate index where water can collect). Water will come here from all neighbourhood whose height is greater than this. For that I call DFS_FOR_MARKING_WITH_GIVEN_VALUE function. **/ for( int i = 0; i <= maxHeightPossible; i++ ){ if(heightsCoordinates[i].size() == 0) continue; for(int j = 0; j < heightsCoordinates[i].size(); j++) { x = heightsCoordinates[i][j].first; y = heightsCoordinates[i][j].second; if( maximumBasin[x][y] == NOT_DEFINED_YET ) { maximumBasin[x][y] = BASIN; alreadyVisited[x][y] = true; for(int k = 0; k < 8; k++) { if( isValidLocation( x + dx[k], y + dy[k] ) ) { if ( heights[x + dx[k]][ y + dy[k]] > heights[x][y] ) { DFS_FOR_MARKING_WITH_GIVEN_VALUE(NOT_BASIN, x + dx[k], y + dy[k]); } } } } else { // If it is set by BASIN or NOT_BASIN, Shows already processed before. } } } //printBasin(); memset(alreadyVisited, 0, sizeof(alreadyVisited)); /** It simply counts basins which are together. **/ for(int i = 0; i < M; i++) { for(int j = 0; j < N; j++) { if( alreadyVisited[i][j] == false && maximumBasin[i][j] == BASIN) { DFS_FOR_COUNTING_BASINS_TOGETHER(cntTemp, i, j); //cout << cntTemp << endl; if(cntTemp > maximumCounts ) maximumCounts = cntTemp; cntTemp = 0; } } } /** This is our final Answer. **/ cout << maximumCounts << endl; return 0; } 

Answer 2

Build a height chart as a graph where each of the elements in your 2d array is a node. In addition, there is a directional edge from node u to node v if the elevation of node u> = the elevation of node v. Build the SCC of this graph and select the largest component. This will be the pool you are looking for.

Answer 3

Watershed is the algorithm you are looking for, I think. It is mainly used for image segmentation, but it is based on finding pools in grayscale images, so I think this applies to your problem.

Answer 4

Algorithm

1- insert all the elements based on the heights in the priority queue (minimum heap) 2- remove the elements from the queue one by one until the queue becomes empty, and mark all the neighbors with a higher height as no pools. (Use the first crossing step to further designate neighboring neighbors with a height greater than the current neighbor as not a pool, and to continue removing elements from the queue) when the queue is empty, all non-pools are marked as non-pools.

 import java.util.Comparator; import java.util.PriorityQueue; /** * Created by dheeraj on 12/16/14. */ public class FindingBasin { int[][] matrix; int rows; int cols; PriorityQueue<RowColHeight> rowColHeightPriorityQueue; private static class RowColHeight { int row; int col; int height; public RowColHeight(int row, int col, int height) { this.row = row; this.col = col; this.height = height; } @Override public boolean equals(Object obj) { RowColHeight obj1 = (RowColHeight) obj; if(obj1.row == this.row && obj1.col == this.col){ return true; }else{ return false; } } } public FindingBasin(int[][] matrix) { this.matrix = matrix; this.rows = matrix.length; this.cols = matrix[0].length; } public void findBasin() { rowColHeightPriorityQueue = new PriorityQueue<RowColHeight>(rows * cols, new Comparator<RowColHeight>() { @Override public int compare(RowColHeight o1, RowColHeight o2) { return o1.height - o2.height; } }); // basin matrix -> true basin , false non basin boolean[][] basinMatrix = new boolean[rows][cols]; boolean[][] visitedMatrix = new boolean[rows][cols]; // sort matrix data on the basis of heights for (int x = 0; x < rows; x++) { for (int y = 0; y < cols; y++) { rowColHeightPriorityQueue.add(new RowColHeight(x, y, matrix[x][y])); basinMatrix[x][y] = true; visitedMatrix[x][y] = false; } } RowColHeight rowColHeight; while (!rowColHeightPriorityQueue.isEmpty()) { //find all non basins rowColHeight = rowColHeightPriorityQueue.remove(); for (int x = Math.max(0, rowColHeight.row - 1); x < Math.min(rows, rowColHeight.row + 2); x++) { for (int y = Math.max(0, rowColHeight.col - 1); y < Math.min(cols, rowColHeight.col + 2); y++) { if (x == rowColHeight.row && y == rowColHeight.col) { continue; } if (visitedMatrix[x][y]) { continue; } else { visitedMatrix[x][y] = true; } if (matrix[x][y] > rowColHeight.height) { basinMatrix[x][y] = false; //matrix[x][y] is non basin so all its neighbours >= it are also non basins markALlNonBasins(rowColHeightPriorityQueue,visitedMatrix,basinMatrix,x,y); } } } } for (int x = 0; x < rows; x++) { for (int y = 0; y < cols; y++) { System.out.print(basinMatrix[x][y] + " "); } System.out.println(); } } private void markALlNonBasins(PriorityQueue<RowColHeight> rowColHeightPriorityQueue,boolean[][] visitedMatrix,boolean[][] basinMatrix,int row,int column) { for (int x = Math.max(0,row - 1); x < Math.min(rows,row + 2); x++) { for (int y = Math.max(0,column - 1); y < Math.min(cols,column + 2); y++) { if (x == row && y == column) { continue; } if(visitedMatrix[x][y]){ continue; } if(matrix[x][y] >= matrix[row][column]){ visitedMatrix[x][y] = true; basinMatrix[x][y] =false; rowColHeightPriorityQueue.remove(new RowColHeight(x,y,matrix[x][y])); markALlNonBasins(rowColHeightPriorityQueue,visitedMatrix,basinMatrix,x,y); } } } } public static void main(String[] args) { int[][] matrix = { {9, 9, 9, 8, 7, 7}, {8, 8, 7, 7, 7, 8}, {8, 8, 8, 7, 7, 7}, {8, 8, 8, 9, 9, 9}, {8, 8, 8, 7, 7, 7}, {4, 4, 5, 5, 5, 5}, {5, 5, 5, 6, 6, 7}, {5, 5, 5, 8, 8, 6} }; FindingBasin findingBasin = new FindingBasin(matrix); findingBasin.findBasin(); } }