富良野

LeetCode 382. Linked List Random Node

LeetCode Notes [75]: Brief explanation for Reservoir Sampling

Problem

https://leetcode.com/problems/linked-list-random-node/description/

Intuition

Reservoir sampling

Let first item in the list be the candidate result to return.
Loop through all nodes in the linked list, for i-th linked list item:

1. Sample a random variable x from [0, 1] uniformly.
2. If x falls between [0, 1/i], let the i-th item replace the candidate.

Proof

Let’s proof by math induction step by step:

Base Case

Get John Lu’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

For n=1, we must select the first item. The probability will be 1/n = 1/1 = 1.

Assume

For n=k, the probability for sampling the item will be 1/k.

It follows that:

• For, n = k + 1, the probability for sampling the k+1-th item is 1/(k+1).
• The probability for sampling the first item will be (1–1/(k+1)) * 1/k = 1/(k+1). (Not selecting the last item and replace the candidate by the first item)
• Same probability for sampling the items for n≥2.

Conclusion

Since the base case and the induction step have been proved as true, by mathematical induction the statement holds for every n≥1.

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

Implementation

import random

class Solution:

    def __init__(self, head: Optional[ListNode]):
        self.head = head

    def getRandom(self) -> int:
        result = self.head.val
        count = 0
        pointer = self.head
        while pointer is not None:
            count += 1
            dice = random.random()
            if dice <= 1 / count:
                result = pointer.val
            pointer = pointer.next
        return result