"Two-pass algorithm" implementation in Java

Question

I'm rather new to Java and to algorithms in general. I implemented the so called Two-pass algorithm, and want to know if there are improvements to my way of implementing it. What it does is it takes a matrix of ones and zeros and replaces all ones by labels. All ones that are connected should be labeled with the same label. Each such component should have a unique label. The end result can be visualized by replacing each label with a color, like this:

result

I followed as closely as I could the pseudo-code available in this section of the Wikipedia article. But are there improvements?

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;
public class MatrixComponents {
 public int[][] labeledMatrix;
 public MatrixComponents(int[][] matrix) {
 ArrayList<ArrayList<Integer>> linked = new ArrayList<ArrayList<Integer>>();
 int[][] labels = new int[matrix.length][matrix[0].length];
 int NextLabel = 0;
 //First pass
 for(int i=0; i<matrix.length; i++) {
 for( int j=0; j<matrix.length; j++) {
 labels[i][j] = 0;
 }
 }
 for(int i=0; i<matrix.length; i++) {
 for(int j=0; j<matrix[0].length; j++) {
 if(matrix[i][j] != 0) {
 //Labels of neighbors
 ArrayList<Integer> neighbors = new ArrayList<Integer>();
 for(int ni=-1; ni<=1; ni++) {
 for(int nj=-1; nj<=1; nj++) {
 if(i+ni<0 || j+nj<0 || i+ni>labels.length-1 || j+nj>labels[0].length-1) {
 continue;
 }
 else {
 if(i+ni == 0 && i+nj == 0) continue;
 if(labels[i+ni][j+nj] != 0) neighbors.add(labels[i+ni][j+nj]);
 }
 }
 }
 if(neighbors.size() == 0) {
 ArrayList<Integer> tempArrayList = new ArrayList<Integer>();
 tempArrayList.add(NextLabel);
 linked.add(NextLabel, tempArrayList);
 labels[i][j] = NextLabel;
 NextLabel++;
 }
 else {
 labels[i][j]=1000*1000;
 for(int neighbor : neighbors) {
 if(neighbor < labels[i][j]) labels[i][j] = neighbor;
 }
 for(int neighbor : neighbors) {
 linked.set(neighbor,union(linked.get(neighbor),neighbors));
 }
 }
 }
 }
 }
 //Second pass
 for(int i=0; i<matrix.length; i++) {
 for(int j=0; j<matrix[0].length; j++) {
 ArrayList<Integer> EquivalentLabels = linked.get(labels[i][j]);
 labels[i][j]=1000*1000;
 for(int label : EquivalentLabels) {
 if(label < labels[i][j]) labels[i][j]=label;
 }
 }
 }
 labeledMatrix = labels;
 }
 //union: http://stackoverflow.com/questions/5283047/intersection-and-union-of-arraylists-in-java
 public <T> ArrayList<T> union(ArrayList<T> list1, ArrayList<T> list2) {
 Set<T> set = new HashSet<T>();
 set.addAll(list1);
 set.addAll(list2);
 return new ArrayList<T>(set);
 }
 public int[][] getLabeledMatrix() {
 return labeledMatrix;
 }
 public static void main(String[] args) {
 int[][] matrix = {{0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1,
 0, 0, 0, 0, 0, 0, 0}, {1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0,
 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1}, {0, 1, 0, 0, 0, 0, 0,
 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 0}, {0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0,
 0, 1, 0, 0, 1, 0, 0, 1, 0}, {0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0,
 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1}, {0, 0, 0, 0, 1,
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0,
 0, 0}, {0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0,
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0,
 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1}, {0, 1, 0, 0,
 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1,
 0, 0, 1, 0}, {0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0,
 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0}, {1, 1, 1, 0, 1, 1, 0, 1, 1, 1,
 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1}, {0, 0,
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0,
 1, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0,
 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0}, {1, 1, 0, 0, 1, 1, 0, 1, 0,
 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1}, {0,
 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1,
 0, 0, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0,
 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0}, {0, 1, 1, 1, 1, 0, 0,
 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1,
 0}, {0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0,
 0, 1, 0, 0, 1, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0,
 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0}, {0, 1, 1, 0, 1,
 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1,
 1, 0}, {0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0,
 0, 0, 1, 0, 0, 1, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0,
 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0}, {0, 1, 0, 1,
 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1,
 1, 1, 1, 1}, {0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0,
 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0}, {0, 0, 0, 0, 1, 0, 0, 1, 0, 0,
 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 1,
 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0,
 1, 1, 1, 1, 1}, {0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1,
 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 0, 0,
 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0}, {1,
 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1,
 0, 1, 1, 0, 1, 1, 0}, {0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0,
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};
 MatrixComponents matrixComponents = new MatrixComponents(matrix);
 int[][] newMatrix = matrixComponents.getLabeledMatrix();
 System.out.println("{");
 for(int i=0; i<newMatrix.length; i++) {
 System.out.print("{");
 for(int j=0; j<newMatrix[0].length; j++) {
 if(j != newMatrix[0].length-1)
 System.out.print(newMatrix[i][j]+", ");
 else
 System.out.print(newMatrix[i][j]);
 }
 if(i != newMatrix.length-1)
 System.out.println("},");
 else
 System.out.println("}");
 }
 System.out.print("}");
 }
}

The test in the main method prints the array. I don't know of any quick way of visualizing it in Java, but if it would be visualized it would look like my image above.

• Neil: Technically initialization of the matrix doesn't count as a pass, so I would move //First pass to the beginning of the following for loop.

Answer 1

Declare by interface and not implementation

Instead of

ArrayList<ArrayList<Integer>> linked = new ArrayList<ArrayList<Integer>>();

use:

List<List<Integer>> linked = new ArrayList<List<Integer>>();

Or, if you're using Java 7+:

List<List<Integer>> linked = new ArrayList<>();

Edit: When looking at your code a bit more, with all the union method and stuff going on, I wonder if it perhaps should be List<Set<Integer>> right from the start, so that you could use

linked.get(neighbor).addAll(neighbors);

instead of what you currently do:

linked.set(neighbor,union(linked.get(neighbor),neighbors));

---

Algorithmically speaking, this part:

//First pass
for(int i=0; i<matrix.length; i++) {
 for( int j=0; j<matrix.length; j++) {
 labels[i][j] = 0;
 }
}

Is a) Not part of the first pass. b) Totally unnecessary as the labels array is filled with zeros already. c) Buggy if matrix is not square.

---

int[][] matrix = {{0, 0, 0, 0, 1, ...

I'd highly recommend reading from a file instead of hardcoding into the code!

---

Your constructor and your main method is doing way too many things, break up the code into additional methods.

Some methods can include:

• Read matrix from file / some input / code
• One (or more) methods for doing the "first pass" (you can put the 2d outer loop in one method, which can call another method)
• One method for the "second pass"
• One method for the output

---

public int[][] labeledMatrix;

Don't use public fields like that, that one should be private. It's good to restrict the visibility as much as possible.

---

i and j vs. x and y

Sometimes 2d arrays are indexed as matrix[x][y] and sometimes as matrix[y][x], to make it clear which version you're using, don't use i and j. I really don't like those variable names when using 2d arrays.

---

It is a good practice to always use braces, even for one-liners: (Even I get told this from time to time!)

if(i+ni == 0 && i+nj == 0) continue;
if(labels[i+ni][j+nj] != 0) neighbors.add(labels[i+ni][j+nj]);

Is changed to:

if (i + ni == 0 && i + nj == 0) {
 continue;
}
if (labels[i + ni][j + nj] != 0) {
 neighbors.add(labels[i + ni][j + nj]);
}

Remember the comments about the naming though.

---

For your drawing an image plans, you should read up on Creating and Drawing to an Image and the chapter that follows it Writing/Saving an Image. You can use the Graphics2D object as shown in the first link to draw rectangles on the image.

---

if(neighbors.size() == 0) {

is the same as

if (neighbors.isEmpty()) {

Answer 2

White-Space

You really need some white-space in your code. This is the first thing that will help to read your code easily. I have not read a lot your since it's really to read those kind of exppresions :

if(i+ni<0 || j+nj<0 || i+ni>labels.length-1 || j+nj>labels[0].length-1)

With some white-spaces, it will be easier to easily see what's going on.

if(i + ni < 0 || j + nj < 0 || i + ni > labels.length - 1 || j + nj > labels[0].length - 1)

It could look like it take a lot more of space, but it's worth it. Imagineiftosavespacewewouldallwritelikethis (This is just an exaggeration, this is not that much of a problem).

Variables names

I know i and j are common names for counter in a for loop, but you can give relevant names too. Why would you not follow the "suggestion" from the wiki and use row and column, this would be much more relevant to your context.

Reading i + ni < 0 versus row + neighborsPosition, I prefer the second option.

In Java, variable names are camelCase so EquivalentLabels and NextLabel should be equivalentLabels and nextLabel. (Hint look at the coloration syntax in your question, it identify those variables like a class).

Functions

You could separate your code in smaller functions. A good example would be :

 ArrayList<Integer> neighbors = new ArrayList<Integer>();
 for(int ni=-1; ni<=1; ni++) {
 for(int nj=-1; nj<=1; nj++) {
 if(i+ni<0 || j+nj<0 || i+ni>labels.length-1 || j+nj>labels[0].length-1) {
 continue;
 }
 else {
 if(i+ni == 0 && i+nj == 0) continue;
 if(labels[i+ni][j+nj] != 0) neighbors.add(labels[i+ni][j+nj]);
 }
 }
 }

This clearly could be a function constructNeighborsList. It would not change your code much but would help read your code.

• Marc-Andre: I'm looking at your algo, I will edit if I find something to say about it.
• Travis: I would go a bit further with the methods. For example, i+ni<0 || j+nj<0 || i+ni>labels.length-1 || j+nj>labels[0].length-1 could be extracted to method on its own, improving readability and promoting single purpose programming.
• Marc-Andre: @Travis I almost suggest it, but I think he's not there yet. I agree with you though and I do it myself when the condition is complex. I might edit it when I'll be back home!

Answer 3

Just a small little comment about your array initializer:

int[][] matrix = {{0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1,
 0, 0, 0, 0, 0, 0, 0}, {1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0,
 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1}, {0, 1, 0, 0, 0, 0, 0,
 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 0}, {0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0,
 0, 1, 0, 0, 1, 0, 0, 1, 0}, {0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0,
 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1}, {0, 0, 0, 0, 1,
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0,
 0, 0}, {0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0,
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0,
 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1}, {0, 1, 0, 0,
 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1,
 0, 0, 1, 0}, {0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0,
 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0}, {1, 1, 1, 0, 1, 1, 0, 1, 1, 1,
 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1}, {0, 0,
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0,
 1, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0,
 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0}, {1, 1, 0, 0, 1, 1, 0, 1, 0,
 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1}, {0,
 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1,
 0, 0, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0,
 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0}, {0, 1, 1, 1, 1, 0, 0,
 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1,
 0}, {0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0,
 0, 1, 0, 0, 1, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0,
 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0}, {0, 1, 1, 0, 1,
 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1,
 1, 0}, {0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0,
 0, 0, 1, 0, 0, 1, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0,
 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0}, {0, 1, 0, 1,
 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1,
 1, 1, 1, 1}, {0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0,
 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0}, {0, 0, 0, 0, 1, 0, 0, 1, 0, 0,
 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 1,
 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0,
 1, 1, 1, 1, 1}, {0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1,
 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 0, 0,
 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0}, {1,
 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1,
 0, 1, 1, 0, 1, 1, 0}, {0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0,
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};

Would be much easier to (削除) read (削除ここまで) parse, and to eventually maintain, if you put line breaks after each element, lining up each item:

int[][] matrix = {
 {0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0}, 
 {1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1}, 
 {0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
 {0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0}, 
 {0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1}, 
 {0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0}, 
 {0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
 {1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1}, 
 {0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0},
 {0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0}, 
 {1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1}, 
 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0}, 
 {0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0}, 
 {1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1}, 
 {0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0}, 
 {0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0}, 
 {0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0}, 
 {0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0},
 {0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0}, 
 {0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0}, 
 {0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0}, 
 {0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0}, 
 {0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1}, 
 {0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0}, 
 {0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
 {0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1}, 
 {0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0}, 
 {0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0}, 
 {1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0}, 
 {0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
};

Now whether or not it's a good idea to put data in your code like this, ... there has to be a better way... I'll leave the actual review to the java guys. Cheers!

• Simon Forsberg: Did you have to copy-paste that whole matrix into your answer? :)
• corsiKa: What a troll - "just a small comment"... proceeds to paste two gigantic matrices.
• user36070: +1. "A picture tells more than thousand words." "Show, don't tell" etc. I think's a perfectly valid answer, thanks.
• Mathieu Guindon: @Pickett awesome! thanks! Welcome to the CR voters' club :D (looks like there's heavy caching on these pages though), feel free to spend up to 40/day, this site needs more voters! :)
• Cruncher: This was bugging me too. I checked all the answers first to see if anyone had mentioned it yet. And alas someone did. +1

Answer 4

Some small tips:

• Avoid calculations in a loop. Change 1000*1000 to a constant:

  public static final int MILLION = 1000 * 1000;
  

• Integer arrays have default value of zero when created, so your "first pass" could be arrested.

• Matthew: Much like no one would write public static final int ONE = 1, perhaps a better name for MILLION would be the significance of what it represents. I would recommend Integer.Max_Value instead, as MILLION just seems arbitrary.
• Ilya Gazman: Yeah, I agree with you. I did not understood the meaning by my self.
• Chris Hayes: "Avoid calculations in a loop" is good advice in general, but in this case 1000 * 1000 is a compile-time constant and there's no performance implication. It's still a good idea for readability.
• Ilya Gazman: @ChrisHayes I agree with you in general, how ever I think it works slightly different. It's not a compile constant but it will optimized with Java jet. Of curse it doesn't meter in this case.
• Chris Hayes: @Ilya_Gazman It absolutely is a compile-time constant, per your own link. In JLS terms, it's two primitive literals composed with the operator *, which is explicitly called out as a constant expression.