Log inSign up
mediumGeeksforGeeksNot Started

Bucket Sort

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on GeeksforGeeks
Lesson

Problem Statement

Given an array of floating-point numbers arr uniformly distributed over the interval [0, 1), sort the array in ascending order using the Bucket Sort algorithm.

Also support general floating-point and integer arrays by scaling the minimum and maximum range across k buckets.

Example 1 · Uniform Float Numbers in [0, 1):

Input: arr = [0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434]
Output: [0.1234, 0.3434, 0.565, 0.656, 0.665, 0.897]
Explanation: Numbers are scattered into 6 buckets based on floor(6 * arr[i]), sorted individually, and concatenated.

Example 2 · Single Element Array:

Input: arr = [0.42]
Output: [0.42]
Explanation: Single element is already sorted.

Constraints:

  • 1 <= arr.length <= 105
  • 0.0 <= arr[i] < 1.0 (for canonical unit-interval variant)
  • -109 <= arr[i] <= 109 (for general range variant)

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Insertion Sort mechanics and linear comparison
  • Dynamic list / array allocation per bucket
  • Normalization and mathematical mapping to bounded ranges

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the Scatter-Gather distribution pattern for continuous numeric intervals.
  • Derive the bucket index hashing formula: idx = floor(k * (val - min) / range).
  • Understand the impact of data distribution on average-case O(N) vs worst-case O(N2) complexity.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Input data is uniformly distributed over a known bounded numeric range.
  • Sorting floating-point numbers in linear average time.
  • Maximum Gap problems and histogram distribution binning.

Algorithmic Decision Tree:

  • If values are dense integers in a small range, use Counting Sort.
  • If values are uniformly distributed floats or arbitrary continuous numbers, use Bucket Sort.

Connected Patterns:

Maximum Gap (LeetCode 164)Top K Frequent Elements (LeetCode 347)Radix Sort

1. Single Bucket with Comparison Sort (Brute Force)

Intuition

Place all floating numbers into a single list and apply insertion sort or bubble sort to sort in O(n2) worst case.

When to apply: Use as a baseline comparison before distributing into multiple buckets.

Single Bucket Insertion Sort Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434]
Current operationSTEP 1 OF 6
Array of 6 floats in [0, 1): [0
Visual state
Values and pointers at this exact step
pointers
S
0.897
0.565
0.656
0.1234
0.665
0.3434
0
↑ i=0
1
2
3
4
5
Variables at this step
n
6
Check / comparison
Start sort.
Decision / next transition
Begin insertion passes.
Why this step matters

Array of 6 floats in [0, 1): [0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434].

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public double[] bucketSort(double[] arr) {
6 int n = arr.length;
7 for (int i = 1; i < n; i++) {
8 double key = arr[i];
9 int j = i - 1;
10 while (j >= 0 && arr[j] > key) {
11 arr[j + 1] = arr[j];
12 j--;
13 }
14 arr[j + 1] = key;
15 }
16 return arr;
17 }
18 }
19
20 public static void main(String[] args) {
21 Solution sol = new Solution();
22 double[] arr = {0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434};
23 System.out.println("Sorted: " + Arrays.toString(sol.bucketSort(arr)));
24 }
25}

Time & Space Complexity

  • Time complexity: O(n^2) — Quadratic comparison sort over all n elements.
  • Space complexity: O(1) auxiliary — O(1) auxiliary memory.

Why Brute Force Doesn't Scale:

Global comparison sorts require O(N log N) or O(N2) comparisons.

For 100,000 uniform floats, Bucket Sort performs ~100,000 bucket inserts and completes in 10ms, outperforming QuickSort.

2. Integer Min-Max Scaled Bucket Sort

Intuition

1. Find min and max. 2. Bucket index = floor((val - min) / range * (k - 1)). 3. Sort each individual bucket with standard sort. 4. Concatenate buckets.

When to apply: Use when numbers are not pre-normalized into [0, 1).

Min-Max Scaled Distribution Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434]
Current operationSTEP 1 OF 6
Min = 0
Visual state
Values and pointers at this exact step
pointers
S
0.897
0.565
0.656
0.1234
0.665
0.3434
0
↑ Range
1
2
3
4
5
Variables at this step
min
0.1234
max
0.897
k
6
Check / comparison
Scale factors computed.
Decision / next transition
Initialize 6 buckets.
Why this step matters

Min = 0.1234, Max = 0.897. Range = 0.7736. Allocate k=6 buckets.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public double[] bucketSort(double[] arr) {
6 int n = arr.length;
7 if (n <= 1) return arr;
8 double min = arr[0], max = arr[0];
9 for (double v : arr) {
10 min = Math.min(min, v);
11 max = Math.max(max, v);
12 }
13 if (min == max) return arr;
14
15 List<List<Double>> buckets = new ArrayList<>();
16 for (int i = 0; i < n; i++) buckets.add(new ArrayList<>());
17
18 for (double v : arr) {
19 int bIdx = (int) ((v - min) / (max - min) * (n - 1));
20 buckets.get(bIdx).add(v);
21 }
22
23 int idx = 0;
24 for (List<Double> b : buckets) {
25 Collections.sort(b);
26 for (double v : b) arr[idx++] = v;
27 }
28 return arr;
29 }
30 }
31
32 public static void main(String[] args) {
33 Solution sol = new Solution();
34 double[] arr = {0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434};
35 System.out.println("Sorted: " + Arrays.toString(sol.bucketSort(arr)));
36 }
37}

Time & Space Complexity

  • Time complexity: O(n + k) — Linear time when items are uniformly distributed across k buckets.
  • Space complexity: O(n + k) — k buckets storing n items.

3. Standard Uniform Distribution Bucket Sort (Optimal & Standard)

Intuition

1. Create n empty buckets. 2. For each element x in arr, insert into bucket floor(n * x). 3. Sort each bucket with insertion sort (or stable sort). 4. Concatenate buckets sequentially back into arr. With uniform distribution, expected bucket size is O(1), yielding O(n) average total time.

When to apply: Use as the canonical textbook standard for uniformly distributed numbers in [0, 1).

Uniform Distribution Bucket Sort Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434]
Current operationSTEP 1 OF 6
n = 6
Visual state
Values and pointers at this exact step
pointers
S
0.897
0.565
0.656
0.1234
0.665
0.3434
0
↑ Init
1
2
3
4
5
Variables at this step
n
6
bucketsCount
6
Check / comparison
Initialize 6 buckets.
Decision / next transition
Begin partitioning.
Why this step matters

n = 6. Create 6 empty buckets (0 to 5). Mapping formula: idx = floor(6 * val).

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public double[] bucketSort(double[] arr) {
6 int n = arr.length;
7 if (n <= 1) return arr;
8
9 List<List<Double>> buckets = new ArrayList<>();
10 for (int i = 0; i < n; i++) buckets.add(new ArrayList<>());
11
12 for (double v : arr) {
13 int idx = (int) (n * v);
14 if (idx >= n) idx = n - 1;
15 buckets.get(idx).add(v);
16 }
17
18 int k = 0;
19 for (List<Double> b : buckets) {
20 Collections.sort(b);
21 for (double v : b) arr[k++] = v;
22 }
23 return arr;
24 }
25 }
26
27 public static void main(String[] args) {
28 Solution sol = new Solution();
29 double[] arr = {0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434};
30 System.out.println("Sorted: " + Arrays.toString(sol.bucketSort(arr)));
31 }
32}

Time & Space Complexity

  • Time complexity: O(n) average, O(n^2) worst — Expected O(1) elements per bucket yields linear average time across all n elements.
  • Space complexity: O(n) — n buckets storing n elements in total.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Full Insertion SortO(N^2)O(1)Sort the entire array using naive quadratic comparison sorting without binning.Repeated shift operations across the full array.
2.Better — Fixed Integer Counting SortO(N + K)O(K)Count frequencies of distinct integer keys.Cannot handle arbitrary real numbers directly.
3.Optimal — Scatter-Gather Bucket SortOptimalO(N + K) avgO(N + K)Distribute elements across K dynamic buckets, sort each bucket with Insertion Sort, and concatenate.Bucket skew / adversarial clustering.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • Single element array ([0.5]) — Returns immediately in O(1).
  • All identical elements ([0.5, 0.5, 0.5]) — All items land in the same bucket; Insertion Sort completes in O(N) linear time.
  • Extreme values at boundaries (0.0 and 0.9999) — Mapped safely without index out of bounds (idx < n).

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Under what condition does Bucket Sort achieve linear O(N + K) average time complexity?

2.What happens in the worst-case scenario when all N elements hash into the exact same bucket?

3.Why is Insertion Sort commonly used to sort individual buckets in Bucket Sort?

Back to DSA Sheet