817. Linked List Components

Reference: LeetCode
Difficulty: Medium

Problem

We are given head, the head node of a linked list containing unique integer values.

We are also given the list G, a subset of the values in the linked list.

Return the number of connected components in G, where two values are connected if they appear consecutively in the linked list.

Example:

head: 0->1->2->3
G = [0, 1, 3]
Output: 2
Explanation: 0 and 1 are connected, so [0, 1] and [3] are the two connected components.

head: 0->1->2->3->4
G = [0, 3, 1, 4]
Output: 2
Explanation: 0 and 1 are connected, 3 and 4 are connected, so [0, 1] and [3, 4] are the two connected components.

Note:

• If N is the length of the linked list given by head, 1 <= N <= 10000.
• The value of each node in the linked list will be in the range [0, N - 1].
• 1 <= G.length <= 10000.
• G is a subset of all values in the linked list.

Analysis

Methods:

1. Build Graph + DFS
   • $U \rightarrow V$. Add edges (links in the list) between $U$ and $V$ if both $U$, $V$ are in $G$.
   • Then use DFS to find all CCs (connected components).
   • Time: $O(N)$
   • Space: $O(N)$
2. Property of List
   • As for 0->1->2->3->4 and G = [0, 3, 1, 4], set the list node $1$ if the node in $G$, or $0$ if not.
   • The result is 1->1->0->1->1.
   • Steps:
     • Go over each node in head:
     • If this node in G,
       • count plus one.
       • Check if successive nodes are in G.
         • If encounter a node not in G then stop.
           • Reach null, done.
           • Go to the next node.
     • If this node not in G, go to the next node.
   • Time: $O(NG)$ and $O(N^2)$ in the worst case.
     • $O(N)$: Go over each node in head if there are $N$ nodes in total.
     • $O(G)$: Check if a node in G takes $G$ times upper bounded by $N$ since G is a subset.
   • Space: $O(1)$
3. HashSet Improvement
   • Convert the G array into a HashSet first.
   • Do the same procedures above.
   • Time: $O(N + G)$ is bounded by $O(N) = O(N + N)$
   • Space: $O(G)$

Note: In terms of the implementation, there are two ways. It turns out that counting the number of 1->0 and 1->null is more intuitive.

Code

Build Graph + DFS

public int numComponents(ListNode head, int[] G) {
  HashSet<Integer> gset = new HashSet<>();
  HashMap<Integer, LinkedList<Integer>> adj = new HashMap<>();
  // init
  for (int i : G) {
    gset.add(i);
    adj.put(i, new LinkedList<>());
  }
  // build adj
  ListNode p = head;
  while (p.next != null) {
    if (gset.contains(p.val) && gset.contains(p.next.val)) {
      int v = p.val, w = p.next.val;
      adj.get(v).add(w); // exist!
      adj.get(w).add(v); // exist!
    }
    p = p.next;
  }
  
  // traverse
  int result = 0;
  HashMap<Integer, Boolean> marked = new HashMap<Integer, Boolean>();
  for (int w : G) marked.put(w, false);
  
  for (int w : G) {
    if (!marked.get(w)) {
      ++result;
      dfs(w, adj, marked);
    }
  }
  return result;
}

private void dfs(int v, HashMap<Integer, LinkedList<Integer>> adj, HashMap<Integer, Boolean> marked) {
  // mark first
  marked.put(v, true);
  for (int w : adj.get(v)) {
    if (!marked.get(w)) {
      dfs(w, adj, marked);
    }
  }
}

Property of List

Note:

• Notice the corner case.

public int numComponents(ListNode head, int[] G) {
  int count = 0;
  ListNode p = head;
  while (p != null) {
    if (isInG(G, p.val)) { // p.val in G
      ++count;
      p = p.next;
      while (p != null && isInG(G, p.val)) {
        p = p.next;
      }
      // now: p->null OR p.val not in G
    }
    if (p != null) p = p.next;
  }
  return count;
}

private boolean isInG(int[] G, int val) {
  for (int i : G) {
    if (i == val) return true;
  }
  return false;
}

HashSet

Note:

• There is no better way to convert an array of primitive types to a set. Arrays.asList(array_primitive) will return a list of array.

public int numComponents(ListNode head, int[] G) {
  HashSet<Integer> set = new HashSet<>();
  for (int a : G) set.add(a);
  
  int count = 0;
  ListNode p = head;
  while (p != null) {
    if (set.contains(p.val)) { // p.val in G
      ++count;
      p = p.next;
      while (p != null && set.contains(p.val)) {
        p = p.next;
      }
      // now: p->null OR p.val not in G
    }
    if (p != null) p = p.next;
  }
  return count;
}

Using 1->0 or 1->null:

public int numComponents(ListNode head, int[] G) {
  HashSet<Integer> set = new HashSet<>();
  for (int a : G) set.add(a);
  
  int count = 0;
  while (head != null) {
    if (set.contains(head.val)) {
      if (head.next == null || set.contains(head.next.val) == false) {
        ++count;
      }
    }
    head = head.next;
  }
  return count;
}