Zombie Clusters Problem

There are zombies in Seattle. Some of them know each other directly. Others might know each other transitively, through others. For example, if zombies A<->B and B<->C know each other directly, then A and C know each other indirectly and all three belong to one cluster.

Knowing which zombies know each other directly, find the number of the zombie clusters.

Input is a square matrix where each cell, zombies[A][B], indicates whether zombie A knows zombie B directly.

Example One

Input:

[“1100”,

“1110”,

“0110”,

“0001”]

Output: 2

There are four zombies: z0, z1, z2 and z3.

Each zombie knows oneself, thus the matrix diagonal has all 1s.

Other than that, the green matrix cells indicate that z0<->z1 and z1<->z2 know each other directly.

Because of the transitive property, zombies z0, z1 and z2 form one cluster.

The remaining zombie, z3, doesn’t know others and forms their own separate cluster.

This gives us a total of 2 zombie clusters.

Example Two

Input:

[“10000”,

“01000”,

“00100”,

“00010”,

“00001”]

Output: 5

Each zombie forms their own cluster: {z0}, {z1}, {z2}, {z3}, and {z4}. The total number of clusters is 5.

Notes

Input Parameters: The function has one argument, an array of n strings. Each string has n characters, each character is either ‘0’ or ‘1’.

Output: Return an integer, the number of zombie clusters.

Constraints:

●      1 <= number of zombies <= 1000

Solutions

We provided one efficient solution, it uses depth first traversal (DFS) to locate the clusters (connected components) in the graph of zombies. We think of “zombie A knows zombie B” as an undirected graph edge. The given list of strings (essentially a two-dimensional boolean array) is an adjacency matrix for our graph of connected zombies.

Please note that solutions that use Union Find algorithm with Path Compression (refer to IK class covering that) might pass all tests but will be suboptimal; time complexity of such solutions would be O(n^2 * log(n)) versus O(n^2) for the DFS solution we discuss here.

dfs_solution.java

• Iterating over zombies from 0 to n-1 (the DFS outer loop), we perform DFS traversal on the current node if it isn’t yet visited.
• DFS marks graph nodes it visits so that they aren’t visited again. It doesn’t need to do anything else because all we need is to count the connected components (nothing more specific than that like remembering which nodes belong to which component).
• Every time the DFS outer loop encounters an unvisited node, we know that we have found another connected component, so we increment the counter. The DFS function call then takes care of marking all the nodes in that component visited.
• By the time the DFS outer loop is done, we have the number of zombie clusters in the counter variable.

Let us see how this algorithm works on this example input:

1 1 0

1 1 0

0 0 1

The outer loop first tries zombie0. It is unvisited, so we increment the counter and call function dfs() on zombie0. That call ends up visiting zombie0 and zombie1.

The outer loop then tries zombie1. It is already visited by then so the counter isn’t incremented and dfs() isn’t called.

The outer loop then tries zombie2. It is unvisited, so we increment the counter and call function dfs() on zombie2. That call ends up visiting zombie2.

The outer loop is now done. We return the value of the counter; that’s 2.

Time Complexity:

O(n^2) for the number of zombies.

Function dfs() is called exactly once (either from the DFS outer loop or from the dfs() function itself) on every graph none, so a total of n times.

Once called on a node, dfs() takes O(n) time because it needs to check if that node is connected to any other node, one by one.

n * O(n) = O(n^2) is the total time complexity.

Auxiliary Space Used:

O(n) for the number of zombies.

“Visited” array takes O(n) space.

Recursive function dfs() will make O(n) nested calls of itself in the worst case, so up to O(n) space can be allocated in the call stack at any time.

Space Complexity:

O(n^2) because of the input size.

 // -------- START --------
    static int zombieCluster(List zombies) {
        int clusters = 0, n = zombies.size();
        boolean[] visited = new boolean[n];

        // Call dfs on any zombie that has not been visited yet.
        for(int i = 0; i < n; i++) {
            if(!visited[i]) {
                // Any unvisited zombie is a part of a cluster we have not seen until now.
                clusters++;
                // dfs() call will visit *all* zombies in that cluster.
                dfs(i, n, zombies, visited);
            }
        }
        return clusters;
    }

    // Traverse depth first starting from node x, mark all visited nodes visited.
    static void dfs(int x, int n, List zombies, boolean[] visited) {
        visited[x] = true;
        for(int i = 0; i < n; i++) {
            if(zombies.get(x).charAt(i) == '1' && !visited[i]) {
                dfs(i, n, zombies, visited);
            }
        }
    }
}
// -------- END --------

‍