Given a 2D matrix where each element represents the elevation(height) on that point, find how many rain water it is able to hold.(Twitter interview question)
For example, given the below 3×3 matrix:
3 3 3
3 0 3
3 3 3
3 3 3
3 0 3
3 3 3
It should hold 3 units of rain water.
I wrote a code for that and I think It works. I tested it against various inputs and got right answer. Please let me know if something appears wrong.
here is my code :
#pragma once #include <iostream> #include <vector> using namespace std; vector<vector<int> > Visited; int HowMuchCanHold(vector<vector<int> > &M,int i,int j) { Visited[i][j]=1; if(i==0 || j==0 || i==M.size()-1 || j==M[0].size()-1) // we are in borders return -1; // drops to earth int up=M[i-1][j],down=M[i+1][j],left=M[i][j-1],right=M[i][j+1]; int minall=1<<10; if(!Visited[i-1][j]) minall=min(minall,up); if(!Visited[i+1][j]) minall=min(minall,down); if(!Visited[i][j-1]) minall=min(minall,left); if(!Visited[i][j+1]) minall=min(minall,right); int mij=M[i][j]; if(minall>mij) return minall-mij; else if(minall<mij) return -1; // can't hold the drop int minup=1<<10,mindown=1<<10,minleft=1<<10,minright=1<<10; if(mij==up && Visited[i-1][j]==0) // drop may flow up minup=HowMuchCanHold(M,i-1,j); else if(mij!=up) minup=up-mij; if(mij==down && Visited[i+1][j]==0) // drop may flow down mindown=HowMuchCanHold(M,i+1,j); else if(mij!=down) mindown=down-mij; if(mij==left && Visited[i][j-1]==0) // drop may flow left minleft=HowMuchCanHold(M,i,j-1); else if(mij!=left) minleft=left-mij; if(mij==right && Visited[i][j+1]==0) // drop may flow right minright=HowMuchCanHold(M,i,j+1); else if(mij!=right) minright=right-mij; if(minup<0 || mindown<0 || minleft<0 || minright <0) // drop wil fall from up,down,left or right! return -1; // can't hold the drop int min1=min(minup,mindown); int min2=min(minleft,minright); minall=min(min1,min2); return minall; } int DropTo(vector<vector<int> > &M,int i,int j) { Visited=vector<vector<int> >(M.size(), vector<int>(M[0].size(),0)); return HowMuchCanHold(M,i,j); } int get_watr_trap(vector<vector<int> > M) { int row=M.size(); int col=M[0].size(); int total=0; int nexthold=0; bool find=false; while(1) { find=false; for(int i=0;i<row;i++) { for(int j=0;j<col;j++) { nexthold=DropTo(M,i,j); if(nexthold>0) { find=true; M[i][j]+=nexthold;//fill current cell up to the maxhold total+=nexthold; } } } if(!find) break; } return total; } void test_water_trap() { vector<vector<int> > M(4, vector<int>(4,10)); M[1][1]=0; M[1][2]=2; M[2][1]=4; M[2][2]=8; M[3][0]=2; M[3][2]=8; int water_trapped=get_watr_trap(M); cout << water_trapped << endl; }
could u explain your algorithm!?
ReplyDeletewhich part is unclear?
ReplyDeletehave you looked at inline comments?
Can you explain your time and space complexity? Thank you!
ReplyDeleteSuppose Matrix is M*N. and let D=Max( elements ) - Min ( elements )
Deletespace complexity is M*N and time complexity seems to be M*N*D
Hi elios !
ReplyDeleteyour code is for 1 dimensional problem!