Linked List Components — HashSet Membership Check
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