Leetcode 817. Linked List Components

Problem Explanation:

We are given the head node of a linked list, where each node in linked list contains a unique integer. The goal of this problem is to identify connected components in a subset of the integers from the linked list.

A connected component is a sequence of numbers that appear consecutively in the linked list. For example, if we have the following linked list:

1
2
30 -> 1 -> 2 -> 3

and the following subset of values [0, 1, 3], the connected components would be [0, 1] and [3], so the output would be 2.

To solve this problem, we create a set that contains all the values in the subset of linked list values. We then traverse the linked list and check if the value of the current node is in the set. If the current value is in the set, and either the next node is null or its value is not in the set, we increment a counter.

Python Solution:

1
2python
3class Solution:
4    def numComponents(self, head, G):
5        set_G = set(G)
6        ans = 0
7        while head:
8            if head.val in set_G and (not head.next or head.next.val not in set_G):
9                ans += 1
10            head = head.next
11        return ans

Java Solution:

1
2java
3public class Solution {
4    public int numComponents(ListNode head, int[] G) {
5        Set<Integer> setG = new HashSet<>();
6        for (int i : G) { setG.add(i); }
7      
8        int ans = 0;
9        while (head != null) {
10            if (setG.contains(head.val) && (head.next == null || !setG.contains(head.next.val))) {
11                ans++;
12            }
13            head = head.next;
14        }
15        return ans;
16    }
17}

JavaScript Solution:

1
2javascript
3var numComponents = function(head, G) {
4    let setG = new Set(G);
5    let ans = 0;
6    while (head != null) {
7        if (setG.has(head.val) && (head.next == null || !setG.has(head.next.val))) {
8            ans++;
9        }
10        head = head.next;
11    }
12    return ans;
13};

C++ Solution:

1
2cpp
3class Solution {
4public:
5    int numComponents(ListNode* head, vector<int>& G) {
6        unordered_set<int> setG(G.begin(), G.end());
7        int ans = 0;
8        while (head) {
9            if (setG.count(head->val) && (!head->next || !setG.count(head->next->val)))
10                ans++;
11            head = head->next;
12        }
13        return ans;
14    }
15};

C# Solution:

1
2csharp
3public class Solution {
4    public int NumComponents(ListNode head, int[] G) {
5        HashSet<int> setG = new HashSet<int>(G);
6        int ans = 0;
7        while (head != null) {
8            if (setG.Contains(head.val) && (head.next == null || !setG.Contains(head.next.val))) {
9                ans++;
10            }
11            head = head.next;
12        }
13        return ans;
14    }
15}

In each language before we start the loop, we initialize ansas 0 and convert the list G into a set. This is done to improve the time complexity of lookup operations. Next, we enter a while loop, which continues until the end of the linked list. And in each iteration, we are first checking if the node's value is present in the set, and if either there's no next node or the next node's value is not in the set then ans is incremented. This is because it either means we came across a connected component for the first time or we got to the end of a connected component. Finally, ans is returned, which answers the problem statement.## Rust Solution:

1
2rust
3use std::collections::HashSet;
4
5pub struct Solution {}
6pub struct ListNode {
7  pub val: i32,
8  pub next: Option<Box<ListNode>>
9}
10
11impl Solution {
12    pub fn num_components(head: Option<Box<ListNode>>, g: Vec<i32>) -> i32 {
13        let set_g: HashSet<_> = g.into_iter().collect();
14        let mut ans = 0;
15        let mut current_node = head;
16
17        while let Some(node) = current_node {
18            if set_g.contains(&node.val) && (node.next.is_none() || !set_g.contains(&(node.next.unwrap().val))) {
19                ans += 1;
20            }
21
22            current_node = node.next;
23        }
24
25        ans
26    }
27}

Swift Solution:

1
2swift
3public class ListNode {
4    public var val: Int
5    public var next: ListNode?
6    public init(_ val: Int) {
7        self.val = val
8        self.next = nil
9    }
10}
11
12class Solution {
13    func numComponents(_ head: ListNode?, _ G: [Int]) -> Int {
14        var setG = Set(G)
15        var ans = 0
16        var node = head
17        while node != nil {
18            if setG.contains(node!.val) && (node!.next == nil || !setG.contains(node!.next!.val)) {
19                ans += 1
20            }
21            node = node!.next
22        }
23        return ans
24    }
25}

As in other languages, the Swift and Rust solutions also first initialize a set with the contents of G. This makes it possible to efficiently check if a value from the linked list is in the set. A counter ans is initialized to 0. Each node of the list is then traversed. If a node's value is found in the set and if it does not have a next node or the next node's value is not in the set, the counter is incremented. This indicates that we have found a connected component. At the end of the iteration, we return ans which is the total number of connected components.