Linked List Components solution and explanation
Google
9 more videos on this problem
817. Linked List Components | LEETCODE MEDIUM | LINKED LISTcode Explainer · 5:20 · 4K views
花花酱 LeetCode 817. Linked List Components - 刷题找工作 EP181Hua Hua · 11:41 · 2K views
Leetcode-817: Linked list components ( Using Event trigger algorithm / Event termination algorithm )Kumar Sanjeev · 4:52 · 2K views
817. Linked List Components (Leetcode Medium)Programming Live with Larry · 18:14 · 1K views
PQ1. | 817. Linked List Components | Linked ListCodeSpace · 9:25 · 810 views
LEETCODE - 817 | Linked List ComponentsSatyam Kumar · 8:16 · 374 views
817. Linked List Components || leetcodeJust ASMR · 5:26 · 352 views
LeetCode 817 | Linked List Components | Detailed Explanation + Java SolutionCode Kage · 6:45 · 194 views
Leetcode 817. Linked List Components (Linked List)LetsCode · 4:57 · 188 views
(C#)LeetCode 817 Linked List Componentszongwu yang · 4:07 · 173 views
The problem
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.
Approach overview
Problem Overview: You are given the head of a linked list and an array nums containing a subset of node values. A component is a group of consecutive nodes in the list where every node value appears in nums. The task is to count how many such connected components exist.
Approach 1: Set for Quick Lookup (O(n) time, O(k) space)
The cleanest solution uses a hash table (set) to quickly check whether a node value exists in nums. Insert all values from nums into a set, then iterate through the linked list once. When the current node value exists in the set and the next node either does not exist in the set or is null, you found the end of a component. Increment the counter. The key insight: each component is counted exactly once at its boundary (the last node belonging to that component). Membership checks become O(1) due to hashing, so the full traversal remains linear. This approach is straightforward and performs well even when nums is large.
Approach 2: Two-Pass on Linked List without Extra Space (O(n * k) time, O(1) space)
If you want to avoid additional memory, skip the hash set and work directly with the array nums. Traverse the linked list and determine membership by scanning the nums array each time you need to check if a value belongs to the subset. Similar to the set approach, you detect a component when the current node value exists in nums and the next node either does not belong to nums or is null. Because each membership test scans the array, the complexity becomes O(n * k), where k is the size of nums. The benefit is constant extra space. This works when nums is small or memory usage is tightly constrained.
Recommended for interviews: The hash set approach is what most interviewers expect. It demonstrates that you recognize the repeated membership check and optimize it with constant-time lookups. Mentioning the no-extra-space variation shows awareness of trade-offs, but the O(n) hash set solution best balances clarity and efficiency.
Approach 1: Set for Quick Lookup
This approach leverages a set data structure to quickly determine if a node from the linked list is part of the 'nums' array. We traverse the linked list and use the set to track connected components. If a node is found in the set and it is not part of an ongoing component, we start a new component and continue the counter until we find a break in connectivity.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def numComponents(self, head: ListNode, nums: List[int]) -> int:
nums_set = set(nums)
count = 0
in_component = False
current = head
while current:
if current.val in nums_set:
if not in_component:
count += 1
in_component = True
else:
in_component = False
current = current.next
return countimport java.util.HashSet;
import java.util.Set;
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; next = null; }
}
public class Solution {
public int numComponents(ListNode head, int[] nums) {
Set<Integer> numSet = new HashSet<>();
for (int num : nums) {
numSet.add(num);
}
int count = 0;
boolean inComponent = false;
while (head != null) {
if (numSet.contains(head.val)) {
if (!inComponent) {
count++;
inComponent = true;
}
} else {
inComponent = false;
}
head = head.next;
}
return count;
}
}#include <unordered_set>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
int numComponents(ListNode* head, vector<int>& nums) {
unordered_set<int> numSet(nums.begin(), nums.end());
int count = 0;
bool in_component = false;
while (head) {
if (numSet.count(head->val)) {
if (!in_component) {
count++;
in_component = true;
}
} else {
in_component = false;
}
head = head->next;
}
return count;
}function ListNode(val, next) {
this.val = val === undefined ? 0 : val;
this.next = next === undefined ? null : next;
}
var numComponents = function(head, nums) {
const numSet = new Set(nums);
let count = 0;
let inComponent = false;
while (head) {
if (numSet.has(head.val)) {
if (!inComponent) {
count++;
inComponent = true;
}
} else {
inComponent = false;
}
head = head.next;
}
return count;
};#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
struct ListNode {
int val;
struct ListNode *next;
};
bool hashset_contains(int* hashset, int size, int key) {
return hashset[key];
}
int numComponents(struct ListNode* head, int* nums, int numsSize) {
int* hashset = (int*)calloc(10000, sizeof(int));
for (int i = 0; i < numsSize; i++) {
hashset[nums[i]] = 1;
}
int count = 0;
bool in_component = false;
struct ListNode* current = head;
while (current) {
if (hashset_contains(hashset, 10000, current->val)) {
if (!in_component) {
count++;
in_component = true;
}
} else {
in_component = false;
}
current = current->next;
}
free(hashset);
return count;
}using System;
using System.Collections.Generic;
public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) { val = x; next = null; }
}
public class Solution {
public int NumComponents(ListNode head, int[] nums) {
HashSet<int> numSet = new HashSet<int>(nums);
int count = 0;
bool inComponent = false;
while (head != null) {
if (numSet.Contains(head.val)) {
if (!inComponent) {
count++;
inComponent = true;
}
} else {
inComponent = false;
}
head = head.next;
}
return count;
}
}This Python solution uses a set to store 'nums'. We iterate through the linked list, checking for start of a new component by checking if the current node is in 'nums' and whether the previous node wasn't in 'nums'. We manage the count accordingly — ensuring we only start a count when entering a new sequence.
Time Complexity: O(n + m), where n is the length of the linked list, and m is the length of 'nums'.
Space Complexity: O(m) due to nums set.
Approach 2: Two-Pass on Linked List without Extra Space (Optimized for nums)
This alternative approach first marks the initial position of all nodes existing in 'nums' by setting their value offsets to a special marker. In a second pass, it counts connected sequences between marked nodes. This enables direct marking of active components without extra space dedicated to hashes or sets but works best only when the linked list structure is such that in-place marking is feasible.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def numComponents(self, head: ListNode, nums: List[int]) -> int:
set_reference = set(nums)
current = head
count = 0
while current:
if current.val in set_reference:
if not (current.next and current.next.val in set_reference):
count += 1
current = current.next
return count#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
struct ListNode {
int val;
struct ListNode *next;
};
int numComponents(struct ListNode* head, int* nums, int numsSize) {
struct ListNode* current = head;
bool in_component = false;
int count = 0;
while (current) {
bool found = false;
for (int i = 0; i < numsSize; i++) {
if (current->val == nums[i]) {
found = true;
break;
}
}
if (found) {
if (!in_component) {
count++;
in_component = true;
}
} else {
in_component = false;
}
current = current->next;
}
return count;
}This Python implementation deviates computations assuming marked places spotted pre-loop process to enable next-awareness without verbose tracking state holdings. This presumes single function iteration without state capture apart from 'count,' optimizing based on node relevancy. Active passes insert boundaries constructed directly from proximity discoveries.
Time Complexity: O(n), driven solely by singular logical testimonies where nodes are set-synchronized.
Space Complexity: O(m), matching reference size still encapsulated for same-session tracking without further buffer arrangement necessity.
Approach 3: Default Approach
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function numComponents(head: ListNode | null, nums: number[]): number {
const set = new Set<number>(nums);
let res = 0;
let cur = head;
let inSet = false;
while (cur != null) {
if (set.has(cur.val)) {
if (!inSet) {
inSet = true;
res++;
}
} else {
inSet = false;
}
cur = cur.next;
}
return res;
}/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func numComponents(head *ListNode, nums []int) int {
s := map[int]bool{}
for _, v := range nums {
s[v] = true
}
ans := 0
for head != nil {
for head != nil && !s[head.Val] {
head = head.Next
}
if head != nil {
ans++
}
for head != nil && s[head.Val] {
head = head.Next
}
}
return ans
}// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
// pub val: i32,
// pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
// #[inline]
// fn new(val: i32) -> Self {
// ListNode {
// next: None,
// val
// }
// }
// }
use std::collections::HashSet;
impl Solution {
pub fn num_components(head: Option<Box<ListNode>>, nums: Vec<i32>) -> i32 {
let set = nums.into_iter().collect::<HashSet<i32>>();
let mut res = 0;
let mut in_set = false;
let mut cur = &head;
while let Some(node) = cur {
if set.contains(&node.val) {
if !in_set {
in_set = true;
res += 1;
}
} else {
in_set = false;
}
cur = &node.next;
}
res
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Set for Quick Lookup | Time Complexity: O(n + m), where n is the length of the linked list, and m is the length of 'nums'. |
| Two-Pass on Linked List without Extra Space (Optimized for nums) | Time Complexity: O(n), driven solely by singular logical testimonies where nodes are set-synchronized. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Set for Quick Lookup | O(n + k) | O(k) | General case. Fast membership checks using a hash set. |
| Two-Pass without Extra Space | O(n * k) | O(1) | Useful when memory is constrained or nums size is very small. |
Frequently asked questions
Is Linked List Components easy or hard?
Linked List Components is considered a medium-level problem on LeetCode with an acceptance rate around 58%. The challenge lies in recognizing component boundaries and using a hash set to avoid repeated membership scans.
Linked List Components Python/Java solution
Python and Java solutions typically build a HashSet or set from nums and iterate through the linked list. When a node is in the set and the next node is not, increment the component count. This implementation runs in O(n) time and is the standard interview solution.
How to solve Linked List Components in O(n)?
Insert all values from nums into a hash set. Traverse the linked list and check if the current node value is in the set while the next node value is not. Each such boundary marks the end of a component, so increment the counter. Because each node is processed once, the total complexity is linear.
What is the best approach for Linked List Components?
The most efficient approach uses a hash set to store all values from nums and then traverses the linked list once. When a node value is in the set and the next node is not, you count a component boundary. This runs in O(n) time with O(k) extra space, where k is the size of nums.
Is Linked List Components asked at Google/Amazon/Meta?
Linked list and hash set combination problems appear frequently in interviews at companies like Amazon, Google, and Meta. This problem tests recognition of connected segments and efficient membership lookup using hashing.
What data structure is used in Linked List Components?
The primary data structure used is a hash set for constant-time membership checks. The problem also requires traversal of a singly linked list and understanding how consecutive nodes form components.
What is the time complexity of Linked List Components?
The optimal solution runs in O(n + k) time, where n is the number of nodes in the linked list and k is the size of nums. Each node is visited once and set membership checks take O(1) on average.