algoadvance

817. Linked List Components

You are given the head of a linked list containing unique integer values and an integer array nums that contains a subset of values in the linked list.

Return the number of connected components in nums where two values are connected if they appeared consecutively in the linked list.

Example:

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.

Clarifying Questions

  1. What does “connected components” mean in this context? It means consecutive sequences in the original linked list where every element in the sequence is part of the nums array.

  2. Can nums be empty? No, according to the problem, nums will always have at least one element.

  3. What should be returned if no elements in nums appear as consecutive in the linked list? In that case, every element in nums will be its own connected component.

Strategy

To solve this problem, we can use the following steps:

  1. Convert nums into a set for O(1) average-time complexity for membership checking.
  2. Traverse the linked list while maintaining a flag to track if we are in a connected component.
  3. If the current value is in nums and we are not currently in a connected component, increment the count of components and set the flag indicating a connection.
  4. If the current value is not in nums, reset the flag indicating the end of a connection.

Code

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

def numComponents(head: ListNode, nums: List[int]) -> int:
    nums_set = set(nums)  # Convert nums to a set for O(1) lookups
    current = head
    in_component = False
    count = 0

    while current:
        if current.val in nums_set:
            if not in_component:
                count += 1
                in_component = True
        else:
            in_component = False
        current = current.next

    return count

# Example usage
# Constructing the linked list: 0 -> 1 -> 2 -> 3
head = ListNode(0)
head.next = ListNode(1)
head.next.next = ListNode(2)
head.next.next.next = ListNode(3)

# nums array
nums = [0, 1, 3]

# Call the function
print(numComponents(head, nums))  # Output: 2

Time Complexity

The time complexity of the solution is O(N), where N is the number of nodes in the linked list. This is because we traverse the linked list exactly once. The space complexity is O(M), where M is the number of elements in nums, primarily due to storing the elements in a set for fast lookup.

Try our interview co-pilot at AlgoAdvance.com