# Java NON Union Find Solution, Involved many little optimizations, NOT AC...

• The idea is quite simple. Just check if this point is already in the map. Then check its surrounding area whether they are in the map. If they are in the map, merge all of the islands involved in these points.

points is a bitmap to store the points of the map.
islands is a queue for easy processing.

``````public List<Integer> numIslands2(int m, int n, int[][] positions) {
int len = positions.length;
List<Integer> result = new ArrayList<>(len);
if (len <= 0) {
return result;
}

int size = m * n;
// Check if the point is on the map.
boolean[] points = new boolean[size];
// Each island occupy a HashSet.
Queue<Set<Integer>> islands = new ArrayDeque<>(size);

for (int i = 0; i < len; i++) {
int[] cords = positions[i];
int x = cords[0];
int y = cords[1];
int point = x * n + y;
if (points[point]) {
continue;
}

points[point] = true;

// This list stores points that needs to be checked.
List<Integer> checkPoints = new ArrayList<>(4);
// Only if those are not out of bound and existed point needs to be searched.

newX = x + 1;
if (newX >= 0 && newX < m) {
adjPoint = newX * n + y;
}
}

newX = x - 1;
if (newX >= 0 && newX < m) {
adjPoint = newX * n + y;
}
}

newY = y + 1;
if (newY >= 0 && newY < n) {
adjPoint = x * n + newY;
}
}

newY = y - 1;
if (newY >= 0 && newY < n) {
adjPoint = x * n + newY;
}
}

int qSize = islands.size();
// Store the island that has the point to a list.
List<Set<Integer>> found = new ArrayList<>();
for (int j = 0; j < qSize; j++) {
Set<Integer> island = islands.poll();
// Mark if they are founded in this island.
int foundPoint = -1;
for (int k = 0; k < checkPoints.size(); k++) {
if (island.contains(checkPoints.get(k))) {
foundPoint = k;
break;
}
}

if (foundPoint == -1) {
} else {
// Found, remove the point from check list. Because no need to check further.
checkPoints.remove(foundPoint);
}
}

Set<Integer> newIsland = null;
if (found.isEmpty()) {
// Brand new island.
newIsland = new HashSet<>();
} else {
// Merge the islands.
newIsland = found.get(0);
for (int j = 1; j < found.size(); j++) {
}
}

}

return result;
}``````

• I just tried your code. It get TLE.

``````Status: Time Limit Exceeded
Submitted: 1 minute ago

Last executed input:
79
82
[[52,17],[15,44],[68,59],[6,61],[23,80],[75,22],[29,59],[62,9],[14,47],[73,4],[29,42],[45,59],[16,74],[1...``````

• Hi, I tried and get the same result. There are two possible reasons for that. One is due to the high load of server so the run time varies. The second would be the TLE threshold was changed from the time I tried. The time I tried last time was 300+ ms.

• This post is deleted!

• You are not bad...This solution passed just because the test case is small. I understand that the cases should use union find to pass and I tried this today.

By the way, may I ask that can we use Chinese to discuss there? Is it allowed to do so?

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