algoadvance

Leetcode 817. Linked List Components

Problem Statement:

We are given the head of a linked list and an array nums that is a subset of the elements in the linked list. The goal is to determine the number of connected components in the linked list that are formed by the elements in nums.

Clarifying Questions:

  1. What is meant by “connected components”?
    • A connected component is a maximal subset of nodes such that every two nodes are either directly connected or are connected through other nodes in the subset.
  2. Are there any constraints on the size of the linked list or nums array?
    • Yes, typically there’s a constraint on the length. For example:
      • The length of the linked list will be in the range [1, 10^4].
      • The size of the array nums will be in the range [1, 10^4].
      • The values must always be unique and present in the linked list.

Strategy:

  1. Create a Set of Nums:
    • Convert the array nums into a set to allow O(1) average time complexity for checking membership.
  2. Traverse the Linked List:
    • As we traverse the linked list, keep track of whether we are currently in a component by checking if a node’s value is in the set and whether it’s the start of a new component.
  3. Count Components:
    • Count transitions from a non-member node to a member node in nums.

Code:

Here’s how you can implement this strategy in C++:

#include <unordered_set>

// 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, std::vector<int>& nums) {
        // Create a set of nums for efficient lookup
        std::unordered_set<int> numSet(nums.begin(), nums.end());
        ListNode* current = head;
        int componentCount = 0;
        bool inComponent = false;

        // Traverse the linked list
        while (current != nullptr) {
            // Check if current node is in nums
            if (numSet.find(current->val) != numSet.end()) {
                // If we're not already in a component, we've found a new component
                if (!inComponent) {
                    componentCount++;
                    inComponent = true;
                }
            } else {
                // If current node is not in nums, we're not in a component
                inComponent = false;
            }
            current = current->next;
        }
        return componentCount;
    }
};

Time Complexity:

Space Complexity:

Thus, this approach is efficient and well-suited for the problem constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI