bucket-sort | brain

Practice › LeetCode › LeetCode 04xx ›

LeetCode 451 - Sort Characters By Frequency

LeetCode Problem 451 Difficulty: 🟡 Medium Topics: Hash Table, String, Sorting, Heap (Priority Queue), Bucket Sort, Counting Solution Problem Understanding The problem asks us to rearrange the characters of a string so that characters with higher frequency appear before characters with lower frequency. The output string must group identical characters together, and those groups must appear in descending order of occurrence count. For example, if the input is "tree" ,...

Practice › LeetCode › LeetCode 03xx ›

LeetCode 347 - Top K Frequent Elements

LeetCode Problem 347 Difficulty: 🟡 Medium Topics: Array, Hash Table, Divide and Conquer, Sorting, Heap (Priority Queue), Bucket Sort, Counting, Quickselect Solution Problem Understanding The problem asks us to return the k most frequently occurring elements from an integer array. We are given an array nums , which may contain duplicates, and an integer k . Our task is to identify which values appear most often and return exactly k...

Practice › LeetCode › LeetCode 09xx ›

LeetCode 912 - Sort an Array

LeetCode Problem 912 Difficulty: 🟡 Medium Topics: Array, Divide and Conquer, Sorting, Heap (Priority Queue), Merge Sort, Bucket Sort, Radix Sort, Counting Sort Solution Problem Understanding The problem asks us to sort an integer array in ascending order without using any built in sorting functions. The result must contain the same elements as the input, but arranged from smallest to largest. The input is an array nums containing integers. These...

Practice › LeetCode › LeetCode 02xx ›

LeetCode 220 - Contains Duplicate III

LeetCode Problem 220 Difficulty: 🔴 Hard Topics: Array, Sliding Window, Sorting, Bucket Sort, Ordered Set Solution Problem Understanding The problem asks whether there exists a pair of different indices (i, j) in the array such that two conditions are satisfied at the same time. The first condition is about index distance: $$|i - j| \leq indexDiff$$ This means the two elements must be relatively close together in the array. The...

Practice › LeetCode › LeetCode 06xx ›

LeetCode 692 - Top K Frequent Words

LeetCode Problem 692 Difficulty: 🟡 Medium Topics: Array, Hash Table, String, Trie, Sorting, Heap (Priority Queue), Bucket Sort, Counting Solution Problem Understanding The problem gives us an array of strings called words and an integer k . Each string represents a word, and words may appear multiple times in the array. Our task is to return the k most frequent words. The result must follow two ordering rules. First, words...

Practice › LeetCode › LeetCode 01xx ›

LeetCode 164 - Maximum Gap

LeetCode Problem 164 Difficulty: 🟡 Medium Topics: Array, Sorting, Bucket Sort, Radix Sort Solution Problem Understanding The problem asks us to compute the largest difference between two consecutive elements after sorting the array . At first glance, this may seem straightforward: sort the array, then scan through adjacent pairs to find the maximum difference. However, there is an important constraint: the algorithm must run in linear time, O(n), and use...

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

LeetCode 347: Top K Frequent Elements

Problem Restatement We are given an integer array nums and an integer k . Return the k most frequent elements in the array. The answer may be returned in any order. The problem guarantees that the answer is unique. The constraints allow nums.length up to 10^5 , so the solution must be better than O(n^2) . Input and Output Item Meaning Input Integer array nums and integer k Output The...

Practice › LeetCode › LeetCode (archived) › LeetCode 02xx ›

LeetCode 220: Contains Duplicate III

Problem Restatement We are given an integer array nums and two integers: indexDiff valueDiff We need to return True if there are two different indices i and j such that: i != j abs(i - j) <= indexDiff abs(nums[i] - nums[j]) <= valueDiff Otherwise, return False . The official problem asks for a pair of distinct indices whose index distance is at most indexDiff and whose value difference is at...

Practice › LeetCode › LeetCode (archived) › LeetCode 01xx ›

LeetCode 164: Maximum Gap

Problem Restatement We are given an integer array nums . We need to imagine the array sorted in ascending order, then return the maximum difference between two successive elements. If the array has fewer than two elements, return 0 . The problem also requires an algorithm that runs in linear time and uses linear extra space. LeetCode states the constraints as 1 <= nums.length <= 10^5 and 0 <= nums[i]...

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

LeetCode 451: Sort Characters By Frequency

Problem Restatement We are given a string s . We need to rearrange its characters so that characters with higher frequency appear before characters with lower frequency. The frequency of a character means how many times it appears in the string. If two characters have the same frequency, their relative order does not matter. Any valid order is accepted. For example: s = "tree" The character frequencies are: Character Frequency...

Programming › Algorithm Cookbook › Chapter 6. Sorting ›

6.9 Bucket Sort

6.9 Bucket Sort Bucket sort distributes elements into groups, sorts each group, and then concatenates the results. It relies on an assumption about the input distribution. When elements are spread roughly uniformly over a known range, bucket sort can run in linear time. Problem You have an array A[0..n-1] of real numbers in a known interval, typically [0, 1) . You want a sorting algorithm that exploits this range and...

Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

Bucket Sort

Bucket Sort Bucket sort partitions elements into a set of buckets based on their value, then sorts each bucket separately and concatenates the results. It is effective when input values are uniformly distributed over a known range. Problem Given an array $A$ of $n$ elements drawn from a range $[a, b)$, sort the elements. Idea Divide the range into $k$ equal sized intervals Place each element into its corresponding bucket...

Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

Uniform Bucket Sort

Uniform Bucket Sort Uniform bucket sort is a specialization of bucket sort where elements are assumed to be uniformly distributed over a known interval. Buckets are defined with equal width, and a direct arithmetic mapping assigns each element to a bucket. The design goal is to keep bucket sizes balanced so that each bucket remains small and can be sorted quickly. Problem Given an array $A$ of $n$ values drawn...

Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

External Bucket Sort

External Bucket Sort External bucket sort extends bucket sort to data that does not fit in memory. It partitions records into ordered buckets stored on external storage, sorts each bucket independently, and concatenates the buckets in key order. The method works well when the key distribution is known well enough to create buckets of manageable size. Problem Given a large dataset and a key function, sort all records using bounded...

#bucket-sort

LeetCode 451 - Sort Characters By Frequency

LeetCode 347 - Top K Frequent Elements

LeetCode 912 - Sort an Array

LeetCode 220 - Contains Duplicate III

LeetCode 692 - Top K Frequent Words

LeetCode 164 - Maximum Gap

LeetCode 347: Top K Frequent Elements

LeetCode 220: Contains Duplicate III

LeetCode 164: Maximum Gap

LeetCode 451: Sort Characters By Frequency

6.9 Bucket Sort

Bucket Sort

Uniform Bucket Sort

External Bucket Sort