DFS with cyclic dependency

Question

I was attempting to solve this challenge

Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the "Pacific ocean" touches the left and top edges of the matrix and the "Atlantic ocean" touches the right and bottom edges.

Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.

Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.

Note: The order of returned grid coordinates does not matter. Both m and n are less than 150.

Example:

 Given the following 5x5 matrix:

   Pacific ~   ~   ~   ~   ~ 
        ~  1   2   2   3  (5) *
        ~  3   2   3  (4) (4) *
        ~  2   4  (5)  3   1  *
        ~ (6) (7)  1   4   5  *
        ~ (5)  1   1   2   4  *
           *   *   *   *   * Atlantic

 Return:

 [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions
 with parentheses in above matrix).

And this is my solution

class Solution {
public:
    vector<pair<int, int>> result;
    map<pair<int, int>, pair<bool, bool>> dp;
    //    P     A
    pair<bool, bool> doPacific(vector<vector<int>>& matrix, vector<vector<bool>> & visited,  int row, int col)
    {
        cout << row << ' ' << col << endl;
        if(col < 0 || row < 0)
        {
            return pair<bool, bool>(true, false);
        }
        if(col >= matrix[0].size() || row >= matrix.size())
        {
            return pair<bool, bool>(false, true);
        }
        if(visited[row][col])
        {
            return dp[make_pair(row, col)];
        }
        pair<bool,bool> left(false, false);
        pair<bool,bool> right(false, false);
        pair<bool,bool> top(false, false);
        pair<bool,bool> bottom(false, false);
        visited[row][col] = true;
    // Go Down if index is invalid or has valid index and water level
    if(((row + 1 < matrix.size()) && (matrix[row + 1][col] <= matrix[row][col])) || row + 1 >= matrix.size())
    {
        bottom = doPacific(matrix,visited, row + 1, col);
    }
    if(((row - 1 >= 0) && (matrix[row - 1][col] <= matrix[row][col])) || (row -1 < 0))
    {
            top = doPacific(matrix,visited, row - 1, col);
    }
    if(((col + 1 < matrix[0].size()) && (matrix[row][col + 1] <= matrix[row][col])) || (col + 1>= matrix[0].size()))    
    {
            right = doPacific(matrix,visited, row, col + 1);
    }
    if(((col - 1 >=0) && (matrix[row][col - 1] <= matrix[row][col])) || (col -1 < 0))
    {
        left = doPacific(matrix,visited, row, col - 1);
    }

        pair<bool, bool>returnValue(false, false);

        returnValue.first |= left.first;
        returnValue.second |= left.second;

        returnValue.first |= right.first;
        returnValue.second |= right.second;

        returnValue.first |= bottom.first;
        returnValue.second |= bottom.second;

        returnValue.first |= top.first;
        returnValue.second |= top.second;

        dp.insert(make_pair(make_pair(row, col), returnValue));
        if(returnValue.first && returnValue.second)
        {
            result.push_back(make_pair(row, col));
        }
        return returnValue;

    }
    vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
        vector<vector<bool>> visited(matrix.size(), vector<bool>(matrix[0].size(), false));
        result.clear();
        dp.clear();
        for(int i=0; i< matrix.size(); ++i)
        {
            for(int j=0; j < matrix[0].size(); ++j)
            {
                if(!visited[i][j])
                {
                    doPacific(matrix, visited, i, j); 
                }                
            }
        }
        return result;
    }
};

But my solution failed for input

[10,10,10]
[10, 1,10]
[10,10,10]

My answer only omitted the index (0,1).

When I traced the recursion tree it looked something like this.

                    (0, 0)
                     /
                  (1,0)
                   /
               (2, 0)
                 /   \
            (2, 1)  (2, 2)
               /      /
         (T,F)/    (1,2)
          (1, 1)     /
                  (0,2)
                    /
                 (0,1) This return(T,F) when it should return (T,T).
                       Because (0,1) won't call (0,0) since it is 
                       already being processed(i.e visited) which in turn depends on (0,1), 
                       creating a cycle. Although there exists a path 
                       from (0,0) to atlantic

My question is how do I solve such a situation when there is a cyclic dependency between the existing node and the node to be added.

Is the approach to such problem incorrect.

Answer 1

You have multiple problems in your implementation:

1. you only consider two states for a node: not visited and visited. But you can indeed fall in a third state. Usually we consider the colors white, gray and black. In your code the gray and black colors are merged together in a single visited state.
2. when entering a new node, if you marked the node as visited you don't visit it again but just lookup its value in your dp array. As you found yourself, it doesn't work because the dp array is correct only for black cells, not for graycells. But because of problem 1. you cannot make the difference

The reason why your dp array is not correctly updated for gray cells is that you try to do two things at the same time:

1. compute if a cell is touched by Pacific
2. compute if a cell is touched by Atlantic

But with a single DFS you can update one property on the forward path, and the second only on the backward path of your traversal.

A solution is to update each property separately with two DFS.

Instead of a single DFS you could try to do two flood-fill starting from one ocean then the second. Each flood-fill is a DFS but from a different source, and upating a different visited property. Obviously, you reverse the condition for the flow, that is your water flows from lower to upper elevation.

After the two flood-fills you eventually output all cells touched by both oceans. Flood-fill is O(n*m) so it doesn't degrade the complexity compared to your current implementation.

In my implementation I start n+m flood fills for each ocean, but I keep the same visiteds maps, so it still remains in O(n*m)

Here is an example solution (readable but still faster than 91% of c++ submission). See that I use a bitmasking technique to mark the cells visited by oceans (1 -> pacific, 2 -> atlantic, 3 -> both) instead of a pair<bool,bool> but this is just for performance optimisation.

int width, height;
vector<vector<unsigned char>> visiteds;

void floodFill(int i, int j, unsigned char mask, vector<vector<int>>& matrix) {
    visiteds[i][j] = visiteds[i][j] | mask;

    auto& h = matrix[i][j];

    if(i > 0 && matrix[i-1][j] >= h && !(visiteds[i-1][j] & mask))
        floodFill(i-1, j, mask, matrix);

    if(i < height-1 && matrix[i+1][j] >= h && !(visiteds[i+1][j] & mask))
        floodFill(i+1, j, mask, matrix);

    if(j > 0 && matrix[i][j-1] >= h && !(visiteds[i][j-1] & mask))
        floodFill(i, j-1, mask, matrix);

    if(j < width-1 && matrix[i][j+1] >= h && !(visiteds[i][j+1] & mask))
        floodFill(i, j+1, mask, matrix);
}

vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
    vector<pair<int,int>> cells;
    height = matrix.size();
    if(! height)
        return cells;

    width = matrix[0].size();
    visiteds.clear();
    visiteds.resize(height, vector<unsigned char>(width, 0));

    for(int k=0; k<height; ++k) {
        floodFill(k, 0, 1, matrix);
        floodFill(k, width-1, 2, matrix);
    }
    for(int k=0; k<width; ++k) {
        floodFill(0, k, 1, matrix);
        floodFill(height-1, k, 2, matrix);
    }

    for(size_t i=0; i<height; ++i)
        for(size_t j=0; j<width; ++j)
            if(visiteds[i][j] == 3)
                cells.push_back(make_pair(i, j));
    return cells;
}