Linked List Components

Medium
2014.

Linked List Components

MediumLinked ListHash TableArrayGoogle

Linked List Components is a medium coding problem on arrays and hash table, asked in Google interviews.

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 n
  • 1 <= n <= 10^4
  • 0 <= Node.val < n
  • All the values Node.val are unique
  • 1 <= nums.length <= n
  • 0 <= nums[i] < n
  • All the values of nums are unique
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for singly-linked list (provided by the judge — do not redefine it):
 * 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) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 n
  • 1 <= n <= 10^4
  • 0 <= Node.val < n
  • All the values Node.val are unique
  • 1 <= nums.length <= n
  • 0 <= nums[i] < n
  • All the values of nums are unique

Hints for Linked List Components

  1. Hint 1

    Only the list's order matters; nums's own order is irrelevant. Put nums in a set for O(1) membership tests.

  2. Hint 2

    Walk the list. A component is a maximal run of nodes in the set.

  3. 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

  1. Insert all of nums into a hash set (or a boolean array indexed by value).
  2. Walk the list; for each node in the set, if node.next is null or node.next.val is not in the set, increase the count.
  3. 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 nums instead 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.includes inside 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 count

Java

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