runtime error for algorithm of surrounded region

Question

I come up with an algorithm to solve surrounded region problem posted at leetcode.

But the sad thing is my solution can pass with first judge input sets, but can not pass with the second larger input sets, and it reports run time error. However, I can run successfully on my laptop! I have spent hours on this problem, but I still have no idea!

Below is the problem.

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region .

For example,

X X X X

X O O X

X X O X

X O X X

After running your function, the board should be:

X X X X

X X X X

X X X X

X O X X

Below is my solution:

class Solution {
public:
    void solve(vector<vector<char> > &board) {
      if(board.size() == 0) return;

      int row = board.size();
      set<pair<int, int> > map;

      for(int i=0; i<= row/2; i++){
         int bottom = row-i-1;
         for(int j=i; j<= bottom; j++){
            checkPoint(board, i, j, map);
            checkPoint(board, bottom, j, map);
            checkPoint(board, j, i, map);
            checkPoint(board, j, bottom, map);
         }
      }        
   }

  void mark(vector<vector<char> >& board, int row, int col, set<pair<int, int> >& map){
      if(row < 0 || row > board.size()-1 || col < 0 || col > board[0].size()-1 )
          return;

    int temp = col;
    while(temp-1 >= 0 && board[row][temp-1] == 'O' &&\
        map.find(pair<int,int>(row, temp-1)) ==   map.end()){
        map.insert(pair<int, int>(row, temp-1));
        temp -=1;
        mark(board, row, temp, map);
    }
    temp = col;
    while(temp+1 <= board[0].size()-1 && board[row][temp+1] == 'O' && \
        map.find(pair<int,int>(row, temp+1)) == map.end()){
        map.insert(pair<int, int>(row, temp+1));
        temp +=1;
        mark(board, row, temp, map);
    }
    temp = row;
    while(temp -1 >= 0 && board[temp-1][col] == 'O'&& \
         map.find(pair<int,int>(temp-1, col)) == map.end()){
        map.insert(pair<int, int>(temp-1, col));
        temp -=1;
        mark(board, temp, col, map);
    }
    temp = row;
    while(temp+1 <= board.size()-1 && board[temp+1][col] == 'O'&& \
         map.find(pair<int,int>(temp+1, col)) == map.end()){
        map.insert(pair<int, int>(temp+1, col));
        temp +=1;
        mark(board, temp, col, map);
    }          
 }

  void checkPoint(vector<vector<char> >& board, int row, int col, set<pair<int, int> >& map){
     if(board[row][col] == 'O'){
       if(row ==0 || col== 0 || row == board.size()-1 || col == board[0].size()-1 ){
           if(map.find(pair<int, int>(row, col)) == map.end()){
               map.insert(pair<int,int>(row, col));
               mark(board, row, col, map);
           }
       }else if(map.find(pair<int, int>(row, col)) == map.end()){
              board[row][col] = 'X';
      }
    }
    return;
  }

};

Answer 1

I agree with one of the other answers, either you are using too much run time or stack space. Try this idea. Note that for a connected region of 'O', either the region touches the edge of the board, or the region is completely surrounded by 'X'. So you can use the following strategy. First go along the edges of the board until you find an 'O'. Then initialize a set CurrentBoundaryO to be equal to the set of just this one 'O', and initialize a set NextBoundaryO to be empty. Then iteratively do the following. Mark every location in CurrentBoundaryO to be 'unchanged O'. Then iterate through the elements of CurrentBoundaryO and check all neighbors. Every neighbor that is 'O' that is not marked 'unchanged O' should be added to the set NextBoundaryO. Then set CurrentBoundaryO = NextBoundaryO and repeat, until CurrentBoundryO has no elements. Then continue searching around the edges of the board, until you find a 'O' that is not marked 'unchanged O', and repeat the process. Keep repeating until you have traveled along the entire edges of the board. Then every 'X' is still an 'X', every 'O' marked 'unchanged O' is still a 'O', and all other 'O' on the board should be switched to 'X'. This strategy runs in linear time in terms of the input size, and it avoids recursion so there is no stack space issue either. This should pass the judge software evaluation.

Answer 2

In general online judges run on a completely different environment than the one on your desktop. The servers use commodity hardware, which mean cpu can be slow and memory small. Nothing prevent your code to be ran in a thread. Moreover you don't have control on level of optimization and compiler used.

The error is probably due to the recursive nature of the mark function. The runtime error imho is either or both due to an overflow of the stack or the program being killed because it took too much time to complete.

The function mark is pretty unintuitive and costly. First it is recursive with the maximum depth linear to the dimensions of the board. If the board has 1 million rows we will have

mark(1000000,...)   
  mark(1000000-1,...)
    ...
      mark(1,...) 
        mark(0,...)

The stack may not be big enough.

Secondly each time you call mark each of the cell in the same row or column with be "visited" (map.find(pair<int,int>(x, y)) == map.end()) several more times than needed. Let say the grid is nxn. If you call mark(x,y) the test above will be done n times for each of the positions on the row x and on the row y. Which means the complexity of mark is O(n^2). In general, it is O(#row^2 + #columns^2)

Then you have :

 for(int i=0; i<= row/2; i++){
     int bottom = row-i-1;
     for(int j=i; j<= bottom; j++){
        checkPoint(board, i, j, map);         <--O(n^2)
        checkPoint(board, bottom, j, map);    <--O(n^2)
        checkPoint(board, j, i, map);         <--O(n^2)
        checkPoint(board, j, bottom, map);    <--O(n^2)
     }
  }

Your code has a worst running time of O(n^4) where n = max(row, cols).

ps: How do i come up with the complexity of mark?

mark(x,y) with board[row][y-1] = 'O' lead to

  mark(x,y-1)
  mark(x,y-2)
  ...
  mark(x,0)

in each of the mark the complete row is tested again. which make n calls to the function map.find(pair<int,int>(A, B)). Thus an n^2 complexity.