reservoir-sampling

Practice › LeetCode › LeetCode 03xx ›

LeetCode 382 - Linked List Random Node

LeetCode Problem 382 Difficulty: 🟡 Medium Topics: Linked List, Math, Reservoir Sampling, Randomized Solution Problem Understanding The problem gives us the head of a singly linked list and asks us to return a random node value such that every node in the list has exactly the same probability of being selected. The class has two operations: Solution(head) initializes the object with the linked list. getRandom() returns one node value chosen...

Practice › LeetCode › LeetCode 03xx ›

LeetCode 398 - Random Pick Index

LeetCode Problem 398 Difficulty: 🟡 Medium Topics: Hash Table, Math, Reservoir Sampling, Randomized Solution Problem Understanding The problem gives us an integer array nums that may contain duplicate values. We must design a class that supports repeatedly selecting a random index for a given target value. The important requirement is that if the target appears multiple times, every valid index must have the same probability of being returned. For example,...

Practice › LeetCode › LeetCode 04xx ›

LeetCode 497 - Random Point in Non-overlapping Rectangles

LeetCode Problem 497 Difficulty: 🟡 Medium Topics: Array, Math, Binary Search, Reservoir Sampling, Prefix Sum, Ordered Set, Randomized Solution Problem Understanding The problem asks us to randomly pick an integer point from a set of non-overlapping rectangles in 2D space. Each rectangle is defined by its bottom-left (ai, bi) and top-right (xi, yi) corners. The goal is to ensure that every integer point inside the union of all rectangles has...

Practice › LeetCode › LeetCode 05xx ›

LeetCode 519 - Random Flip Matrix

LeetCode Problem 519 Difficulty: 🟡 Medium Topics: Hash Table, Math, Reservoir Sampling, Randomized Solution Problem Understanding The problem gives us an m x n matrix where every cell initially contains 0 . We need to design a data structure that supports two operations efficiently: flip() This operation must randomly choose one of the remaining cells that still contains 0 , return its coordinates [row, col] , and then change that...

Practice › LeetCode › LeetCode (archived) › LeetCode 03xx ›

LeetCode 398: Random Pick Index

Problem Restatement We are given an integer array nums . The array may contain duplicate values. We need to implement a class with one operation: pick(target) This operation returns a random index i such that: nums[i] == target If the target appears at multiple indices, each valid index must have equal probability of being returned. The problem guarantees that target exists in nums . The constraints allow nums.length <= 2...