# Straightforward efficient C++ solution using stack

• The code is rather long, but very easy to understand.
Basically, we use two tables to record if the water can flow to pacific or atlantic. To determine the element, we use a stack structure to search the element on the four sides of a certain element.
In the test the runtime is 55ms.

``````class Solution {
public:
vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
vector<pair<int,int>> result;
int m=matrix.size();
if (m==0) return result;
int n=matrix[0].size();
int pacific[m][n];
int atlantic[m][n];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
pacific[i][j]=0;
atlantic[i][j]=0;
}
}
stack<pair<int,int>> sp;
stack<pair<int,int>> sa;
for (int i=0;i<m;i++){
pacific[i][0]=1;
sp.push(make_pair(i,0));
}
for(int i=1;i<n;i++){
pacific[0][i]=1;
sp.push(make_pair(0,i));
}
while(!sp.empty()){
pair<int, int> index=sp.top();
int x=index.first;
int y=index.second;
sp.pop();
if (x-1>=0&&pacific[x-1][y]==0&&matrix[x-1][y]>=matrix[x][y]){
sp.push(make_pair(x-1,y));
pacific[x-1][y]=1;
}
if (x+1<m&&pacific[x+1][y]==0&&matrix[x+1][y]>=matrix[x][y]){
sp.push(make_pair(x+1,y));
pacific[x+1][y]=1;
}
if (y-1>=0&&pacific[x][y-1]==0&&matrix[x][y-1]>=matrix[x][y]){
sp.push(make_pair(x,y-1));
pacific[x][y-1]=1;
}
if (y+1<n&&pacific[x][y+1]==0&&matrix[x][y+1]>=matrix[x][y]){
sp.push(make_pair(x,y+1));
pacific[x][y+1]=1;
}
}
for (int i=0;i<m;i++){
atlantic[i][n-1]=1;
sa.push(make_pair(i,n-1));
}
for(int i=0;i<n-1;i++){
atlantic[m-1][i]=1;
sa.push(make_pair(m-1,i));
}
while(!sa.empty()){
pair<int, int> index=sa.top();
int x=index.first;
int y=index.second;
sa.pop();
if (x-1>=0&&atlantic[x-1][y]==0&&matrix[x-1][y]>=matrix[x][y]){
sa.push(make_pair(x-1,y));
atlantic[x-1][y]=1;
}
if (x+1<m&&atlantic[x+1][y]==0&&matrix[x+1][y]>=matrix[x][y]){
sa.push(make_pair(x+1,y));
atlantic[x+1][y]=1;
}
if (y-1>=0&&atlantic[x][y-1]==0&&matrix[x][y-1]>=matrix[x][y]){
sa.push(make_pair(x,y-1));
atlantic[x][y-1]=1;
}
if (y+1<n&&atlantic[x][y+1]==0&&matrix[x][y+1]>=matrix[x][y]){
sa.push(make_pair(x,y+1));
atlantic[x][y+1]=1;
}
}
for(int i=0; i<m;i++){
for(int j=0;j<n;j++){
if (atlantic[i][j]==1&&pacific[i][j]==1){
result.push_back(make_pair(i,j));
}
}
}
return result;
}
};

``````

• @liyouvane Thank you so much for your solution..

• @liyouvane Thanks for sharing. I changed the coding style.

``````class Solution {
public:
vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
vector<pair<int,int>> res;
if (matrix.empty()) return res;
int m = matrix.size(), n = matrix[0].size();
vector<vector<bool>> p(m, vector<bool>(n, false));
vector<vector<bool>> a(m, vector<bool>(n, false));
stack<pair<int, int>> sp;
stack<pair<int, int>> sa;
for (int i = 0; i < m; i++)
{
p[i][0] = true;
sp.push(make_pair(i, 0));

a[i][n-1] = true;
sa.push(make_pair(i, n-1));
}
for(int j = 0; j < n; j++)
{
p[0][j] = true;
sp.push(make_pair(0, j));

a[m-1][j] = true;
sa.push(make_pair(m-1, j));
}
int dir[5] = {0, 1, 0, -1, 0};
while(!sp.empty())
{
auto ij = sp.top(); sp.pop();
int i = ij.first, j = ij.second;
for (int d = 0; d < 4; d++)
{
int x = i + dir[d], y = j + dir[d+1];
if (x >= 0 && x < m && y >= 0 && y < n)
{
if (!p[x][y] && matrix[x][y] >= matrix[i][j])
{
sp.push(make_pair(x, y));
p[x][y] = true;
}
}
}
}
while(!sa.empty())
{
auto ij = sa.top(); sa.pop();
int i = ij.first, j = ij.second;
for (int d = 0; d < 4; d++)
{
int x = i + dir[d], y = j + dir[d+1];
if (x >= 0 && x < m && y >= 0 && y < n)
{
if (!a[x][y] && matrix[x][y] >= matrix[i][j])
{
sa.push(make_pair(x, y));
a[x][y] = true;
}
}
}
}
for(int i = 0; i < m; i++)
{
for(int j = 0; j < n; j++)
{
if (p[i][j] && a[i][j])
{
res.push_back(make_pair(i, j));
}
}
}
return res;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.