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:

1
2
3
4
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.
1
2
3
4
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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;
}

Comment