817. Linked List Components

1. Description

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.

2. Example

Example 1:
Input:
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.

Example 2:
Input:
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.

3. 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.

4. Solutions

My Accepted Solution

n is the number of nodes in i_head, range = 10000
Time complexity: O(n)
Space complexity: O(range)

class Solution {
public:
    // int numComponents(ListNode* head, vector<int>& G)
    int numComponents(const ListNode* i_head, const vector<int>& i_groups) {
        array<int, 10000> nodeOccurTimes{}; // the range is 10000, array is faster than unordered_map
        for (auto node : i_groups) {
            ++nodeOccurTimes[node];
        }

        int count = 0;
        for (auto iter = i_head; iter; iter = iter->next) {
            if (nodeOccurTimes[iter->val] > 0 &&
                (!iter->next || nodeOccurTimes[iter->next->val] == 0)) {
                ++count;
            }
        }

        return count;
    }
};