Why do I get a stackoverflow on the largest input? How can I improve my code?


  • 1
    K
    public class Solution {
        public void solve(char[][] board) {
            if (board == null || board.length == 0){
                return;
            }
            int width = board.length;
            int height = board[0].length;
            boolean[][] visited = new boolean[width][height];
    
            for (int i = 0; i < width; i++){
                if (board[i][0] == 'O' && !visited[i][0]){
                    dfs(board, visited, i, 0);
                }
                if (board[i][height - 1] == 'O' && !visited[i][height - 1]){
                    dfs(board, visited, i, height - 1);
                }
            }
            
            for (int i = 0; i < height; i++){
                if (board[0][i] == 'O' && !visited[0][i]){
                    dfs(board, visited, 0, i);
                }
                if (board[width - 1][i] == 'O' && !visited[width - 1][i]){
                    dfs(board, visited, width - 1, i);
                }
            }
            
            for (int i = 0; i < width; i++){
                for (int j = 0; j < height; j++){
                    if (board[i][j] == 'O' && !visited[i][j]){
                        board[i][j] = 'X';
                    }
                }
            }
        }
        
        public void dfs(char[][] board, boolean[][] visited, int i, int j){
            if (i < 0 || j < 0 ||i >= board.length || j >= board[0].length || visited[i][j] || board[i][j] == 'X'){
                return;
            }
            visited[i][j] = true;
            dfs(board, visited, i + 1, j);
            dfs(board, visited, i - 1, j);
            dfs(board, visited, i, j + 1);
            dfs(board, visited, i, j - 1);
        }
    }
    

  • 0

    @kevzsolo Your solution is right but check this or this.


  • 0
    K

    So the only difference I can see is:

    // the next four lines are cases where the cell is at the edge, 
                // in these cases we only need to check one direction, 
                // "in-bound" direction, to avoid unnecessary calls to dfs()
                if(i == 0) dfs(i+1, j, board);
                else if (j == 0) dfs(i, j+1, board);
                else if(i == board.length-1) dfs(i-1, j, board);
                else if(j == board[i].length-1) dfs(i, j-1, board);
    

    That eliminates the extra method calls for cases that are out of bounds I think. But does that make a big difference?


  • 0

    @kevzsolo It does in this problem in OJ, which also bothers for long @contributors @administrators perhaps we should call up these guys altogether to help us out. Haha...


  • 0

    @kevzsolo said in Why do I get a stackoverflow on the largest input? How can I improve my code?:

    That eliminates the extra method calls for cases that are out of bounds I think.

    Nah, it doesn't just prevent out-of-bounds calls.

    When your submission fails, the system tells you the input you failed. Look at that input. You should be able to see why your way fails it and the other way doesn't (And maybe also why the other way is pretty much cheating, doesn't really solve the issue).


  • 0
    K

    @StefanPochmann It passes on 57/58 cases. The only case it fails on is the one with the largest input. And the result is stackoverflow.


  • 0

    @kevzsolo Go on...


  • 0

    @StefanPochmann Still not solve this problem, to my knowledge. I mean since the solutions similar to the following already labelled the boundary cells, there is no way to over-cross them stack over flow should not happen. There are bunches of people failed on this point and till now, nothing constructive has been proposed. @StefanPochmann @contributors @administrators No one can have a clear point on this?

    class Solution {
    private:
        int rowSize, colSize;
        void fill_up(vector<vector<char>>& board, int r, int c)
        {
            if(r==-1 || c==-1 || r==rowSize || c==colSize || board[r][c]!='O') return ;
            board[r][c] = 'a';
            fill_up(board, r-1, c);
            fill_up(board, r+1, c);
            fill_up(board, r, c-1);
            fill_up(board, r, c+1);
        }
    public:
        void solve(vector<vector<char>>& board) 
        {
            rowSize = board.size();
            if(!rowSize) return ;
            colSize = board[0].size();
            for(int r = 0; r < rowSize; ++r)
                for(int c = 0;  c < colSize; ++c)
                    if((r==0 || c==0 || r==rowSize-1 || c==colSize-1) && board[r][c]=='O')
                        fill_up(board, r, c);
            for(int r = 0; r < rowSize; ++r)
                for(int c = 0;  c < colSize; ++c)
                {
                    if(board[r][c] == 'a') board[r][c] = 'O';
                    else board[r][c] = 'X';
                }
        }
    };
    

  • 2

    @LHearen said in Why do I get a stackoverflow on the largest input? How can I improve my code?:

    nothing constructive has been proposed

    Hmm, I do think it was constructive when I told you to look at the failed test case and understand why you fail it (and why that other solution doesn't). I don't believe that "It's big" is honestly the best analysis of the test case that you two can offer.

    The test case you fail looks as follows, only bigger (and I changed O to . for easy viewing):

    ..........................
    XXXXXXXXXXXXXXXXXXXXXXXXX.
    ..........................
    .XXXXXXXXXXXXXXXXXXXXXXXXX
    ..........................
    XXXXXXXXXXXXXXXXXXXXXXXXX.
    ..........................
    .XXXXXXXXXXXXXXXXXXXXXXXXX
    ..........................
    XXXXXXXXXXXXXXXXXXXXXXXXX.
    ..........................
    .XXXXXXXXXXXXXXXXXXXXXXXXX
    ..........................
    XXXXXXXXXXXXXXXXXXXXXXXXX.
    

    So when you call dfs(0, 0), you'll immediately run that entire zig-zag path all the way through the whole board. That's half of all cells, 31375 cells for the actual test case. Very deep recursion, hence your stack overflow problem. So you can't do that. Do it iteratively instead.

    That other solution, which from edges only goes "in-bound", doesn't just prevent going out-of-bounds with that. For the zig-zag example, that "in-bound" behaviour also leads to dfs(0, 0) going pretty much nowhere. And then dfs(0, 1), dfs(0, 2), etc also go pretty much nowhere. The first time it goes a little deep is when it reaches the third row, and then it only goes that one row to the right. Not very deep.

    Though like I said, that doesn't really solve the issue. It's just a dirty fix for that particular test case. All you have to do to make it fail is add an additional X-column left and right, like:

    X..........................X
    XXXXXXXXXXXXXXXXXXXXXXXXXX.X
    X..........................X
    X.XXXXXXXXXXXXXXXXXXXXXXXXXX
    X..........................X
    XXXXXXXXXXXXXXXXXXXXXXXXXX.X
    X..........................X
    X.XXXXXXXXXXXXXXXXXXXXXXXXXX
    X..........................X
    XXXXXXXXXXXXXXXXXXXXXXXXXX.X
    X..........................X
    X.XXXXXXXXXXXXXXXXXXXXXXXXXX
    X..........................X
    XXXXXXXXXXXXXXXXXXXXXXXXXX.X
    

  • 0

    @StefanPochmann

    Big Boss, you are here too rude. You really thought I have not thought about it? It's been long since I encountered this but it just struck me.

    But as you pointed it out, I think I now truly get it. Thanks!


    The truth here is that traversing done by recursive is okay but it's time-consuming as the invoking levels go deep, which can actually be replaced by the linear traversing at the very beginning two-level loops to avoid that deep invoking (which is the devil that causes so much trouble).


    That is the key point. Finally it's clear now. Thank you again @StefanPochmann, though you are kind of aggressive back then.


  • 1

    Yeah, sorry, I edited and toned it down now. I tend to get cranky when people disappoint me, plus I didn't appreciate the "nothing constructive has been proposed" and you two apparently not really looking at the failed case and thinking it through. At the very least I would've expected you two to look at the test case and tell us what it's like, either in words or by showing a smaller version. It would've been helpful for everybody, and it would've demonstrated that you did look into it. I don't think it should've been me who did that.

    This is also a general pet peeve of mine that has been building up more and more, I don't understand why so many people ask for help and then only dump their solution but don't show the test case they failed, as if that couldn't possibly help. Many don't even say what the problem is (Wrong Answer, Runtime Error or so) but just ask "What's wrong with this?". I find that rather rude, too. They want others to spend time helping them, but can't be bothered to provide the available information?


  • 0

    @StefanPochmann You're right, man. I think I can do better next time. Thank you again for helping me out again. It's quite awesome for your being here showing us the direction.


  • 0

    @LHearen said in Why do I get a stackoverflow on the largest input? How can I improve my code?:

    The truth here is that traversing done by recursive is okay but it's time-consuming

    I don't think time consumption is any problem here.

    can actually be replaced by the linear traversing at the very beginning two-level loops to avoid that deep invoking

    I don't understand what you mean here, can you explain more or show it as code?


  • 0

    @StefanPochmann time-consuming here refers to your too deep recursive invoking.

    The code enclosed below is the correct one which will label the boundary in the first level of the traverse recursive invoking and then within the traverse the traversing range of the board manually exclude the boundary (which will be handled int the first time the traverse invoked in the two-level loop) which is the way to avoid too deep searching, I think is that you mentioned before.

    class Solution {
    private:
        int rowSize, colSize;
        void traverse(vector<vector<char>>& board, int r, int c)
        {
            if(board[r][c]=='a' || board[r][c]=='X') return ;
            board[r][c] = 'a';
            if(r > 1) traverse(board, r-1, c);
            if(c > 1) traverse(board, r, c-1);
            if(r < rowSize-2) traverse(board, r+1, c);
            if(c < colSize-2) traverse(board, r, c+1);
        }
    public:
        void solve(vector<vector<char>>& board) 
        {
            if(board.empty()) return ;
            rowSize = board.size(), colSize = board[0].size();
            for(int r = 0; r < rowSize; ++r)
                for(int c = 0; c < colSize; ++c)
                    if((r==0 || c==0 || r==rowSize-1 || c==colSize-1) && board[r][c]=='O')
                        traverse(board, r, c);
            for(int r = 0; r < rowSize; ++r)
                for(int c = 0; c < colSize; ++c)
                    board[r][c] = (board[r][c]=='a')? 'O' : 'X';
        }
    };
    

  • 0

    @StefanPochmann Besides I count that redundancy before, it's about five times than the current excluding version.


  • 0

    @LHearen said in Why do I get a stackoverflow on the largest input? How can I improve my code?:

    @StefanPochmann time-consuming here refers to your too deep recursive invoking.

    But the recursion being too deep has absolutely nothing to do with time. It's purely a space issue.

    The code enclosed below is the correct one

    Well, "correct" in the same sense that that "only in-bound" solution is "correct". That is, it gets accepted by the OJ. Because it has a dirty fix for that particular test case in the OJ's test suite. It doesn't really solve the problem.

    Besides I count that redundancy before, it's about five times than the current excluding version.

    I don't understand, I think there's at least one missing word and one wrong word.


  • 0
    M

    void dfs(char[][] board, int i , int j){

        if(board[i][j]=='O'){
            board[i][j]='1';
            //In order to decrease the recursion times, 
            //we don't need to check the outside boarder. 
            //So i>1,j>1,i+2<board.size(),and j+2<board[0].size().
            //This platform has a limited stack storage.
            
            if(i>1) dfs(board,i-1,j);
            if(j>1) dfs(board,i,j-1);
            if(i<board.length-2)dfs(board,i+1,j);
            if(j<board[0].length-2)dfs(board,i,j+1);
        }
        return;
    }

  • 0

    @Mick It's because we're going to traverse them in the two-level loop which will be linear

    for(int r = 0; r < rowSize; ++r)
                for(int c = 0; c < colSize; ++c)
                    if((r==0 || c==0 || r==rowSize-1 || c==colSize-1) && board[r][c]=='O')
                        traverse(board, r, c);
    

    instead of too many recursive invokings which will cause deep recursion problem


Log in to reply
 

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