Pigeonhole-Principle
Bucket Sort and the Pigeonhole Principle
·2 mins
Algorithm
Bucket-Sort
Pigeonhole-Principle
Sorting
Split the value range into n - 1 buckets; the largest gap can never fall inside one bucket, so keeping each bucket’s minimum and maximum finds the maximum adjacent difference in linear time
LeetCode 961: N-Repeated Element in Size 2N Array
·1 min
LeetCode
Easy
Array
Hash-Table
Pigeonhole-Principle
LeetCode 961 note: the other n values are distinct, so the first value seen twice is the answer