array index out of boundary exception floodfill java

Question

I am trying to count number of zero from a 2d array by using floodfill, but I am getting an ArrayIndexOutOfBoundsException. Here is what I've done so far. I commented where the error is.

public class floodfill {

    public static int[][] input = new int[][]{
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
    };

    public static int count = 0;

    public static void main(String[] args) {
        int row = input.length;
        int col = input[0].length;
        System.out.println("" + row);
        System.out.println("" + col);

        apply(row, col);

    }

    private static void apply(int x, int y) {
        int currentColor = getValueAt(x, y);
        if (currentColor == 0) {
            count++;
            apply(x + 1, y);
            apply(x - 1, y);
            apply(x, y + 1);
            apply(x, y - 1);
        }
    }

    private static int getValueAt(int x, int y) {
        if (x < 0 || y < 0 || x > input.length || y > input[x].length) {
            return -1;
        } else {
            return input[x][y];
        }
    }

}

Shouldn't you be passing `0` to `apply()`? Right now, you are passing the `length` of the `row` and `col`, which in turn gives you the `size` of the array. It seems to me like you are passing the`size`, so when you get down to `return input[x][y];` it is `index out of bounds`. — Hypnic Jerk, Oct 06 '16 at 20:17
I'm not seeing any comments in this code. Have you tried to use a debugger? — OneCricketeer, Oct 06 '16 at 20:17
int row = input.length-1; int col = input[0].length-1; will fix your problem — JavaHopper, Oct 06 '16 at 20:19

nbrooks · Accepted Answer · 2016-10-06T21:45:02.490

In addition to the errors that have been pointed out with your array index checking (terminating when >= array length, rather than when greater than the length), your recursion will never terminate and you're going to experience some pretty fun stack overflow errors.

Once you've been into a cell, you'll need to change the value from 0 to something else (1, for example). I'd suggest adding a visit method to handle this:

private static void visit(int x, int y) {
    input[x][y] = 1;
}

You would call this inside apply, inside of your if block. Finally, you should probably start at the first node apply(0, 0) and work your way outwards (x+1, y+1), (x, y+1), (x+1, y); there's never a reason to subtract from the current index, since previous cells will have already been visited.

private static void apply(int x, int y) {
    int currentColor = getValueAt(x, y);
    if (currentColor == 0) {
        visit(x, y);
        count++;
        apply(x + 1, y + 1);
        apply(x + 1, y);
        apply(x, y + 1);
    }
}

Demo

There's a simple visualization of this updated algorithm running below (ported to JS to run in the browser, but the syntax is similar enough that you will understand it -- you can ignore the code that's specific to the visualization).

$(function() {
    var input = [
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    ];

    var count = 0;

    function main() {
        var row = 0, col = 0;
        apply(row, col);
        console.log(count);
    };

    function apply(x, y) {
        var currentColor = getValueAt(x, y);
        if (currentColor == 0) {
            visit(x, y);
            count++;
            apply(x + 1, y + 1);
            apply(x + 1, y);
            apply(x, y + 1);
        }
    }

    function getValueAt(x, y) {
        if (x < 0 || y < 0 || x >= input.length || y >= input[x].length) {
            return -1;
        } else {
            return input[x][y];
        }
    }

    function visit(x, y) {
        setTimeout(function() {
           $(("#child" + x) + y).css("background-color", "pink");
        }, 170 * x + 170 * y);
        input[x][y] = 1;
    }

    function visualize() {
        for (var i = 0; i < input.length; i++) {
            $("<div />", {
                "id" : "row" + i
            }).appendTo("#parent");

            for (var j = 0; j < input[i].length; j++) {

                $("<div />", {
                    "class" : "child",
                    "id" : ("child" + i) + j
                }).appendTo("#row" + i);
            }
        }
    }

    visualize();
    main();
});

.child {
 width: 25px;
 height: 25px;
 background-color: yellow;
 border: 1px solid black;
 margin: 1px;
 display: inline-block;
}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.11.1/jquery.min.js"></script>
<div id="parent"></div>

+10000000 for taking the time not only to answer, but also to write a visualization demo! and port it to JS to run in the browser!! — Gonen I, Oct 06 '16 at 21:43

score 0 · Answer 2 · 2016-10-06T20:31:27.740

Your problem here is that when going to getValueAt, you are passing the array length, and array indices stop at .length - 1. The parameter was 1 too much... It wouldn't have thrown an error if your 'if' statement was correct:

// Add equal sign to last 2 conditions
if (x < 0 || y < 0 || x >= input.length || y >= input[x].length) {
    return -1;
}

Other minor stuff:

Always capitalize your class names, i.e Floodfill or FloodFill;
It's kind of useless to have an 'else' statement after an 'if' statement that returns.

score 0 · Answer 3 · answered Oct 06 '16 at 20:26

I am looking at your getValueAt function and the boundary conditions are inaccurate. Array elements are indexed from 0 to the array's length minus 1, if you try to access an element outside of these limits you will get an exception. Try the following code to be in bounds in your getValueAt function:

private static int getValueAt(int x, int y) {
    if (x < 0 || y < 0 || x >= input.length || y >= input[x].length) {
        return -1;
    } else {
        return input[x][y];
    }
}

Also, I would suggest changing your initial apply to be in bounds, as array.length or array[x].length is not in bounds.

array index out of boundary exception floodfill java

3 Answers3

Demo