algoadvance

Leetcode 817. Linked List Components

Problem Statement

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. The task is to return the number of connected components in the linked list that are formed by the nodes from nums.

A connected component of the linked list is a subset of nodes such that:

• Every node in the subset appears in nums.
• The nodes in the subset are all adjacent in the original linked list.

Clarifying Questions

1. Input Format:
   • head: The head of the linked list.
   • nums: An array containing some values from the linked list.
2. Output:
   • Return an integer representing the number of connected components.
3. Constraints:
   • The number of nodes in the linked list is in the range [1, 10^4].
   • 1 <= Node.val <= 10^4
   • All the values inside the linked list are unique.
   • 1 <= nums.length <= 10^4
   • All nums values are unique.
   • nums is a subset of values in the linked list.

Strategy

1. Use a Set:
   • We will store all elements of nums in a set for O(1) average-time complexity look-up.
2. Traverse the Linked List:
   • While traversing the linked list, check if the current node’s value is in the set.
   • Count a new connected component whenever we encounter the start of a new component (i.e., a node whose value is in the set but the previous node’s value was not or it is the start of the list).
3. Count Components:
   • Increment the component count at the start of each new component.

Code

Here’s the Java code to accomplish this:

import java.util.HashSet;
import java.util.Set;

public class Solution {
    public int numComponents(ListNode head, int[] nums) {
        Set<Integer> numSet = new HashSet<>();
        // Add all elements of nums into the set
        for (int num : nums) {
            numSet.add(num);
        }
        
        int components = 0;
        boolean inComponent = false;
        
        // Traverse the linked list
        ListNode current = head;
        while (current != null) {
            if (numSet.contains(current.val)) {
                if (!inComponent) {
                    // We found the start of a new component
                    components++;
                    inComponent = true;
                }
            } else {
                // End of the current component
                inComponent = false;
            }
            current = current.next;
        }
        
        return components;
    }
}

Time Complexity

• Time Complexity:
  • Building the set from nums: O(N) where N is the length of nums.
  • Traversing the linked list: O(L) where L is the number of nodes in the linked list.

  Thus, the overall time complexity is O(N + L).

• Space Complexity:
  • The space complexity is O(N) due to the storage of elements from nums in the set.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?