We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Linked List Components

Number: 835

Difficulty: Medium

Paid? No

Companies: Amazon, Google

Problem Description

Given the head of a linked list with unique integer values and an integer array nums (which is a subset of the linked list values), determine the number of connected components. A component is defined as a maximal subset of nodes in the linked list such that every node in the subset is in nums and nodes are consecutive in the linked list.

Key Insights

  • Convert the nums array into a set for O(1) membership checking.
  • Traverse the linked list once while detecting the end of a component.
  • A component ends when a node’s value belongs to nums and either the next node is null or its value is not in nums.
  • The problem is solved with a single pass through the linked list.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the linked list because we traverse all nodes. Space Complexity: O(m), where m is the size of nums (in worst-case m can be n) for storing the set.

Solution

We use a set to quickly check if a node's value is in the nums array. As we traverse the linked list, we check if the current node is part of a component. If it is and either it is the last node or the next node does not belong to the set, we increment our component count. This approach ensures we detect the end of each connected component in a single pass.

Code Solutions

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

def numComponents(head, nums):
    # Create a set from nums for O(1) lookups
    nums_set = set(nums)
    components = 0
    current = head
    
    # Traverse the linked list
    while current:
        # If the current node is in nums set and either it's the last node
        # or the next node is not in the nums set, it marks the end of a component
        if current.val in nums_set and (current.next is None or current.next.val not in nums_set):
            components += 1
        current = current.next

    return components
← Back to All Questions