NUHMAN.com

📘 Problem Statement

Given a singly linked list, implement an algorithm to randomly select a node from the list. The solution must work in O(n) time complexity, where n is the number of nodes in the list.

Design a solution to the following API:

python

class Solution:
    def __init__(self, head: ListNode):
        # Constructor to initialize the linked list.

    def getRandom(self) -> int:
        # Returns a random node's value from the linked list.

📚 Example:

python

Input:
head = [1, 2, 3]
solution = Solution(head)
solution.getRandom() # Returns a random value from the list [1, 2, 3]
solution.getRandom() # Returns a random value from the list [1, 2, 3]
solution.getRandom() # Returns a random value from the list [1, 2, 3]

🧠 Key Insight

To efficiently return a random node from a singly linked list, we can use Reservoir Sampling, a method that ensures every node in the list has an equal chance of being selected. This technique allows us to sample a random element from a stream (or a list) in a single pass.

Key Concepts:

• Reservoir Sampling: When iterating through the list, each node has a probability of being chosen. The probability remains constant throughout the traversal.

💡 Approach

The key to solving this problem is using the Reservoir Sampling algorithm. Here’s how we can implement it:

1. Initialize a counter to keep track of the number of nodes we have visited.
2. For each node we visit, select it with a probability of 1 / i, where i is the index of the current node (1-based).
3. If we select a node, we replace our current random node with this one.
4. Continue this process until we have traversed the entire list.
5. After the traversal, we return the value of the node that has been randomly selected.

This approach ensures that each node has an equal probability of being chosen.

🐍 Python Code

python

import random

class Solution:

    def __init__(self, head: ListNode):
        """
        Initialize the solution with the given linked list head.
        """
        self.head = head

    def getRandom(self) -> int:
        """
        Returns a random node's value.
        """
        current = self.head
        result = current.val
        count = 1

        while current:
            if random.randint(1, count) == count:
                result = current.val
            current = current.next
            count += 1
        
        return result

🔍 Step-by-Step Explanation

1. Initialization

python

def __init__(self, head: ListNode):
    self.head = head

• The __init__ function initializes the Solution class with the head of the linked list.

2. Get Random Value

python

def getRandom(self) -> int:
    current = self.head
    result = current.val
    count = 1

    while current:
        if random.randint(1, count) == count:
            result = current.val
        current = current.next
        count += 1

    return result

• current: We start at the head of the linked list and begin traversing.
• result: Initially, the first node's value is chosen as the random result.
• count: This counter keeps track of how many nodes we've seen so far.
• random selection: On each node, we generate a random integer between 1 and count. If the random integer equals count, we update the result with the current node's value. This ensures that each node has an equal probability of being selected.
• Traversal: We continue traversing the list, updating current to the next node and incrementing count.
• Return: Once the traversal is complete, we return the randomly selected node's value.

💡 Example Walkthrough

Example 1:

python

Input:
head = [1, 2, 3]
solution = Solution(head)
solution.getRandom() # Returns a random value from the list [1, 2, 3]
solution.getRandom() # Returns a random value from the list [1, 2, 3]
solution.getRandom() # Returns a random value from the list [1, 2, 3]

• First Call: We traverse the list:
• For node 1: count = 1, probability of selecting 1 = 1/1 = 100%. Set result = 1.
• For node 2: count = 2, probability of selecting 2 = 1/2.
• For node 3: count = 3, probability of selecting 3 = 1/3.
• A random selection will return a random value from [1, 2, 3].
• Second Call: The process is repeated, and the randomly selected value might change.
• Third Call: Similarly, a random value is chosen from [1, 2, 3].

⏱️ Time & Space Complexity

MetricComplexitygetRandomO(n)Space ComplexityO(1)

• Time Complexity: The getRandom method requires traversing the entire linked list, which takes O(n) time where n is the number of nodes in the list.
• Space Complexity: We are only using a few additional variables to store the current node, result, and count, so the space complexity is O(1).

🧵 Final Thoughts

LeetCode 382 demonstrates how to use Reservoir Sampling to efficiently pick a random element from a linked list. The solution works in O(n) time complexity, making it scalable for large linked lists. The method ensures that each element has an equal chance of being selected by maintaining a uniform probability distribution throughout the traversal.

This problem is a good example of how a single pass over the data structure, combined with careful probability management, can yield optimal solutions for random selection in data streams or linked lists.