Linked List Components — HashSet Membership Check

Sanjeev SharmaSanjeev Sharma
1 min read

Advertisement

Problem 241 · Linked List Components

Difficulty: Medium · Pattern: HashSet Lookup

Count components: consecutive sequences of nodes all present in nums array.

Solutions

# Python
def numComponents(head, nums):
    s = set(nums)
    ans = 0; in_comp = False
    while head:
        if head.val in s:
            if not in_comp: ans += 1; in_comp = True
        else:
            in_comp = False
        head = head.next
    return ans
// Java
public int numComponents(ListNode head, int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int n : nums) set.add(n);
    int ans = 0; boolean inComp = false;
    while (head != null) {
        if (set.contains(head.val)) { if (!inComp) { ans++; inComp = true; } }
        else inComp = false;
        head = head.next;
    }
    return ans;
}

Complexity

  • Time: O(n + k) where k = nums length
  • Space: O(k)

Advertisement

Sanjeev Sharma

Written by

Sanjeev Sharma

Full Stack Engineer · E-mopro