Help solving TLE problem


  • 0
    J

    Can anybody see why below code get TLE? Thanks.

    {
    public class Solution {
    class Coord
    {
    public int x;
    public int y;
    public Coord(int x, int y)
    {
    this.x = x;
    this.y = y;
    }
    }

    HashSet<Coord> visitedCoord = new HashSet<Coord>();
    
    public void solve(char[][] board) {
        if(board==null) return;
        
        for(int i=1;i<board.length-1;++i)
        {
            for(int j=1;j<board[0].length-1;++j)
            {
                Coord c = new Coord(i,j);
                if(board[i][j]=='O' && !visitedCoord.contains(c))
                {
                    flood(board, c);
                }
            }
        }
    }
    
    void flood(char[][] board, Coord c)
    {
        Queue<Coord> queue = new ArrayDeque<Coord>();
        queue.add(c);
        ArrayList<Coord> list = new ArrayList<Coord>();
        boolean shouldFlip=true;
        while(queue.peek()!=null)
        {
            Coord c2 = queue.remove();
            list.add(c2);
            if(c2.x==0 || c2.x==board.length-1 || c2.y==0 || c2.y==board[0].length-1) 
               shouldFlip=false;
               
            if(c2.x>0 && board[c2.x-1][c2.y]=='O')
            {
                Coord c3 = new Coord(c2.x-1, c2.y);
                if(!list.contains(c3))
                {
                    queue.add(c3);
                }
            }
            if(c2.x<board.length-1 && board[c2.x+1][c2.y]=='O') 
            {
                Coord c3 = new Coord(c2.x+1, c2.y);
                if(!list.contains(c3))
                {
                    queue.add(c3);
                }
            }
            if(c2.y>0 && board[c2.x][c2.y-1]=='O')
            {
                Coord c3 = new Coord(c2.x, c2.y-1);
                if(!list.contains(c3))
                {
                    queue.add(c3);
                }
            }
            if(c2.y<board[0].length-1 && board[c2.x][c2.y+1]=='O')
            {
                Coord c3 = new Coord(c2.x, c2.y+1);
                if(!list.contains(c3))
                {
                    queue.add(c3);
                }
            }
        }
        
        for(int i=0;i<list.size();++i)
        {
            Coord c3 = list.get(i);
            if(shouldFlip) 
            {
                board[c3.x][c3.y]='X';
            }
            else visitedCoord.add(c3);
        }
    }
    

    }
    }


Log in to reply
 

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