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


  • 0
    Y

    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 the point already added, no need to merge.
            if (points[point]) {
                result.add(islands.size());
                continue;
            }
            
            points[point] = true;
            
            // This list stores points that needs to be checked.
            List<Integer> checkPoints = new ArrayList<>(4);
            int newX, newY, adjPoint;
            // 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;
                if (points[adjPoint]) {
                    checkPoints.add(adjPoint);
                }
            }
            
            newX = x - 1;
            if (newX >= 0 && newX < m) {
                adjPoint = newX * n + y;
                if (points[adjPoint]) {
                    checkPoints.add(adjPoint);
                }
            }
            
            newY = y + 1;
            if (newY >= 0 && newY < n) {
                adjPoint = x * n + newY;
                if (points[adjPoint]) {
                    checkPoints.add(adjPoint);
                }
            }
            
            newY = y - 1;
            if (newY >= 0 && newY < n) {
                adjPoint = x * n + newY;
                if (points[adjPoint]) {
                    checkPoints.add(adjPoint);
                }
            }
            
            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))) {
                        found.add(island);
                        foundPoint = k;
                        break;
                    }
                }
                
                if (foundPoint == -1) {
                    // Not found, add the island back to the queue.
                    islands.add(island);
                } 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<>();
                newIsland.add(point);
                islands.add(newIsland);
            } else {
                // Merge the islands.
                newIsland = found.get(0);
                newIsland.add(point);
                for (int j = 1; j < found.size(); j++) {
                    newIsland.addAll(found.get(j));
                }
                // Add back to queue.
                islands.add(newIsland);
            }
            
            result.add(islands.size());
        }
        
        return result;
    }

  • 0

    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...

  • 0
    Y

    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.


  • 0
    This post is deleted!

  • 0
    Y

    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?


  • 0

    I don't know you need ask admin.


  • 0

    I have adjusted the resource limit so your solution gets AC now. Sorry about that.


Log in to reply
 

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