Linked List Components — Solution in Python, Java & C++
Linked List Components solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Google.
Linked List Components is a medium coding problem on arrays and hash table, asked in Google interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table
- Asked at: Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given the head of a singly linked list of n nodes whose values are the distinct integers 0 to n - 1 (in some order), and an array nums holding some of those values, each at most once.
Two values of nums are connected if their nodes are adjacent in the list. Return the number of connected components of nums — the number of maximal runs of consecutive list nodes whose values all belong to nums.
Example 1
Input: head = [0,1,2,3], nums = [0,1,3]
Output: 2
Explanation: 0 and 1 are adjacent and form one component; 3 is alone.
Example 2
Input: head = [0,1,2,3,4], nums = [0,3,1,4]
Output: 2
Explanation: The runs are [0,1] and [3,4].
Example 3
Input: head = [2,0,1], nums = [1]
Output: 1
Constraints
The number of nodes in the list is n1 <= n <= 10^40 <= Node.val < nAll the values Node.val are unique1 <= nums.length <= n0 <= nums[i] < nAll the values of nums are unique
Hints for Linked List Components
Hint 1
Only the list's order matters;
nums's own order is irrelevant. Putnumsin a set for O(1) membership tests.Hint 2
Walk the list. A component is a maximal run of nodes in the set.
Hint 3
Count the nodes that end a run: a node in the set whose next node is missing or not in the set.
How to solve Linked List Components
A component is a maximal run of set members along the list, and every run has exactly one last node. So count the nodes that are in the set but whose successor is not.
Approach
- Insert all of
numsinto a hash set (or a boolean array indexed by value). - Walk the list; for each node in the set, if
node.nextis null ornode.next.valis not in the set, increase the count. - Return the count.
Why it works
Runs are disjoint, and each one ends at exactly one node — the member whose successor is not a member (or does not exist). Counting those nodes therefore counts each run exactly once.
Complexity
- Time —
O(n + |nums|) - Space —
O(|nums|) for the set
Pitfalls
- Counting nodes in
numsinstead of runs overcounts adjacent members. - Adjacency is about list neighbours, not consecutive integers: 3 and 4 are connected only if their nodes touch.
- Checking
nums.includesinside the loop makes it O(n·|nums|).
Reference solution
Python
from typing import List, Optional
def numComponents(head: Optional[ListNode], nums: List[int]) -> int:
members = set(nums)
count = 0
while head:
if head.val in members and (head.next is None or head.next.val not in members):
count += 1
head = head.next
return countJava
public static int numComponents(ListNode head, int[] nums) {
java.util.HashSet<Integer> members = new java.util.HashSet<>();
for (int x : nums) members.add(x);
int count = 0;
for (; head != null; head = head.next) {
if (members.contains(head.val) && (head.next == null || !members.contains(head.next.val))) count++;
}
return count;
}C++
int numComponents(ListNode* head, vector<int>& nums) {
unordered_set<int> members(nums.begin(), nums.end());
int count = 0;
for (; head; head = head->next) {
if (members.count(head->val) && (!head->next || !members.count(head->next->val))) count++;
}
return count;
}JavaScript
var numComponents = function(head, nums) {
var members = new Set(nums), count = 0;
for (; head !== null; head = head.next) {
if (members.has(head.val) && (head.next === null || !members.has(head.next.val))) count++;
}
return count;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets