382.linked-list-random-node.md

382. Linked List Random Node

Hints

• Think about how to select a random node without knowing the total size in advance
• Consider how to maintain equal probability for each node
• Remember that we can only traverse the list once

Breakdowns

1. Random Selection

   • How to select a random node with equal probability
   • How to handle unknown list size
   • How to maintain selection probability

2. Space Optimization

   • How to avoid storing all nodes
   • How to use constant extra space

Naive Approach

Store all nodes in a list and select randomly:

class Solution(private val head: ListNode?) {
    private val values = mutableListOf<Int>()

    init {
        var current = head
        while (current != null) {
            values.add(current.`val`)
            current = current.next
        }
    }

    fun getRandom(): Int {
        val index = (Math.random() * values.size).toInt()
        return values[index]
    }
}

• Time Complexity: O(n) for initialization, O(1) for getRandom()
• Space Complexity: O(n)

Reservoir Sampling

Reservoir Sampling is a technique to randomly select k items from a list of unknown size n, where n is very large or unknown. In this problem, we want to select 1 random node from a linked list.

How it works:

Idea!! Select random node while traversing the list once:

1. We start with the first node as our initial result
2. For each new node we see (i-th node):
   • We generate a random number between [1, i]
   • If the random number is 1, we replace our current result with this new node
   • Otherwise, we keep our current result

Why it works:

• Each node has an equal chance of being selected
• For the i-th node, the probability of being selected is 1/i
• The probability of staying selected is (i-1)/i
• This ensures each node has a 1/n chance of being the final result

Key Notes:

• We only need to traverse the list once
• We don't need to know the total size in advance
• We only need O(1) extra space
• Each node has an equal probability of being selected

class Solution(private val head: ListNode?) {
    fun getRandom(): Int {
        var i = 1
        var current: ListNode? = head
        var result = -1
        while (current != null) {
            // `Random.nextInt(i)` generates a random number between `[0, i)`
            // Choose a random number between [1, i]
            val possibility = Random.nextInt(i) + 1

            if (possibility == 1) {
                result = current.`val`
            }
            i++
            current = current.next
        }
        return result
    }
}

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

Similar Problems

1. 398. Random Pick Index - Similar reservoir sampling concept
2. 528. Random Pick with Weight - Weighted random selection
3. 497. Random Point in Non-overlapping Rectangles - Random selection with area weights

Follow-up Questions

1. What if we need to select k random nodes instead of 1? Use reservoir sampling with a reservoir of size k, replacing elements with probability k/i for the i-th node.
2. What if the list is too large to fit in memory? Use reservoir sampling as it only requires O(1) space and processes one node at a time.
3. What if we need to support deletion of nodes? Maintain a hash table to track deleted nodes and skip them during random selection.
4. What if we need to support insertion of new nodes? Use reservoir sampling as it naturally handles new nodes by considering them in the probability calculation.