Sorting algorithm selection
Filed under Amazon
Free read 1 of 3Since the range [0, 100] is small and constant, we can use Counting Sort.
The question
Given an array of integers where values are in the range [0, 100], identify the most efficient sorting algorithm.
Constraints
- Range of values is small and fixed.
- Must be efficient in time and space.
Approach
Since the range [0, 100] is small and constant, we can use Counting Sort.
Create a frequency array of size 101. Iterate through the input, incrementing counts for each value.
Iterate through the frequency array to reconstruct the sorted list.
Time complexity is O(n + K) where K=101, which is effectively O(n). Space complexity is O(K), which is O(1).
Tips
- What they are testing: Explain why comparison-based sorts (O(n log n)) are inferior to non-comparison sorts here.
- Common mistake: Suggesting QuickSort or MergeSort without acknowledging the constraints.
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.