# Linked List Components
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/linked-list-components)
Canonical: https://scaleengineer.com/dsa/problems/linked-list-components
**Data structures:** Array, Hash Table, Linked List
---
## Problem
You are given the `head` of a linked list containing unique integer values and an integer array `nums` that is a subset of the linked list values.

Return _the number of connected components in_ `nums` _where two values are connected if they appear **consecutively** in the linked list_.

**Example 1:**

![](https://assets.glich.co/dsa/linked-list-components/image0.jpg) 

**Input:** head = [0,1,2,3], nums = [0,1,3]
**Output:** 2
**Explanation:** 0 and 1 are connected, so [0, 1] and [3] are the two connected components.

**Example 2:**

![](https://assets.glich.co/dsa/linked-list-components/image1.jpg) 

**Input:** head = [0,1,2,3,4], nums = [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.

**Constraints:**

* The number of nodes in the linked list is `n`.
* `1 <= n <= 104`
* `0 <= Node.val < n`
* All the values `Node.val` are **unique**.
* `1 <= nums.length <= n`
* `0 <= nums[i] < n`
* All the values of `nums` are **unique**.

# Approaches
## Brute Force with Linear Scan
This approach involves iterating through the linked list. For each node, we check if its value and its next node's value are present in the `nums` array by performing a linear scan through `nums`. We count a component every time we find a node that is in `nums` but its next node is either null or not in `nums`.
**Time:** O(N * M), where N is the number of nodes in the linked list and M is the length of the `nums` array. For each of the N nodes, we may perform up to two linear scans of the `nums` array, each taking O(M) time. · **Space:** O(1), as we only use a few variables to store the count and the current node pointer.
**Pros:** Simple to understand and implement.; Very low memory usage.
**Cons:** Highly inefficient for large inputs, likely to result in a "Time Limit Exceeded" error on most platforms.; The repeated linear scans of the `nums` array are the bottleneck.
### Explanation
The core idea is to identify the end of each connected component. A component ends when a node `curr` has its value in `nums`, but the subsequent node `curr.next` either doesn't exist (i.e., `curr` is the tail) or its value is not in `nums`.

We traverse the linked list from the `head`.
For each node, we first check if its value is in the `nums` array. This check is done by iterating through the entire `nums` array.
If the current node's value is found in `nums`, we then check if it's the end of a component. This is true if the next node is `null` or the next node's value is not in `nums` (which requires another linear scan of `nums`).
If it's the end of a component, we increment our component counter.
We continue this process until we have traversed the entire linked list.

```java
class Solution {
    private boolean contains(int[] nums, int target) {
        for (int num : nums) {
            if (num == target) {
                return true;
            }
        }
        return false;
    }

    public int numComponents(ListNode head, int[] nums) {
        int components = 0;
        ListNode current = head;
        while (current != null) {
            // Check if current node's value is in nums
            if (contains(nums, current.val)) {
                // Check if it's the end of a component
                if (current.next == null || !contains(nums, current.next.val)) {
                    components++;
                }
            }
            current = current.next;
        }
        return components;
    }
}
```
### Algorithm
*   Initialize a counter `components` to 0.
*   Create a pointer `current` and set it to `head`.
*   Loop while `current` is not `null`:
    *   Linearly scan the `nums` array to check if `current.val` exists.
    *   If `current.val` is in `nums`:
        *   Check if `current.next` is `null` or if `current.next.val` is not in `nums` (by another linear scan).
        *   If either condition is true, increment `components`.
    *   Move to the next node: `current = current.next`.
*   Return `components`.

## Sorting `nums` and Using Binary Search
This approach improves upon the brute-force method by optimizing the search within the `nums` array. By first sorting the `nums` array, we can use binary search instead of a linear scan to check for the presence of a node's value. This significantly reduces the time complexity of each lookup.
**Time:** O(M log M + N log M), where N is the number of nodes and M is the length of `nums`. Sorting takes O(M log M). The list traversal takes N steps, and each step involves one or two binary searches, each taking O(log M). · **Space:** O(log M) or O(M), depending on the implementation of the sorting algorithm. `Arrays.sort` in Java for primitives uses a dual-pivot quicksort, which has an average space complexity of O(log M) for the recursion stack.
**Pros:** Significantly faster than the brute-force approach for larger inputs.
**Cons:** The sorting step adds an initial overhead.; Still not the most optimal solution, as repeated binary searches are performed.
### Explanation
The overall logic remains the same: traverse the linked list and count the ends of components. The improvement comes from how we check if a value is in `nums`.

First, we sort the `nums` array. This allows us to perform lookups in logarithmic time.
We then iterate through the linked list node by node.
For each node, we use binary search on the sorted `nums` array to check if its value is present.
If the value is present, we again use binary search to check if the next node's value is present. If the next node is `null` or its value is not in `nums`, we've found the end of a component and increment our counter.
This method is faster than the brute-force approach because binary search (O(log M)) is much more efficient than linear scan (O(M)).

```java
import java.util.Arrays;

class Solution {
    private boolean binarySearch(int[] nums, int target) {
        return Arrays.binarySearch(nums, target) >= 0;
    }

    public int numComponents(ListNode head, int[] nums) {
        // Sort the nums array to enable binary search
        Arrays.sort(nums);
        
        int components = 0;
        ListNode current = head;
        while (current != null) {
            // Check if current node's value is in nums using binary search
            if (binarySearch(nums, current.val)) {
                // Check if it's the end of a component
                if (current.next == null || !binarySearch(nums, current.next.val)) {
                    components++;
                }
            }
            current = current.next;
        }
        return components;
    }
}
```
### Algorithm
*   Sort the input array `nums`. This takes O(M log M) time.
*   Initialize a counter `components` to 0.
*   Create a pointer `current` and set it to `head`.
*   Loop while `current` is not `null`:
    *   Use binary search to check if `current.val` exists in the sorted `nums` array.
    *   If `current.val` is in `nums`:
        *   Check if `current.next` is `null` or if `current.next.val` is not in `nums` (by another binary search).
        *   If either condition is true, increment `components`.
    *   Move to the next node: `current = current.next`.
*   Return `components`.

## Using a Hash Set for Efficient Lookups
This is the most efficient approach. We can convert the `nums` array into a `HashSet` to achieve constant-time average complexity for lookups. By doing this, checking if a node's value is part of a component becomes an O(1) operation.
**Time:** O(N + M), where N is the number of nodes and M is the length of `nums`. O(M) to build the set and O(N) to traverse the list with O(1) lookups. This is linear time. · **Space:** O(M), for storing the `nums` elements in the `HashSet`.
**Pros:** Most efficient time complexity.; The logic is straightforward after understanding the use of a hash set.
**Cons:** Uses extra space proportional to the size of `nums`, which might be a concern if memory is extremely limited.
### Explanation
The key to this optimization is to pre-process the `nums` array by storing all its elements in a `HashSet`. This data structure provides, on average, O(1) time complexity for insertion and search operations.

After building the set, we traverse the linked list just once.
For each node, we check if its value is in the `HashSet`.
We count a component whenever we encounter a node whose value is in the set, and its successor is either `null` or has a value that is *not* in the set. This marks the end of a sequence of connected nodes from `nums`.
This approach avoids the expensive repeated searches of the previous methods, leading to a linear time solution.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int numComponents(ListNode head, int[] nums) {
        // Step 1: Convert nums array to a HashSet for O(1) lookups.
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }
        
        int components = 0;
        ListNode current = head;
        
        // Step 2: Traverse the linked list.
        while (current != null) {
            // Step 3: Check if the current node is part of a component and if it's the end of one.
            if (numSet.contains(current.val)) {
                if (current.next == null || !numSet.contains(current.next.val)) {
                    components++;
                }
            }
            current = current.next;
        }
        
        return components;
    }
}
```
### Algorithm
*   Create a `HashSet` and add all elements from the `nums` array to it. This takes O(M) time.
*   Initialize a counter `components` to 0.
*   Create a pointer `current` and set it to `head`.
*   Loop while `current` is not `null`:
    *   Check if `current.val` exists in the `HashSet` (O(1) average time).
    *   If `current.val` is in the set:
        *   Check if `current.next` is `null` or if `current.next.val` is not in the `HashSet`.
        *   If either condition is true, it signifies the end of a component, so increment `components`.
    *   Move to the next node: `current = current.next`.
*   Return `components`.

# Solutions
### Java

```java
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public int numComponents ( ListNode head , int [] nums ) { int ans = 0 ; Set < Integer > s = new HashSet <>(); for ( int v : nums ) { s . add ( v ); } while ( head != null ) { while ( head != null && ! s . contains ( head . val )) { head = head . next ; } ans += head != null ? 1 : 0 ; while ( head != null && s . contains ( head . val )) { head = head . next ; } } return ans ; } }
```

### JavaScript

```javascript
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @param {number[]} nums * @return {number} */ var numComponents =
  function (head, nums) {
    const s = new Set(nums);
    let ans = 0;
    while (head) {
      while (head && !s.has(head.val)) {
        head = head.next;
      }
      ans += head != null;
      while (head && s.has(head.val)) {
        head = head.next;
      }
    }
    return ans;
  };

```

### CPP

```cpp
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: int numComponents ( ListNode * head , vector < int >& nums ) { unordered_set < int > s ( nums . begin (), nums . end ()); int ans = 0 ; while ( head ) { while ( head && ! s . count ( head -> val )) head = head -> next ; ans += head != nullptr ; while ( head && s . count ( head -> val )) head = head -> next ; } return ans ; } };
```

### Python

```python
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution : def numComponents ( self , head : Optional [ ListNode ], nums : List [ int ]) -> int : ans = 0 s = set ( nums ) while head : while head and head . val not in s : head = head . next ans += head is not None while head and head . val in s : head = head . next return ans
```