CodingGyan

Mark and Sweep: Find the Garbage

medium JVM, Memory and Performance

Problem

A program has n objects numbered 0 to n-1. The first line is n. The second line lists the root objects (objects the running program can use directly), or a single - if there are none. Each next line a b means: object a holds a reference to object b. An object is garbage if it cannot be reached from any root by following references. Print the garbage objects in ascending order, or none.

Constraints

  • 1 <= n <= 10^5

Examples

Input

5
0
0 1
1 2
3 4

Output

3 4

Solutions

Best approachTime O(n + m)Space O(n + m)

Garbage collectors do not count references (which fails for cycles like 2 and 3 in the example). They mark everything reachable from the roots, then sweep the rest. Two objects that point to each other are still garbage if no root reaches them.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Find the garbage.
 * Input   : n, the roots, then reference lines.
 * Output  : The garbage objects.
 * Approach: Mark and sweep.
 * Time    : O(n + m)
 * Space   : O(n + m)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static String solve(String[] lines) {
        int n = Integer.parseInt(lines[0]);

        // Step 1: Read the roots (the objects the program can reach directly). A line with only "-" means: no roots.
        java.util.ArrayDeque<Integer> pending = new java.util.ArrayDeque<>();
        if (!lines[1].equals("-")) {
            for (String root : lines[1].split(" ")) {
                pending.push(Integer.parseInt(root));
            }
        }

        // Step 2: Read the references. references.get(a) holds the objects that object a points to.
        java.util.List<java.util.List<Integer>> references = new java.util.ArrayList<>();
        for (int i = 0; i < n; i++) {
            references.add(new java.util.ArrayList<>());
        }
        for (int i = 2; i < lines.length; i++) {
            String[] edge = lines[i].split(" ");
            references.get(Integer.parseInt(edge[0])).add(Integer.parseInt(edge[1]));
        }

        // Step 3: MARK. Walk from the roots and mark every object we can reach.
        boolean[] marked = new boolean[n];
        while (!pending.isEmpty()) {
            int object = pending.pop();
            if (marked[object]) {
                continue;
            }
            marked[object] = true;
            for (int next : references.get(object)) {
                pending.push(next);
            }
        }

        // Step 4: SWEEP. Every object that is not marked is garbage.
        StringBuilder garbage = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (!marked[i]) {
                garbage.append(garbage.length() == 0 ? "" : " ").append(i);
            }
        }
        return garbage.length() == 0 ? "none" : garbage.toString();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        java.util.List<String> all = new java.util.ArrayList<>();
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine().trim();
            if (!line.isEmpty()) {
                all.add(line);
            }
        }
        String[] lines = all.toArray(new String[0]);
        System.out.println(solve(lines));
    }
}
Hints (1)
  1. Why does reference counting fail for cycles but mark and sweep does not?

Try these next