Time limit exceeded for common solution


  • 0
    B

    It seems to me that I came to the same conclusion as many of you, with the exception of using BFS instead of DFS. However, I'm getting a time limit exceeded error on one of the test cases. This leads me to believe there's an infinite loop in the code, but I can't really find one. Does anyone see one, or any other error?

    public class Solution {
    public int numIslands(char[][] grid) {
        int islands = 0;
        for(int row = 0; row < grid.length; row++){
            for(int col = 0; col < grid[row].length; col++){
                if(grid[row][col] == '1'){
                    SpanLand(row, col, grid);
                    islands++;
                }
            }
        }
        return islands;
    }
    
    class Point{
        int row, col;
        public Point(int row, int col){
            this.row = row;
            this.col = col;
        }
    }
    
    public void SpanLand(int row, int col, char[][] grid){
        LinkedList<Point> q = new LinkedList<Point>();
        Point root = new Point(row, col);
        q.add(root);
        while(!q.isEmpty()){
            Point curr = q.poll();
            int up = curr.row - 1, down = curr.row + 1;
            int left = curr.col - 1, right = curr.col + 1; 
            
            if(left >= 0 && grid[curr.row][left] == '1')
                q.add(new Point(curr.row, left));
            if(right < grid[0].length && grid[curr.row][right] == '1')
                q.add(new Point(curr.row, right));
            if(down < grid.length && grid[down][curr.col] == '1')
                q.add(new Point(down, curr.col));
            if(up >= 0 && grid[up][curr.col] == '1')
                q.add(new Point(up, curr.col));
            
            grid[curr.row][curr.col] = '5';    
        }
    }
    

    }


  • 0
    O

    Because when a Point is added, the state of this Point should be changed. In your code, one Point may be add in the LinkedList more than once.


Log in to reply
 

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