1

I'm writing a Java program to solve the following problem statement:

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

I went through the algorithm to implement which is essentially using DFS to compute the number of connected components.

The following is the code that I've written:

public class Solution {
    public int numIslands(char[][] grid) {

        boolean [][] visited = new boolean [grid.length][grid[0].length];
        int numClusters = 0;

        for(int i=0; i<visited.length; i++)
        {   for(int j=0; j<visited[0].length; j++)
                visited[i][j] = false;
        }

        for(int i=0; i<visited.length; i++)
        {   for(int j=0; j<visited[0].length; j++)
            {   if(grid[i][j] == '0')
                {   visited[i][j] = true;
                    continue;
                }

                if(!visited[i][j])
                {
                    DFS(grid,i,j,visited);
                    numClusters++;
                }
            }
        }

    return numClusters;

    }

     public void DFS(char[][] grid, int i, int j, boolean[][] visited)
        {
            if(i > grid.length || j > grid[0].length || i < 0 || j < 0)
                return;

               if(visited[i][j]) // Line where the error is thrown.
                    return;

                visited[i][j] = true;

                if(grid[i][j] == '0')
                    return;

                DFS(grid,i+1,j,visited);
                DFS(grid,i-1,j,visited);
                DFS(grid,i,j+1,visited);
                DFS(grid,i,j-1,visited);

        }
}

I'm getting an ArrayIndexOutOfBoundsException when I try to execute this for the input 

["11000","11000","00100","00011"]

The error is on the line - if(visited[i][j]) of the DFS function definition. I've updated it in the code as well as a comment.

Any help on this would be great!

Kaushik Rajan
  • 43
  • 6
  • Maybe you could post the stacktrace and mark in your code where the exception is thrown –  Nov 24 '16 at 16:52
  • 1
    A string in Java is NOT a char array! – John Strood Nov 24 '16 at 16:54
  • This isn't really a question about the islands problem -- it's a "please debug my code" question -- https://ericlippert.com/2014/03/05/how-to-debug-small-programs/ – slim Nov 24 '16 at 16:58
  • 2
    and please do add how you call your `numIslands` function. Because as @Djack mentionned: a String is not a char array in Java and if you first process the string array from your input, we need to know that as well. – J.Baoby Nov 24 '16 at 17:00
  • Your input does not match the statement "You may assume all four edges of the grid are all surrounded by water" in the task. – Robert Nov 24 '16 at 17:01
  • Look at the exception message. It will tell you what the index which is out of bounds is, and that should give you a hint as to the problem (luckily, you have different width and height, which makes it even easier). – Andy Turner Nov 24 '16 at 17:06
  • Thanks for the suggestions everyone. It was a minor change which I missed. (Had to update the if condition before the error). Kind of feel silly asking this question now. It's working fine now! – Kaushik Rajan Nov 24 '16 at 17:56

0 Answers0