Counting Sort is a non-comparison-based sorting algorithm that works by counting the frequency of each value in a dataset. Instead of repeatedly comparing elements like traditional algorithms, Counting Sort calculates how many times each number appears and then reconstructs the sorted output using those counts. When the range of input values is small relative to the number of elements, this approach achieves an impressive O(n + k) time complexity, where n is the number of elements and k is the value range.
In coding interviews and competitive programming, Counting Sort is important because it introduces a different way of thinking about sorting problems. Rather than relying on comparison-based methods such as Sorting algorithms like quicksort or mergesort, it leverages frequency counting and cumulative counts. This concept appears frequently in problems involving frequency arrays, ranking elements, and building prefix-based structures.
Many interview questions that look unrelated to sorting can still be solved using Counting Sort ideas. For example, tasks involving frequency distributions in an Array, counting occurrences of values, or computing cumulative counts often rely on the same logic. Understanding this technique also makes it easier to grasp advanced algorithms like Radix Sort and Bucket Sort, which often use Counting Sort internally as a stable subroutine.
Common patterns you will see in Counting Sort problems include:
You should consider using Counting Sort when the input values fall within a known and reasonably small range, when stability matters, or when you need faster-than-comparison sorting. Mastering these patterns helps you solve a wide range of DSA interview problems involving counting, frequency tracking, and linear-time sorting.
Counting Sort operates directly on arrays and relies on indexing values as frequencies. Understanding array traversal and indexing is essential before implementing the algorithm.
Basic sorting concepts help you compare Counting Sort with comparison-based algorithms like quicksort and merge sort, and understand when linear-time sorting is possible.
Counting Sort uses cumulative counts to determine final positions of elements. Prefix sum concepts explain how these cumulative frequencies are computed efficiently.
Radix Sort frequently uses Counting Sort as a stable subroutine for sorting digits. Learning Counting Sort first makes Radix Sort easier to understand.
| Status | Title | Solution | Practice | Difficulty | Companies | Topics |
|---|---|---|---|---|---|---|
| 274. H-Index | Solution | Solve | Medium | Adobe+10 | ||
| 912. Sort an Array | Solution | Solve | Medium | Accenture+11 | ||
| 1833. Maximum Ice Cream Bars | Solution | Solve | Medium | Amazon | ||
| 3189. Minimum Moves to Get a Peaceful Board | Solution | Solve | Medium | - | ||
| 3517. Smallest Palindromic Rearrangement I | Solution | Solve | Medium | Amazon+1 |
Frequently appear alongside Counting Sort.
Common questions about Counting Sort.
Counting Sort itself is asked less frequently than algorithms like quicksort or merge sort, but the underlying idea of frequency counting appears often. FAANG interviews commonly include problems involving counting arrays, bucket logic, or prefix-based frequency calculations.
Common patterns include building frequency arrays, computing cumulative counts, reconstructing sorted outputs, and solving problems involving value ranges. Many variations also combine Counting Sort ideas with prefix sums or bucket-based grouping.
Counting Sort runs in O(n + k) time, where n is the number of elements and k is the range of input values. It requires O(k) extra space for the counting array. This makes it extremely fast when the value range is small relative to the input size.
The best Counting Sort interview problems focus on frequency arrays, sorting integers within a fixed range, and reconstructing ordered results. Many problems involve counting occurrences, ranking elements, or building cumulative counts. Practicing around 8–12 curated problems is usually enough to master the pattern.
Most candidates become comfortable with Counting Sort after solving about 8 to 15 focused problems. Start with basic frequency counting tasks, then move to stable sorting implementations and problems that combine counting with prefix sums or arrays.
Counting Sort works best when input values fall within a small known range, such as integers between 0 and 1000. In these cases, it can outperform comparison-based algorithms by achieving linear time complexity.
