randomized | brain

Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.19 Online Algorithms

19.19 Online Algorithms Most algorithms assume complete knowledge of the input before computation begins. Sorting algorithms see the entire array. Graph algorithms receive the complete graph. Dynamic programming algorithms assume all problem data is available from the start. Many real systems do not operate this way. A web server receives requests one at a time. A scheduler receives jobs continuously. A network router sees packets as they arrive. A cloud...

Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.4 Randomized Quicksort

19.4 Randomized Quicksort Randomized quicksort is one of the most successful applications of randomization in algorithm design. It combines the elegance and practical efficiency of quicksort with probabilistic guarantees that eliminate dependence on particular input arrangements. The resulting algorithm is simple, fast, cache-friendly, and widely used in production systems. Classical quicksort already performs extremely well on average. Its weakness lies in pivot selection. Poor pivot choices produce highly unbalanced partitions,...

Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.20 Streaming Algorithms

19.20 Streaming Algorithms Streaming algorithms process data one item at a time while using much less memory than the input size. They are designed for systems where the stream is too large to store, too fast to revisit, or too distributed to collect in one place. A streaming algorithm usually sees each element once. It updates a compact state and discards the raw item. Later, queries are answered from that...

Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.15 Greedy Approximation

19.15 Greedy Approximation Many approximation algorithms are built around a simple principle: make the best local decision available at each step. This strategy is known as the greedy approach. Greedy algorithms are attractive because they are usually easy to understand, simple to implement, and computationally efficient. For some problems, greedy choices produce optimal solutions. For others, they do not. Even when optimality is impossible, however, a carefully designed greedy strategy...

Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.18 Primal-Dual Approximation

19.18 Primal-Dual Approximation Primal-dual approximation algorithms use linear programming structure to design fast approximate solutions. The method starts from an optimization problem, writes a linear-programming relaxation, examines its dual, and then builds a solution while maintaining information about both sides. The central idea is simple: the dual solution gives a bound on the optimum. If the algorithm constructs a feasible primal solution whose cost is at most some factor times...

Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.5 Random Sampling

19.5 Random Sampling Random sampling is one of the most powerful techniques in algorithm design. Instead of processing an entire dataset, we examine a carefully selected subset and use it to estimate properties of the whole. When designed correctly, a sample can provide surprisingly accurate answers while requiring only a fraction of the computation, memory, and storage needed by exact algorithms. The idea appears throughout computer science. Database systems estimate...

Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.13 Locality-Sensitive Hashing

19.13 Locality-Sensitive Hashing Many applications need to find similar items inside very large collections. Search engines look for near-duplicate documents. Recommendation systems search for users with similar preferences. Image retrieval systems search for visually similar images. Fraud detection systems search for related transactions. The obvious solution is to compare every item against every other item. Unfortunately, this approach scales poorly. A collection containing one million objects requires roughly: 500 billion...

Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.21 The Power of Randomization

19.21 The Power of Randomization Throughout this chapter, we have encountered a recurring theme: A small amount of randomness can dramatically simplify a difficult problem. Randomization appears in sorting, graph algorithms, approximation algorithms, streaming systems, sketching structures, online decision-making, and distributed computing. Sometimes randomness improves performance. Sometimes it simplifies implementation. Sometimes it makes a problem tractable that would otherwise be infeasible. This concluding section examines the broader principles behind randomized...

Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.1 Random Variables in Algorithms

19.1 Random Variables in Algorithms Randomized algorithms differ from deterministic algorithms because their behavior depends on random choices made during execution. A deterministic algorithm always follows the same sequence of operations for a given input. A randomized algorithm may produce different execution paths, different running times, or even different outputs when executed multiple times on the same input. To analyze such algorithms rigorously, we need a mathematical framework that describes...

Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.12 Count-Min Sketch Revisited

19.12 Count-Min Sketch Revisited A Count-Min Sketch estimates item frequencies in a stream using fixed memory. It answers questions such as: How many times has this key appeared? The answer is approximate. Unlike a hash map, a Count-Min Sketch does not store every key. It stores counters arranged in a small table and updates several counters for each observed item. The key property is one-sided error. A Count-Min Sketch never...

Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.16 Set Cover Approximation

19.16 Set Cover Approximation Set Cover is the canonical greedy approximation problem. It is easy to describe, appears in many practical systems, and has a clean logarithmic approximation guarantee. If you understand Set Cover, you understand the basic shape of many approximation algorithms: choose the best local move, compare that move to what an optimal solution must accomplish, and accumulate a global bound. The problem is computationally hard in general,...

Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.7 Skip Lists Revisited

19.7 Skip Lists Revisited Balanced search trees achieve logarithmic performance by carefully maintaining structural invariants. AVL trees perform rotations to preserve height balance. Red-black trees maintain coloring rules. B-trees redistribute keys across nodes. These structures provide excellent asymptotic guarantees, but the implementation complexity can be substantial. Skip lists take a different approach. Instead of maintaining strict balance through deterministic rules, they use randomness. A skip list is essentially a hierarchy...

Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.14 Approximation Ratios

19.14 Approximation Ratios Some optimization problems are easy to state and hard to solve exactly. We may want the smallest set of servers that covers all regions, the cheapest route visiting every city, the best subset of ads under a budget, or the minimum number of machines needed to schedule jobs. For many such problems, exact algorithms are too expensive for large inputs. Approximation algorithms address this situation directly. Instead...

Programming › Algorithm Cookbook ›

Chapter 19. Randomized and Approximate Algorithms

Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.24 Randomized Algorithms in Practice

19.24 Randomized Algorithms in Practice Theoretical analysis explains why randomized algorithms work. Production systems reveal why they matter. Many randomized algorithms were originally developed to solve mathematical problems. Over time, they became essential engineering tools. Search engines use sketches to summarize web traffic. Databases use probabilistic structures to avoid unnecessary I/O. Distributed systems use randomness to coordinate millions of machines. Machine learning systems rely on random sampling and stochastic optimization...

Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.25 Choosing the Right Randomized Technique

19.25 Choosing the Right Randomized Technique Randomized algorithms span a wide range of techniques. Some improve runtime. Some reduce memory usage. Some provide approximate answers. Some help systems make decisions under uncertainty. Others simplify algorithm design or avoid adversarial inputs. A common challenge for practitioners is not understanding an individual algorithm. The challenge is knowing which randomized technique applies to a particular problem. This final section serves as a practical...

Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.8 Hashing with Randomness

19.8 Hashing with Randomness Hash tables are usually presented as deterministic data structures: compute a hash, reduce it to a table index, and store or retrieve the key. In practice, randomness is often part of the design. A randomized hash function can reduce collision patterns, defend against adversarial inputs, and provide strong expected-time guarantees without relying on accidental properties of the input. The main issue is collisions. A hash table...

Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.6 Shuffling

19.6 Shuffling Shuffling converts an ordered collection into a uniformly random permutation. This is a small operation with large consequences. A correct shuffle removes input order bias, supports randomized experiments, prepares data for training, randomizes work distribution, and provides a foundation for many randomized algorithms. The central requirement is uniformity. For an array with n distinct elements, there are n! possible permutations. A correct shuffle must make every permutation equally...

Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.11 Bloom Filters Revisited

19.11 Bloom Filters Revisited A Bloom filter is one of the most widely deployed probabilistic data structures in modern computing. It answers a simple question: Have I seen this item before? The answer is not exact. A Bloom filter may occasionally report that an item is present when it is not. It never reports that a previously inserted item is absent. This asymmetry makes Bloom filters useful in systems where...

Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.2 Las Vegas Algorithms

19.2 Las Vegas Algorithms A randomized algorithm can use randomness in several ways. Some algorithms use random choices to improve performance while guaranteeing that every answer produced is correct. Others use random choices to reduce running time while accepting a small probability of error. The first category is known as Las Vegas algorithms. A Las Vegas algorithm always returns a correct result. Randomness affects the amount of work performed, not...

Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.23 Derandomization

19.23 Derandomization Randomized algorithms are often easier to design and analyze than deterministic algorithms. A random pivot simplifies quicksort. Randomized rounding simplifies approximation algorithms. Random sampling simplifies large-scale data analysis. A natural question follows: If randomness helps so much, can we remove it? Surprisingly, the answer is often yes. Derandomization is the process of transforming a randomized algorithm into a deterministic one while preserving most or all of its guarantees....

Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.22 Probability Bounds

19.22 Probability Bounds Randomized algorithms rarely stop at computing an expected value. An expected value tells us what happens on average, but it does not say how often the algorithm deviates from that average. For production systems, that missing information matters. If a randomized algorithm has expected runtime: O(n log n) we may still ask: How likely is a much slower run? If a sketch estimates frequency with expected error:...

Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.10 HyperLogLog

19.10 HyperLogLog HyperLogLog estimates the number of distinct elements in a stream using a small, fixed amount of memory. This problem appears constantly in large systems: distinct users, distinct IP addresses, distinct search queries, distinct URLs, distinct products viewed, distinct errors, distinct devices, and distinct sessions. The exact solution is straightforward: store every distinct value in a set and return the size of the set. That works for small inputs....

Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.9 MinHash

19.9 MinHash Many large-scale systems need to compare sets. Search engines compare documents. Recommendation systems compare user interests. Security systems compare malware signatures. Data integration pipelines compare records from different sources. The obvious approach is to compute the exact similarity between every pair of sets. Unfortunately, exact comparison becomes expensive as datasets grow. A search index may contain billions of documents. A recommendation platform may store billions of user interactions....

Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.17 Randomized Rounding

19.17 Randomized Rounding Many optimization problems can be expressed as integer programs. Variables represent decisions, constraints describe feasibility requirements, and an objective function measures solution quality. Unfortunately, integer programs are often computationally difficult to solve exactly. A common strategy is to relax the problem. Instead of requiring variables to be integers, allow them to take fractional values. The resulting linear program can usually be solved efficiently. The challenge then becomes...

Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.3 Monte Carlo Algorithms

19.3 Monte Carlo Algorithms Las Vegas algorithms always return correct answers and use randomness to influence resource consumption. Monte Carlo algorithms take the opposite approach. They place strict bounds on resource usage and allow a small probability of error. This trade-off has become increasingly important in modern computing. Large-scale search systems, distributed databases, streaming analytics engines, machine learning pipelines, and cryptographic protocols frequently process data volumes that make exact computation...

Practice › LeetCode › LeetCode 03xx ›

LeetCode 381 - Insert Delete GetRandom O(1) - Duplicates allowed

LeetCode Problem 381 Difficulty: 🔴 Hard Topics: Array, Hash Table, Math, Design, Randomized Solution Problem Understanding The problem asks us to design a data structure called RandomizedCollection that behaves like a multiset. Unlike a normal set, duplicate values are allowed. The data structure must support three operations: Insert a value Remove one occurrence of a value Return a random element The critical requirement is that every operation must run in...

Practice › LeetCode › LeetCode 05xx ›

LeetCode 528 - Random Pick with Weight

LeetCode Problem 528 Difficulty: 🟡 Medium Topics: Array, Math, Binary Search, Prefix Sum, Randomized Solution Problem Understanding The problem asks us to design a data structure that supports weighted random sampling . You are given an array w , where each element represents the weight of an index. Instead of choosing every index with equal probability, the selection probability depends on its weight. For example: If w = [1, 3]...

Practice › LeetCode › LeetCode 15xx ›

LeetCode 1515 - Best Position for a Service Centre

LeetCode Problem 1515 Difficulty: 🔴 Hard Topics: Array, Math, Geometry, Randomized Solution Problem Understanding The problem asks us to find the optimal location for a service center on a 2D map such that the total Euclidean distance from the center to all customers is minimized. We are given the coordinates of customers as a list positions , where each element is a 2-element list [x, y] . The goal is...

Practice › LeetCode › LeetCode 04xx ›

LeetCode 478 - Generate Random Point in a Circle

LeetCode Problem 478 Difficulty: 🟡 Medium Topics: Math, Geometry, Rejection Sampling, Randomized Solution LeetCode 478 - Generate Random Point in a Circle Problem Understanding This problem asks us to generate random points uniformly inside a circle. The circle is defined by its radius and the coordinates of its center. Every call to randPoint() must return a point [x, y] such that the point lies either inside the circle or exactly...

Practice › LeetCode › LeetCode 04xx ›

LeetCode 470 - Implement Rand10() Using Rand7()

LeetCode Problem 470 Difficulty: 🟡 Medium Topics: Math, Rejection Sampling, Randomized, Probability and Statistics Solution Problem Understanding The problem provides access to a single API, rand7() , which returns a uniformly random integer from 1 to 7 . The task is to implement another function, rand10() , which must return a uniformly random integer from 1 to 10 . The important constraint is that we are not allowed to use...

Practice › LeetCode › LeetCode 03xx ›

LeetCode 384 - Shuffle an Array

LeetCode Problem 384 Difficulty: 🟡 Medium Topics: Array, Math, Design, Randomized Solution Problem Understanding The problem asks us to design a data structure that supports two operations on an integer array: Reset the array back to its original order. Return a randomly shuffled version of the array. The important requirement is that every possible permutation of the array must be equally likely. This means the shuffle operation cannot introduce statistical...

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 07xx ›

LeetCode 710 - Random Pick with Blacklist

LeetCode Problem 710 Difficulty: 🔴 Hard Topics: Array, Hash Table, Math, Binary Search, Sorting, Randomized Solution Problem Understanding The problem asks us to design a data structure that can repeatedly return a random integer from the range [0, n - 1] , while excluding all integers that appear in a blacklist. Every valid number must have exactly the same probability of being chosen. The challenge is not simply filtering numbers....

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 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 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 03xx ›

LeetCode 380 - Insert Delete GetRandom O(1)

LeetCode Problem 380 Difficulty: 🟡 Medium Topics: Array, Hash Table, Math, Design, Randomized Solution Problem Understanding This problem asks us to design a custom data structure called RandomizedSet that supports three operations: Insert a value into the set. Remove a value from the set. Return a random element from the set. The critical requirement is that all three operations must run in average O(1) time complexity. The behavior is very...

Practice › LeetCode › LeetCode (archived) › LeetCode 05xx ›

LeetCode 528: Random Pick with Weight

Problem Restatement We are given a 0-indexed array of positive integers w . Each w[i] is the weight of index i . We need to implement a class with a method: pickIndex() This method returns an index from 0 to len(w) - 1 . The probability of returning index i must be: w[i] / sum(w) So larger weights should be picked more often. For example, if: w = [1, 3]...

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...

Practice › LeetCode › LeetCode (archived) › LeetCode 04xx ›

LeetCode 470: Implement Rand10() Using Rand7()

Problem Restatement We are given an API: rand7() It returns a uniformly random integer from 1 to 7 . We need to implement: rand10() It must return a uniformly random integer from 1 to 10 . We may only call rand7() . We should not use any other random API. The official problem asks for a uniform random integer in [1, 10] using only rand7() . Input and Output Item...

Practice › LeetCode › LeetCode (archived) › LeetCode 04xx ›

LeetCode 497: Random Point in Non-overlapping Rectangles

Problem Restatement We are given a list of non-overlapping axis-aligned rectangles. Each rectangle is represented as: [x1, y1, x2, y2] where: Value Meaning x1, y1 Bottom-left corner x2, y2 Top-right corner All coordinates are integers. We need to implement a class that can randomly return an integer point inside the area covered by the rectangles. A point on the border is included. Every valid integer point across all rectangles must...

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

LeetCode 384: Shuffle an Array

Problem Restatement We are given an integer array nums . We need to design a class with two operations: Operation Meaning reset() Return the array to its original configuration shuffle() Return a random permutation of the array The important requirement is that every possible permutation must be equally likely. For an array of length n , there are n! possible permutations. A correct shuffle gives each one the same probability....

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

LeetCode 382: Linked List Random Node

Problem Restatement We are given the head of a singly linked list. We need to implement a class with one main operation: getRandom() This operation returns the value of a random node from the linked list. Every node must have the same probability of being chosen. The linked list has at least one node, so getRandom() always has a valid value to return. The follow-up asks whether we can solve...

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

LeetCode 381: Insert Delete GetRandom O(1) - Duplicates Allowed

Problem Restatement We need to implement a data structure called RandomizedCollection . It behaves like a multiset, so duplicate values are allowed. It must support three operations in average O(1) time: Operation Meaning insert(val) Insert one occurrence of val remove(val) Remove one occurrence of val if present getRandom() Return a random element from the current collection For getRandom() , every stored occurrence has equal probability. So if the collection contains:...

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

LeetCode 380: Insert Delete GetRandom O(1)

Problem Restatement We need to implement a data structure called RandomizedSet . It supports three operations: Operation Meaning insert(val) Insert val if it does not already exist remove(val) Remove val if it exists getRandom() Return a random element from the current set Each operation must run in average O(1) time. For getRandom() , every element currently in the set must have the same probability of being returned. The problem guarantees...

Practice › LeetCode › LeetCode (archived) › LeetCode 04xx ›

LeetCode 478: Generate Random Point in a Circle

Problem Restatement We are given a circle defined by: Value Meaning radius Radius of the circle x_center x-coordinate of the center y_center y-coordinate of the center We need to implement a class with two parts: Method Meaning Solution(radius, x_center, y_center) Stores the circle randPoint() Returns a random point inside or on the circle The returned point must be uniformly distributed inside the circle. A point on the circumference is allowed....

Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Weighted Reservoir Sampling

Weighted Reservoir Sampling Weighted Reservoir Sampling selects a random sample from a stream where each item has a weight. Higher weight items should be more likely to appear in the sample. A common method assigns each item a random priority derived from its weight, then keeps the $k$ items with the largest priorities. Problem Given a stream of weighted items: $$ (x_1, w_1), (x_2, w_2), \dots, (x_n, w_n) $$ where...

Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Randomized Quickselect

Randomized Quickselect Randomized Quickselect improves Quickselect by choosing the pivot uniformly at random. This removes dependence on input order and avoids pathological worst cases in practice. The structure remains identical to Quickselect. Only pivot selection changes. Problem Given an array $A$ of length $n$ and an integer $k$ with $0 \le k < n$, return the k-th smallest element. Algorithm At each step, select a random pivot, partition, and recurse...

Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Floyd Sampling

Floyd Sampling Floyd Sampling selects $k$ distinct integers uniformly from the range $0$ to $n - 1$. It avoids building and shuffling the full range, so it is useful when $k$ is much smaller than $n$. The algorithm inserts one value per iteration into a set. Each insertion preserves uniformity over all subsets of the processed range. Problem Given integers $n$ and $k$ with: $$ 0 \le k \le n...

Wiki › Algorithms › 02. Data Structures › 1. Core Data Structures and Operations › 1.1 Arrays and Dynamic Arrays ›

Array Shuffle

Array Shuffle Array shuffle rearranges elements into a random order such that every permutation is equally likely. You use it when unbiased randomization is required, such as sampling, randomized algorithms, or testing. Problem Given an array $A$ of length $n$, produce a permutation where each of the $n!$ possible orderings occurs with equal probability. Algorithm Use the Fisher–Yates shuffle. Iterate from the end and swap each position with a random...

Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Reservoir Sampling

Reservoir Sampling Reservoir Sampling selects a uniform random sample from a stream without knowing the stream length in advance. It keeps only a fixed-size reservoir and updates it as new items arrive. The simplest version keeps one item. The general version keeps $k$ items. Problem Given a stream: $$ x_1, x_2, \dots, x_n $$ choose $k$ items uniformly at random from the stream, using only: $$ O(k) $$ memory. Algorithm...

Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Randomized Quicksort

Randomized Quicksort Randomized quicksort modifies quicksort by choosing the pivot at random. This removes dependence on input order and prevents consistently bad partitions. The algorithm retains the same structure as quicksort but replaces deterministic pivot selection with a random choice. Problem Given an array $A$ of length $n$, reorder it such that: $$ A[0] \le A[1] \le \dots \le A[n-1] $$ Idea Instead of always choosing a fixed pivot position,...

#randomized

19.19 Online Algorithms

19.4 Randomized Quicksort

19.20 Streaming Algorithms

19.15 Greedy Approximation

19.18 Primal-Dual Approximation

19.5 Random Sampling

19.13 Locality-Sensitive Hashing

19.21 The Power of Randomization

19.1 Random Variables in Algorithms

19.12 Count-Min Sketch Revisited

19.16 Set Cover Approximation

19.7 Skip Lists Revisited

19.14 Approximation Ratios

Chapter 19. Randomized and Approximate Algorithms

19.24 Randomized Algorithms in Practice

19.25 Choosing the Right Randomized Technique

19.8 Hashing with Randomness

19.6 Shuffling

19.11 Bloom Filters Revisited

19.2 Las Vegas Algorithms

19.23 Derandomization

19.22 Probability Bounds

19.10 HyperLogLog

19.9 MinHash

19.17 Randomized Rounding

19.3 Monte Carlo Algorithms

LeetCode 381 - Insert Delete GetRandom O(1) - Duplicates allowed

LeetCode 528 - Random Pick with Weight

LeetCode 1515 - Best Position for a Service Centre

LeetCode 478 - Generate Random Point in a Circle

LeetCode 470 - Implement Rand10() Using Rand7()

LeetCode 384 - Shuffle an Array

LeetCode 398 - Random Pick Index

LeetCode 710 - Random Pick with Blacklist

LeetCode 497 - Random Point in Non-overlapping Rectangles

LeetCode 382 - Linked List Random Node

LeetCode 519 - Random Flip Matrix

LeetCode 380 - Insert Delete GetRandom O(1)

LeetCode 528: Random Pick with Weight

LeetCode 398: Random Pick Index

LeetCode 470: Implement Rand10() Using Rand7()

LeetCode 497: Random Point in Non-overlapping Rectangles

LeetCode 384: Shuffle an Array

LeetCode 382: Linked List Random Node

LeetCode 381: Insert Delete GetRandom O(1) - Duplicates Allowed

LeetCode 380: Insert Delete GetRandom O(1)

LeetCode 478: Generate Random Point in a Circle

Weighted Reservoir Sampling

Randomized Quickselect

Floyd Sampling

Array Shuffle

Reservoir Sampling

Randomized Quicksort