LeetCode 817 - Linked List Components

The problem gives us a singly linked list where every node contains a unique integer value. We are also given an array nums, and every value in nums is guaranteed to appear somewhere in the linked list.

leetcodemediumarrayhash-tablelinked-list

LeetCode Problem 817

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Linked List

Solution

Problem Understanding

The problem gives us a singly linked list where every node contains a unique integer value. We are also given an array nums, and every value in nums is guaranteed to appear somewhere in the linked list.

We need to count how many connected components exist among the nodes whose values belong to nums.

Two nodes are considered connected if:

  1. Both node values are present in nums
  2. The two nodes appear consecutively in the linked list

This means we are not looking for arbitrary graph connectivity. Connectivity is determined entirely by adjacency in the linked list.

For example, suppose the linked list is:

0 -> 1 -> 2 -> 3

and:

nums = [0,1,3]

Nodes 0 and 1 are consecutive in the linked list and both belong to nums, so they form one component:

[0,1]

Node 3 is isolated because node 2 is not in nums, so 3 forms another component:

[3]

Therefore, the answer is 2.

The constraints are important:

  • The linked list length can be as large as 10^4
  • All node values are unique
  • All values in nums are unique

The uniqueness guarantee simplifies the problem significantly because we never need to worry about repeated values or ambiguous matches.

The main challenge is efficiently determining whether a node belongs to nums, and whether it continues an existing component or starts a new one.

Several edge cases are important:

  • nums may contain only one value
  • All linked list nodes may belong to nums
  • Every selected node may be isolated
  • Components may appear at the beginning or end of the linked list
  • Consecutive sequences may have different lengths

A naive implementation that repeatedly searches through nums linearly would become inefficient for large inputs.

Approaches

Brute Force Approach

A straightforward solution is to traverse the linked list and, for each node, check whether its value exists in nums using a linear scan.

Whenever we encounter a node that belongs to nums, we determine whether it starts a new component. A node starts a new component if:

  • It belongs to nums

  • The next node is either:

  • None, or

  • not present in nums

This logic works because each connected component ends exactly where adjacency breaks.

However, membership checking becomes expensive if implemented with repeated linear scans through nums.

If:

  • n is the linked list length
  • m is the size of nums

then each membership check costs O(m), and we perform up to O(n) checks, leading to O(n * m) time complexity.

With constraints up to 10^4, this is unnecessarily slow.

Optimal Approach

The key observation is that we only need fast membership testing.

A hash set provides O(1) average lookup time.

We first store all values from nums into a set. Then we traverse the linked list once.

For every node:

  • If the node value is in the set
  • And the next node is either absent or not in the set

then this node marks the end of a connected component, so we increment the answer.

This works because every component has exactly one ending node.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n * m) O(1) Linear search in nums for every node
Optimal O(n + m) O(m) Uses a hash set for constant time membership checks

Algorithm Walkthrough

  1. Create a hash set from nums.

We use a set because membership checks in a hash set are very fast, typically O(1) on average. This avoids repeatedly scanning the array. 2. Initialize a counter called components to 0.

This variable stores the number of connected components discovered so far. 3. Traverse the linked list from head to the end.

We inspect each node exactly once. 4. For each node, check whether its value belongs to the set.

If the value is not in the set, then this node is irrelevant to the problem and we move on. 5. If the current node belongs to the set, determine whether it is the end of a component.

A node ends a component if:

  • current.next is None, or
  • current.next.val is not in the set

This means the chain of connected nodes stops here. 6. If the current node ends a component, increment components.

Every component contributes exactly one ending node, so counting endings correctly counts components. 7. Continue until the traversal finishes. 8. Return components.

Why it works

A connected component in this problem is simply a maximal consecutive sequence of nodes whose values belong to nums.

Every such sequence has exactly one last node. By counting nodes where:

  • the current value belongs to nums, and
  • the next node does not continue the sequence,

we count every component exactly once.

No component is missed, and no component is counted multiple times.

Python Solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

from typing import List, Optional

class Solution:
    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:
        nums_set = set(nums)

        components = 0
        current = head

        while current:
            if current.val in nums_set:
                if current.next is None or current.next.val not in nums_set:
                    components += 1

            current = current.next

        return components

The implementation begins by converting nums into a hash set called nums_set. This gives constant time membership checks.

We then initialize components to store the number of connected components discovered during traversal.

The pointer current walks through the linked list node by node.

For every node, we first check whether its value belongs to the set. If it does not, we skip it because it cannot contribute to a component.

If the value does belong to the set, we determine whether this node marks the end of a connected sequence. That happens when either:

  • there is no next node, or
  • the next node's value is not in the set

Whenever this condition is true, we increment the component counter.

Finally, after traversing the entire list, we return the total number of components.

Go Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func numComponents(head *ListNode, nums []int) int {
    numsSet := make(map[int]bool)

    for _, num := range nums {
        numsSet[num] = true
    }

    components := 0
    current := head

    for current != nil {
        if numsSet[current.Val] {
            if current.Next == nil || !numsSet[current.Next.Val] {
                components++
            }
        }

        current = current.Next
    }

    return components
}

The Go implementation follows the same logic as the Python solution.

Since Go does not have a built in hash set type, we simulate one using map[int]bool.

The linked list traversal uses a pointer named current. Go uses nil instead of Python's None for missing pointers.

The rest of the logic is identical:

  • identify nodes that belong to nums
  • determine whether they terminate a component
  • increment the counter accordingly

No integer overflow concerns exist here because the maximum number of nodes is only 10^4.

Worked Examples

Example 1

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

The set becomes:

{0,1,3}

Linked list:

0 -> 1 -> 2 -> 3
Current Node In Set? Next In Set? Component Ends Here? Components
0 Yes Yes No 0
1 Yes No Yes 1
2 No Yes No 1
3 Yes No next node Yes 2

Final answer:

2

Example 2

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

The set becomes:

{0,1,3,4}

Linked list:

0 -> 1 -> 2 -> 3 -> 4
Current Node In Set? Next In Set? Component Ends Here? Components
0 Yes Yes No 0
1 Yes No Yes 1
2 No Yes No 1
3 Yes Yes No 1
4 Yes No next node Yes 2

Final answer:

2

Complexity Analysis

Measure Complexity Explanation
Time O(n + m) Building the set takes O(m), traversing the list takes O(n)
Space O(m) The hash set stores all values from nums

The linked list is traversed exactly once, and each set lookup is constant time on average.

The additional memory usage comes entirely from storing the nums values in the hash set.

Test Cases

# Helper classes and functions for testing

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build_list(values):
    dummy = ListNode()
    current = dummy

    for value in values:
        current.next = ListNode(value)
        current = current.next

    return dummy.next

class Solution:
    def numComponents(self, head, nums):
        nums_set = set(nums)

        components = 0
        current = head

        while current:
            if current.val in nums_set:
                if current.next is None or current.next.val not in nums_set:
                    components += 1

            current = current.next

        return components

solution = Solution()

# Example 1
head = build_list([0, 1, 2, 3])
assert solution.numComponents(head, [0, 1, 3]) == 2  # two separate components

# Example 2
head = build_list([0, 1, 2, 3, 4])
assert solution.numComponents(head, [0, 3, 1, 4]) == 2  # two groups

# Single node selected
head = build_list([5])
assert solution.numComponents(head, [5]) == 1  # single component

# Entire list selected
head = build_list([0, 1, 2, 3])
assert solution.numComponents(head, [0, 1, 2, 3]) == 1  # one large component

# No consecutive nodes
head = build_list([0, 1, 2, 3, 4])
assert solution.numComponents(head, [0, 2, 4]) == 3  # all isolated

# Component at beginning
head = build_list([0, 1, 2, 3])
assert solution.numComponents(head, [0, 1]) == 1  # component starts at head

# Component at end
head = build_list([0, 1, 2, 3])
assert solution.numComponents(head, [2, 3]) == 1  # component ends at tail

# Multiple mixed components
head = build_list([0, 1, 2, 3, 4, 5, 6])
assert solution.numComponents(head, [0, 1, 3, 5, 6]) == 3  # mixed structure

# Single isolated middle node
head = build_list([0, 1, 2, 3])
assert solution.numComponents(head, [2]) == 1  # isolated node

# Large consecutive block
head = build_list(list(range(10)))
assert solution.numComponents(head, [2, 3, 4, 5, 6]) == 1  # long component

Test Summary

Test Why
[0,1,2,3], [0,1,3] Validates basic multiple component detection
[0,1,2,3,4], [0,3,1,4] Ensures nonadjacent ordering in nums does not matter
Single node list Tests smallest valid input
Entire list selected Ensures one large component is counted correctly
Alternating selected nodes Tests multiple isolated components
Component at head Verifies handling of list beginning
Component at tail Verifies handling of list ending
Mixed component sizes Tests general correctness
Single middle node Ensures isolated nodes work properly
Large consecutive block Tests longer connected sequences

Edge Cases

Entire Linked List Forms One Component

If every node value belongs to nums, the entire linked list becomes one connected component.

For example:

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

A buggy implementation might incorrectly count every node as a separate component. Our solution avoids this by only counting nodes that terminate a component. In this case, only the final node satisfies that condition.

Every Selected Node Is Isolated

Consider:

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

No two selected nodes are adjacent. Therefore, every selected node forms its own component.

This case is important because naive adjacency handling may accidentally merge nonconsecutive nodes. Our implementation checks actual linked list adjacency through current.next, so isolated nodes are counted correctly.

Component Ends at the Tail

Consider:

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

The component reaches the last node of the list.

This is a common source of bugs because the final node has no next pointer. Our implementation explicitly checks:

current.next is None

which correctly identifies the end of the final component.