I did some research on what causes a stack overflow errors, and I can conclude it is being caused by a recursive function in a program that is supposed to "count the number of islands" in an array. I understand what is causing the issue, but not sure why this is happening, or my main question is what to actually do about it. I found that if I slow down the program by having it repeatedly printing out something to the console, it works, but it takes forever to complete. Is there a way I can keep the program speed without the error, or a better way to solve the problem (search up "number of islands" to find the problem). Also, the array is two dimensional with a size of 1050 by 800.
public class NumOfIslands {
static boolean[][] dotMap = new boolean[1050][800];
static boolean visited[][] = new boolean[1050][800];
static int total = 0;
public static void main(String args[]) {
defineArrays();
run();
}
public static void findObjects(int xCord, int yCord) {
for(int y = yCord - 1; y <= yCord + 1; y++) {
for(int x = xCord - 1; x <= xCord + 1; x++) {
if(x > -1 && y > -1 && x < dotMap[0].length && y < dotMap.length) {
if((x != xCord || y != yCord) && dotMap[x][y] == true && visited[x][y] != true) {
visited[x][y] = true;
findObjects(x,y);
//System.out.println("test");
}
}
}
}
}
public static void defineArrays() {
for(int y = 0; y < 800; y++) {
for(int x = 0; x < 1050; x++) {
dotMap[x][y] = true;
}
}
}
public static int run() {
//dotMap = DisplayImage.isYellow;
System.out.println(dotMap.length + " " + dotMap[0].length);
int objects = 0;
for(int y = 439; y < 560/*dotMap[0].length*/; y++) {
for(int x = 70; x < 300/*dotMap.length*/; x++) {
if(dotMap[x][y] == true && visited[x][y] != true) {
visited[x][y] = true;
objects++;
findObjects(x,y);
}
}
}
System.out.println("total" + total);
System.out.println(objects);
return objects;
}
}
StackOverflowError reasons. In your example each call to findObjects
adds 2 variables to the stack int x and int y from loops.
One of the fastest solution:
class Solution {
int m, n;
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
m = grid.length;
n = grid[0].length;
int counter = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
visit(grid, i, j);
counter++;
}
}
}
return counter;
}
public void visit(char[][] grid, int i, int j) {
if (i < 0 || i >= m || j < 0 || j >= n) {
return;
}
if (grid[i][j] == '0') {
return;
}
grid[i][j] = '0';
visit(grid, i - 1, j);
visit(grid, i + 1, j);
visit(grid, i, j - 1);
visit(grid, i, j + 1);
}
}
All recursive algorithms can be implemented with loops. One of the example is below. The Solution implements BFS (Breadth-first search) algorithm, more details on wikipedia.
class Solution {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int nr = grid.length;
int nc = grid[0].length;
int num_islands = 0;
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
if (grid[r][c] == '1') {
++num_islands;
grid[r][c] = '0'; // mark as visited
Queue<Integer> neighbors = new LinkedList<>();
neighbors.add(r * nc + c);
while (!neighbors.isEmpty()) {
int id = neighbors.remove();
int row = id / nc;
int col = id % nc;
if (row - 1 >= 0 && grid[row-1][col] == '1') {
neighbors.add((row-1) * nc + col);
grid[row-1][col] = '0';
}
if (row + 1 < nr && grid[row+1][col] == '1') {
neighbors.add((row+1) * nc + col);
grid[row+1][col] = '0';
}
if (col - 1 >= 0 && grid[row][col-1] == '1') {
neighbors.add(row * nc + col-1);
grid[row][col-1] = '0';
}
if (col + 1 < nc && grid[row][col+1] == '1') {
neighbors.add(row * nc + col+1);
grid[row][col+1] = '0';
}
}
}
}
}
return num_islands;
}
}