Counting Sort is a non-comparison sorting algorithm that sorts elements by counting how many times each value appears. Instead of comparing elements like traditional algorithms, it builds a frequency array that stores the count of each value and then reconstructs the sorted output from those counts. Because it avoids comparisons, Counting Sort can achieve O(n + k) time complexity, where n is the number of elements and k is the range of input values.
This algorithm frequently appears in coding interviews when candidates need to optimize sorting for constrained ranges. Interviewers may test your ability to recognize when Counting Sort is more efficient than comparison-based approaches such as those covered in Sorting. It is also a foundational concept behind advanced algorithms like Radix Sort and related distribution techniques such as Bucket Sort.
Most Counting Sort problems revolve around recognizing patterns where element values fall within a limited range. Instead of repeatedly comparing numbers, you create a counting array, compute frequencies, and optionally convert those counts into prefix sums to determine final positions. Many interview problems also combine Counting Sort ideas with techniques from Prefix Sum to build stable sorting solutions or compute cumulative counts efficiently.
Counting Sort works best when the input values are integers within a reasonably small range. Many interview problems involving score distributions, character frequencies, or small integer arrays can be solved elegantly using this technique. Understanding how it operates on simple Array inputs and how it integrates with other distribution-based algorithms will help you recognize when it’s the optimal solution.
On FleetCode, you can strengthen your understanding by solving 9 curated Counting Sort problems that cover frequency arrays, stable sorting logic, and hybrid interview patterns commonly seen in coding interviews.
Counting Sort operates directly on arrays and relies on indexing values into a counting array. Understanding array traversal and indexing is essential before implementing the algorithm.
Counting Sort is a specialized sorting technique that differs from comparison-based algorithms. Learning general sorting concepts helps you understand when Counting Sort is the optimal choice.
Stable Counting Sort uses cumulative counts to determine the final index of each element. Prefix sum concepts help transform frequency arrays into positional indices.
Radix Sort uses Counting Sort as a subroutine to sort digits efficiently. Understanding Counting Sort is necessary to implement digit-based sorting strategies.
| Status | Title | Solution | Practice | Difficulty | Companies | Topics |
|---|---|---|---|---|---|---|
| 3088. Make String Anti-palindrome | Solution | Solve | Hard | - |
Frequently appear alongside Counting Sort.
Common questions about Counting Sort.
Counting Sort runs in O(n + k) time, where n is the number of elements and k is the range of values. It also requires O(k) extra space for the counting array. The algorithm becomes inefficient if the value range is extremely large compared to the input size.
Counting Sort itself is not asked as frequently as algorithms like Quick Sort or Merge Sort, but the underlying idea of frequency counting appears often. Interviewers commonly expect candidates to recognize when counting-based solutions reduce time complexity from O(n log n) to O(n + k).
Common patterns include frequency counting, stable reconstruction using prefix sums, sorting integers within a known range, and counting occurrences of characters or scores. These patterns also appear as building blocks in algorithms like Radix Sort.
The best Counting Sort interview problems focus on frequency arrays, sorting integers within a fixed range, and counting occurrences efficiently. Classic examples include sorting scores, counting characters in strings, and implementing stable counting-based sorting. Practicing 5–10 well-structured problems is usually enough to master the pattern.
Start by implementing the basic counting approach using a frequency array. Then practice converting counts into prefix sums to produce stable sorted output. Finally, solve several interview-style problems where counting replaces comparison-based sorting.
Most candidates become comfortable with Counting Sort after solving around 8–12 problems. This typically covers basic frequency counting, prefix-sum based stable sorting, and problems where counting replaces traditional sorting for efficiency.
