#817

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Linked List Components

Count the number of connected components in a linked list subset using array scanning and hash table lookups efficiently.

array hash table linked list

Problem Statement

Given the head of a linked list containing unique integers and an array nums representing a subset of these values, identify how many connected components exist. Two values are considered connected if they appear consecutively in the linked list and are both present in nums.

For example, with head = [0,1,2,3] and nums = [0,1,3], the linked list forms two connected components: [0,1] and [3]. Return the total number of such connected components for the given input.

Examples

Example 1

Input: head = [0,1,2,3], nums = [0,1,3]

Output: 2

0 and 1 are connected, so [0, 1] and [3] are the two connected components.

Example 2

Input: head = [0,1,2,3,4], nums = [0,3,1,4]

Output: 2

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.

Solution Approach

Convert nums to a hash set

Store all elements of nums in a hash set to allow O(1) membership checks while scanning the linked list. This ensures you can quickly determine whether each node belongs to a component.

Scan linked list and count components

Iterate through the linked list and increment the component count whenever you find a node in nums that is not immediately preceded by another node in nums. This identifies the start of each connected component.

Handle edge cases

Ensure you correctly process the last node and isolated nodes. If a node in nums has no adjacent nodes in nums, it still counts as a single component. This avoids off-by-one errors in counting.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n + m) where n is the length of the linked list and m is the length of nums, because each node is visited once and hash lookups are constant time. Space complexity is O(m) to store the hash set of nums.

What Interviewers Usually Probe

Expecting clear identification of consecutive sequences in the linked list.
Looking for efficient use of hash table to check membership instead of nested loops.
Watching for correct handling of isolated nodes versus multi-node components.

Common Pitfalls or Variants

Common pitfalls

Using nested loops to compare each node with nums, causing O(n*m) time complexity.
Failing to increment the count correctly when a sequence ends or a single node is a component.
Ignoring edge nodes or empty nums arrays leading to incorrect component counts.

Follow-up variants

Counting connected components in a linked list with duplicate values allowed.
Returning the actual sublists forming each connected component rather than just the count.
Extending the problem to a doubly linked list and detecting bi-directional connectivity.

FAQ

What is the most efficient approach for Linked List Components?

Use a hash set to store nums and scan the linked list once, counting new components when a node is in nums but the previous node is not.

How does the array scanning plus hash lookup pattern apply here?

It lets you iterate through the linked list and check membership in constant time, avoiding nested loops and reducing complexity.

Can a single node in nums be a connected component?

Yes, any node in nums with no consecutive neighbors in nums forms its own single-node component.

What if nums contains all linked list nodes?

The entire linked list becomes a single connected component because all nodes are consecutive in nums.

How do I handle the last node in the list?

Check if it is in nums and whether the previous node is not in nums; if so, increment the component count appropriately.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

# 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

Continue Practicing

#706 design hashmap #705 design hashset #815 bus routes