Log inSign up
easyGeeksforGeeksNot Started

Counting Sort

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

Arrays
Solve on GeeksforGeeks
Lesson

Problem Statement

Given an array of integers nums, sort the array in ascending order without using comparison-based sort functions (such as Quicksort or Merge Sort), using the Counting Sort algorithm.

Example 1 · Standard Array with Duplicates:

Input: nums = [4, 2, 2, 8, 3, 3, 1]
Output: [1, 2, 2, 3, 3, 4, 8]
Explanation: Counting frequencies: 1:1, 2:2, 3:2, 4:1, 8:1. Assembling in order yields [1, 2, 2, 3, 3, 4, 8].

Example 2 · Array with Negative Numbers:

Input: nums = [5, 2, -3, 1, 0, -3]
Output: [-3, -3, 0, 1, 2, 5]
Explanation: Shift elements by minimum value (-3) to index into a 0-indexed count array.

Example 3 · Already Sorted Array:

Input: nums = [1, 2, 3, 4]
Output: [1, 2, 3, 4]
Explanation: Algorithm traverses frequency array and outputs [1, 2, 3, 4].

Constraints:

  • 1 <= nums.length <= 5 * 104
  • -5 * 104 <= nums[i] <= 5 * 104
  • Range K = (max - min + 1) is reasonably bounded.

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Array indexing and frequency arrays
  • Understanding the difference between comparison sorts (O(N log N)) and non-comparison sorts (O(N + K))
  • Concept of Stable Sorting

What You'll Learn

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

  • Understand how non-comparison sorting beats the theoretical O(N log N) lower bound.
  • Implement both frequency overwriting and stable cumulative prefix sum sorting.
  • Correctly handle negative numbers via offset shifting.

Pattern Recognition Trigger

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

Signals to Look For:

  • Elements are integers within a small, bounded numerical range [min, max].
  • Sorting must be done faster than O(N log N) (linear time O(N + K)).
  • Stable sorting is required (e.g., when sorting records by a key).

Algorithmic Decision Tree:

  • If values are integers and Range K <= O(N): Counting Sort beats O(N log N) comparison sorts with O(N + K) time.
  • If values can be negative: Offset indices by min_val (index = num - min_val).

Connected Patterns:

Two PointersSliding WindowPrefix Sum

1. Standard Comparison Sort

Intuition

Sort the input array using standard comparison sort in O(N log N) time.

Algorithm

  1. 1. Call built-in comparison sorting algorithm on the array.
  2. 2. Orders elements in O(N log N) time without exploiting bounded integer ranges.

Standard Comparison Sort (O(N log N))

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [4, 2, 2, 8, 3, 3, 1]
Current operationSTEP 1 OF 6
Phase 1 — Initial Unsorted Array: nums = [4, 2, 2, 8, 3, 3, 1]
Visual state
Values and pointers at this exact step
array
S
4
2
2
8
3
3
1
0
↑ Start
1
2
3
4
5
6
Variables at this step
nums
[4, 2, 2, 8, 3, 3, 1]
Check / comparison
Unsorted input.
Decision / next transition
Begin sorting.
Why this step matters

Phase 1 — Initial Unsorted Array: nums = [4, 2, 2, 8, 3, 3, 1]. Length = 7. Standard quicksort/mergesort makes pairwise comparisons.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 vector<int> countSort(vector<int>& arr) {
17 std::sort(arr.begin(), arr.end());
18 return arr;
19 }
20};
21
22int main() {
23 Solution sol;
24 vector<int> nums = {4, 2, 2, 8, 3, 3, 1};
25 vector<int> sorted = sol.countingSort(nums);
26
27 cout << "Counting Sort: [";
28 for (size_t i = 0; i < sorted.size(); ++i) {
29 cout << sorted[i] << (i + 1 < sorted.size() ? ", " : "");
30 }
31 cout << "]" << endl;
32 return 0;
33}

Time & Space Complexity

  • Time complexity: O(N log N) — Standard comparison sorting performs O(N log N) operations.
  • Space complexity: O(1) — In-place comparison sorting uses O(1) auxiliary space.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Frequency Array Direct Overwrite (Unstable)

Intuition

Count the occurrence of each integer in a frequency array, then write each number back into the original array according to its count.

Algorithm

  1. 1. Find minVal and maxVal in arr. Range K = maxVal - minVal + 1.
  2. 2. Create count array of size K initialized to 0.
  3. 3. Count occurrences: For x in arr, count[x - minVal]++.
  4. 4. Overwrite arr by iterating through count and placing (i + minVal) count[i] times.
  5. 5. Note: This approach is unstable (it does not preserve the relative order of equal keys).

Frequency Array Direct Overwrite (Unstable)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 2, 2, 3, 3, 4, 8]
Current operationSTEP 1 OF 6
Phase 1 — Count Frequencies: Scan nums to populate count array of size max + 1 = 9: count[1]=1, count[2]=2, count[3]=2, count[4]=1, count[8]=1
Visual state
Values and pointers at this exact step
array
S
—
—
—
—
—
—
—
0
↑ Counts Ready
1
2
3
4
5
6
Variables at this step
Counts
{ 1:1, 2:2, 3:2, 4:1, 8:1 }
Check / comparison
Frequencies counted in O(N).
Decision / next transition
Prepare in-place overwrite.
Why this step matters

Phase 1 — Count Frequencies: Scan nums to populate count array of size max + 1 = 9: count[1]=1, count[2]=2, count[3]=2, count[4]=1, count[8]=1.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 vector<int> countSort(vector<int>& arr) {
17 if (arr.empty()) return arr;
18 int minVal = *min_element(arr.begin(), arr.end());
19 int maxVal = *max_element(arr.begin(), arr.end());
20 int range = maxVal - minVal + 1;
21 vector<int> count(range, 0);
22
23 for (int x : arr) count[x - minVal]++;
24
25 int idx = 0;
26 for (int i = 0; i < range; ++i) {
27 while (count[i]-- > 0) {
28 arr[idx++] = i + minVal;
29 }
30 }
31 return arr;
32 }
33};
34
35int main() {
36 Solution sol;
37 vector<int> nums = {4, 2, 2, 8, 3, 3, 1};
38 vector<int> sorted = sol.countingSort(nums);
39
40 cout << "Counting Sort: [";
41 for (size_t i = 0; i < sorted.size(); ++i) {
42 cout << sorted[i] << (i + 1 < sorted.size() ? ", " : "");
43 }
44 cout << "]" << endl;
45 return 0;
46}

Time & Space Complexity

  • Time complexity: O(N + K) — Counting takes O(N) and traversing frequency array takes O(K). Total time is O(N + K).
  • Space complexity: O(K) — Requires frequency array of size K = (max - min + 1), consuming O(K) space.

3. Cumulative Prefix Sum Stable Counting Sort

Intuition

Compute running prefix sums of counts to determine exact final output positions, then traverse input right-to-left to ensure stability.

Algorithm

  1. 1. Find minVal and maxVal. Compute count array of size K = maxVal - minVal + 1.
  2. 2. Populate frequencies in count.
  3. 3. Prefix Sum: For i from 1 to K-1: count[i] += count[i-1].
  4. 4. Traverse arr from right to left (n-1 down to 0): - pos = count[arr[i] - minVal] - 1 - output[pos] = arr[i] - count[arr[i] - minVal]--.
  5. 5. Return output array. Guaranteed O(N + K) time and stable sorting.

Cumulative Prefix Sum Stable Counting Sort (O(N + K) Time)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 2, 2, 3, 3, 4, 8]
Current operationSTEP 1 OF 6
Phase 1 — Frequency Counts: count[1]=1, count[2]=2, count[3]=2, count[4]=1, count[8]=1
Visual state
Values and pointers at this exact step
array
S
—
—
—
—
—
—
—
0
↑ Step 1
1
2
3
4
5
6
Variables at this step
Counts
[1:1, 2:2, 3:2, 4:1, 8:1]
Check / comparison
Counts initialized.
Decision / next transition
Compute prefix sums.
Why this step matters

Phase 1 — Frequency Counts: count[1]=1, count[2]=2, count[3]=2, count[4]=1, count[8]=1.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 vector<int> countSort(vector<int>& arr) {
17 int n = arr.size();
18 if (n == 0) return arr;
19 int minVal = *min_element(arr.begin(), arr.end());
20 int maxVal = *max_element(arr.begin(), arr.end());
21 int range = maxVal - minVal + 1;
22
23 vector<int> count(range, 0);
24 vector<int> output(n);
25
26 for (int x : arr) count[x - minVal]++;
27 for (int i = 1; i < range; ++i) count[i] += count[i - 1];
28
29 for (int i = n - 1; i >= 0; --i) {
30 output[count[arr[i] - minVal] - 1] = arr[i];
31 count[arr[i] - minVal]--;
32 }
33 return output;
34 }
35};
36
37int main() {
38 Solution sol;
39 vector<int> nums = {4, 2, 2, 8, 3, 3, 1};
40 vector<int> sorted = sol.countingSort(nums);
41
42 cout << "Counting Sort: [";
43 for (size_t i = 0; i < sorted.size(); ++i) {
44 cout << sorted[i] << (i + 1 < sorted.size() ? ", " : "");
45 }
46 cout << "]" << endl;
47 return 0;
48}

Time & Space Complexity

  • Time complexity: O(N + K) — All operations (finding min/max, frequency counting, prefix sums, and stable output placement) execute in O(N + K) linear time.
  • Space complexity: O(N + K) — Requires auxiliary output array of size N and count array of size K, taking O(N + K) space.

Approach Comparison Matrix

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

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Approach 1: Standard Comparison SortO(N log N)O(1)Sort the input array using standard comparison sort in O(N log N) time.Repeated redundant scans over the input.
2.Approach 2: Frequency Array Direct Overwrite (Unstable)O(N + K)O(K)Count the occurrence of each integer in a frequency array, then write each number back into the original array according to its count.Auxiliary memory allocation or sorting step.
3.Approach 3: Cumulative Prefix Sum Stable Counting SortOptimalO(N + K)O(N + K)Compute running prefix sums of counts to determine exact final output positions, then traverse input right-to-left to ensure stability.None. Asymptotically optimal.

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:

  • Negative Numbers — Input: `, Expected: ` —
  • Single Element Array [x] — Input: `, Expected: ` —
  • All Identical Elements [5, 5, 5, 5] — Input: `, Expected: ` —

Interview Tips & Best Practices

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

  1. Always state the constraint requirement: Counting sort is only linear when K = O(N).
  2. Explain the difference between non-stable count reconstruction vs stable prefix-sum placement.
  3. Mention how Counting Sort serves as the core subroutine for Radix Sort to sort multi-digit numbers or strings in linear time.

Quick Comprehension Check

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

1.What is the optimal time and auxiliary space complexity for Counting Sort?

2.Why is the brute force approach suboptimal for large inputs in Counting Sort?

3.Which data structure or technique enables the optimal solution for Counting Sort?

Back to DSA Sheet