grid47 Exploring patterns and algorithms
Sep 29, 2024
5 min read
Solution to LeetCode 382: Linked List Random Node Problem
Given a singly linked list, implement a class that supports the initialization of the list and the ability to return a random node’s value with equal probability.
Problem
Approach
Steps
Complexity
Input: The input consists of the initialization of a linked list followed by multiple calls to the getRandom method.
Example: Example input: [[1, 2, 3]] for initialization followed by calls to getRandom.
Constraints:
• 1 <= Number of nodes <= 10^4
• -10^4 <= Node.val <= 10^4
• At most 10^4 calls to getRandom.
Output: The output is a sequence of results from each getRandom() call, where each result corresponds to a random node's value from the list.
Example: Example output: [null, 2, 3, 1, 2, 3]
Constraints:
• Each getRandom() call returns one node's value randomly chosen from the linked list.
Goal: The goal is to implement getRandom in such a way that each node in the list has an equal probability of being chosen.
Steps:
• Initialize the linked list with the given nodes.
• Iterate through the linked list, maintaining a count of the nodes encountered.
• At each node, decide randomly whether to select that node or not using a probability of 1/i, where i is the number of nodes visited so far.
Goal: The solution must be efficient with a time complexity of O(n) and space complexity of O(1), where n is the number of nodes in the linked list.
Steps:
• Ensure O(n) time complexity for the getRandom method.
• Ensure O(1) space complexity for the getRandom method, meaning no extra space should be used other than for iterating through the list.
• Explanation: Here, 5, 10, or 15 is selected randomly on each call to getRandom.
Approach: We will use the Reservoir Sampling algorithm to randomly select a node from the linked list, ensuring each node has an equal chance of being chosen.
Observations:
• We need to ensure that each node is equally likely to be chosen, which suggests using a random selection approach while traversing the list.
• The linked list is traversed once, and a random value is chosen during each iteration with a decreasing probability, ensuring each node has equal selection chance.
Steps:
• Iterate through the list while maintaining a random variable that stores the selected node's value.
• At each node, decide randomly whether to keep that node's value based on the current node's index.
• Return the value of the node selected randomly after the iteration ends.
Empty Inputs:
• An empty linked list is not possible in this problem as the number of nodes will always be at least 1.
Large Inputs:
• The solution must handle linked lists with up to 10^4 nodes efficiently.
Special Values:
• Ensure that the solution handles edge values such as -10^4 and 10^4.
Constraints:
• The getRandom method must return a value from the linked list in constant space and linear time.
classSolution {
ListNode* head;
public:Solution(ListNode* head) {
this->head = head;
}
intgetRandom() {
int ans =0, i =1;
ListNode* p =this->head;
while(p) {
if(rand() % i ==0) ans = p->val;
i++;
p = p->next;
}
return ans;
}
};
/**
* Your Solution object will be instantiated and called as such:
* Solution* obj = new Solution(head);
* int param_1 = obj->getRandom();
1 : Class Declaration
classSolution {
This line begins the declaration of the `Solution` class.
2 : Variable Declaration
ListNode* head;
A pointer `head` to the first node in a linked list is declared.
3 : Access Modifiers
public:
The `public:` keyword denotes the start of the public section of the class, where the methods will be defined.
4 : Constructor
Solution(ListNode* head) {
This is the constructor for the `Solution` class that initializes the `head` pointer with the provided argument.
5 : Variable Assignment
this->head = head;
The constructor assigns the provided `head` to the class's `head` variable.
6 : Method Definition
intgetRandom() {
This defines the `getRandom` method which will return a random node's value from the linked list.
7 : Variable Initialization
int ans =0, i =1;
Two variables, `ans` and `i`, are initialized. `ans` stores the random node's value, and `i` is used to determine the probability of selecting each node.
8 : Pointer Initialization
ListNode* p =this->head;
A pointer `p` is initialized to the `head` of the linked list.
9 : Loop Structure
while(p) {
The `while` loop iterates over each node in the linked list until `p` becomes `NULL`.
10 : Reservoir Sampling
if(rand() % i ==0) ans = p->val;
This line implements the reservoir sampling algorithm to randomly select a node's value. The probability of selecting each node decreases with each additional node.
11 : Incrementing Counter
i++;
The counter `i` is incremented to reflect the number of nodes encountered so far.
12 : Pointer Advancement
p = p->next;
The pointer `p` moves to the next node in the linked list.
13 : Return Statement
return ans;
The method returns the value of the randomly selected node.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The getRandom method requires a full traversal of the linked list, which takes O(n) time.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is O(1) because the algorithm uses no extra space other than for the iteration variable.
