Linked List Components
MedPrompt
You are given the head of a linked list containing unique integer values and an integer array nums that is a subset of the linked list values.
Return the number of connected components in nums where two values are connected if they appear consecutively in the linked list.
Example 1:
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.Example 2:
Input: head = [0,1,2,3,4], nums = [0,3,1,4]
Output: 2
Explanation: 0 and 1 are connected, 3 and 4 are connected, so [0, 1] and [3, 4] are the two connected components.
Constraints:
- The number of nodes in the linked list is
n. 1 <= n <= 1040 <= Node.val < n- All the values
Node.valare unique. 1 <= nums.length <= n0 <= nums[i] < n- All the values of
numsare unique.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves iterating through the linked list. For each node, we check if its value and its next node's value are present in the nums array by performing a linear scan through nums. We count a component every time we find a node that is in nums but its next node is either null or not in nums.
Algorithm
- Initialize a counter
componentsto 0. - Create a pointer
currentand set it tohead. - Loop while
currentis notnull:- Linearly scan the
numsarray to check ifcurrent.valexists. - If
current.valis innums:- Check if
current.nextisnullor ifcurrent.next.valis not innums(by another linear scan). - If either condition is true, increment
components.
- Check if
- Move to the next node:
current = current.next.
- Linearly scan the
- Return
components.
Walkthrough
The core idea is to identify the end of each connected component. A component ends when a node curr has its value in nums, but the subsequent node curr.next either doesn't exist (i.e., curr is the tail) or its value is not in nums.
We traverse the linked list from the head.
For each node, we first check if its value is in the nums array. This check is done by iterating through the entire nums array.
If the current node's value is found in nums, we then check if it's the end of a component. This is true if the next node is null or the next node's value is not in nums (which requires another linear scan of nums).
If it's the end of a component, we increment our component counter.
We continue this process until we have traversed the entire linked list.
class Solution { private boolean contains(int[] nums, int target) { for (int num : nums) { if (num == target) { return true; } } return false; } public int numComponents(ListNode head, int[] nums) { int components = 0; ListNode current = head; while (current != null) { // Check if current node's value is in nums if (contains(nums, current.val)) { // Check if it's the end of a component if (current.next == null || !contains(nums, current.next.val)) { components++; } } current = current.next; } return components; }}Complexity
Time
O(N * M), where N is the number of nodes in the linked list and M is the length of the `nums` array. For each of the N nodes, we may perform up to two linear scans of the `nums` array, each taking O(M) time.
Space
O(1), as we only use a few variables to store the count and the current node pointer.
Trade-offs
Pros
Simple to understand and implement.
Very low memory usage.
Cons
Highly inefficient for large inputs, likely to result in a "Time Limit Exceeded" error on most platforms.
The repeated linear scans of the
numsarray are the bottleneck.
This approach improves upon the brute-force method by optimizing the search within the nums array. By first sorting the nums array, we can use binary search instead of a linear scan to check for the presence of a node's value. This significantly reduces the time complexity of each lookup.
Algorithm
- Sort the input array
nums. This takes O(M log M) time. - Initialize a counter
componentsto 0. - Create a pointer
currentand set it tohead. - Loop while
currentis notnull:- Use binary search to check if
current.valexists in the sortednumsarray. - If
current.valis innums:- Check if
current.nextisnullor ifcurrent.next.valis not innums(by another binary search). - If either condition is true, increment
components.
- Check if
- Move to the next node:
current = current.next.
- Use binary search to check if
- Return
components.
Walkthrough
The overall logic remains the same: traverse the linked list and count the ends of components. The improvement comes from how we check if a value is in nums.
First, we sort the nums array. This allows us to perform lookups in logarithmic time.
We then iterate through the linked list node by node.
For each node, we use binary search on the sorted nums array to check if its value is present.
If the value is present, we again use binary search to check if the next node's value is present. If the next node is null or its value is not in nums, we've found the end of a component and increment our counter.
This method is faster than the brute-force approach because binary search (O(log M)) is much more efficient than linear scan (O(M)).
import java.util.Arrays; class Solution { private boolean binarySearch(int[] nums, int target) { return Arrays.binarySearch(nums, target) >= 0; } public int numComponents(ListNode head, int[] nums) { // Sort the nums array to enable binary search Arrays.sort(nums); int components = 0; ListNode current = head; while (current != null) { // Check if current node's value is in nums using binary search if (binarySearch(nums, current.val)) { // Check if it's the end of a component if (current.next == null || !binarySearch(nums, current.next.val)) { components++; } } current = current.next; } return components; }}Complexity
Time
O(M log M + N log M), where N is the number of nodes and M is the length of `nums`. Sorting takes O(M log M). The list traversal takes N steps, and each step involves one or two binary searches, each taking O(log M).
Space
O(log M) or O(M), depending on the implementation of the sorting algorithm. `Arrays.sort` in Java for primitives uses a dual-pivot quicksort, which has an average space complexity of O(log M) for the recursion stack.
Trade-offs
Pros
Significantly faster than the brute-force approach for larger inputs.
Cons
The sorting step adds an initial overhead.
Still not the most optimal solution, as repeated binary searches are performed.
This is the most efficient approach. We can convert the nums array into a HashSet to achieve constant-time average complexity for lookups. By doing this, checking if a node's value is part of a component becomes an O(1) operation.
Algorithm
- Create a
HashSetand add all elements from thenumsarray to it. This takes O(M) time. - Initialize a counter
componentsto 0. - Create a pointer
currentand set it tohead. - Loop while
currentis notnull:- Check if
current.valexists in theHashSet(O(1) average time). - If
current.valis in the set:- Check if
current.nextisnullor ifcurrent.next.valis not in theHashSet. - If either condition is true, it signifies the end of a component, so increment
components.
- Check if
- Move to the next node:
current = current.next.
- Check if
- Return
components.
Walkthrough
The key to this optimization is to pre-process the nums array by storing all its elements in a HashSet. This data structure provides, on average, O(1) time complexity for insertion and search operations.
After building the set, we traverse the linked list just once.
For each node, we check if its value is in the HashSet.
We count a component whenever we encounter a node whose value is in the set, and its successor is either null or has a value that is not in the set. This marks the end of a sequence of connected nodes from nums.
This approach avoids the expensive repeated searches of the previous methods, leading to a linear time solution.
import java.util.HashSet;import java.util.Set; class Solution { public int numComponents(ListNode head, int[] nums) { // Step 1: Convert nums array to a HashSet for O(1) lookups. Set<Integer> numSet = new HashSet<>(); for (int num : nums) { numSet.add(num); } int components = 0; ListNode current = head; // Step 2: Traverse the linked list. while (current != null) { // Step 3: Check if the current node is part of a component and if it's the end of one. if (numSet.contains(current.val)) { if (current.next == null || !numSet.contains(current.next.val)) { components++; } } current = current.next; } return components; }}Complexity
Time
O(N + M), where N is the number of nodes and M is the length of `nums`. O(M) to build the set and O(N) to traverse the list with O(1) lookups. This is linear time.
Space
O(M), for storing the `nums` elements in the `HashSet`.
Trade-offs
Pros
Most efficient time complexity.
The logic is straightforward after understanding the use of a hash set.
Cons
Uses extra space proportional to the size of
nums, which might be a concern if memory is extremely limited.
Solutions
Solution
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public int numComponents ( ListNode head , int [] nums ) { int ans = 0 ; Set < Integer > s = new HashSet <>(); for ( int v : nums ) { s . add ( v ); } while ( head != null ) { while ( head != null && ! s . contains ( head . val )) { head = head . next ; } ans += head != null ? 1 : 0 ; while ( head != null && s . contains ( head . val )) { head = head . next ; } } return ans ; } }/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @param {number[]} nums * @return {number} */ var numComponents = function (head, nums) { const s = new Set(nums); let ans = 0; while (head) { while (head && !s.has(head.val)) { head = head.next; } ans += head != null; while (head && s.has(head.val)) { head = head.next; } } return ans; };/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: int numComponents ( ListNode * head , vector < int >& nums ) { unordered_set < int > s ( nums . begin (), nums . end ()); int ans = 0 ; while ( head ) { while ( head && ! s . count ( head -> val )) head = head -> next ; ans += head != nullptr ; while ( head && s . count ( head -> val )) head = head -> next ; } return ans ; } };# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution : def numComponents ( self , head : Optional [ ListNode ], nums : List [ int ]) -> int : ans = 0 s = set ( nums ) while head : while head and head . val not in s : head = head . next ans += head is not None while head and head . val in s : head = head . next return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.