An array arr containing non-negative integers is given. Rearrange all values in non-decreasing order using the counting sort algorithm.
The algorithm may use the numeric value as an index in a frequency array. Return a sorted array without using comparison-based sorting.
Example 1
Input: arr = [4, 2, 2, 8, 3, 3, 1]
Output: [1, 2, 2, 3, 3, 4, 8]
Explanation: Frequencies are counted for values 1, 2, 3, 4, and 8. Prefix sums give final positions, and the output array receives all values in sorted order.
Example 2
Input: arr = [0, 0, 0]
Output: [0, 0, 0]
Explanation: Every value is already equal. Counting sort records frequency 3 for value 0 and returns the same sorted order.
Approach
Counting Sort avoids comparing values with one another by using each value as an index in a count array. The frequency stored at that index tells how many times the value appears.
These frequencies are then converted into prefix sums, so each position tells how many elements are less than or equal to that value and helps determine its correct position in the sorted output. The input is scanned from right to left while placing values, which keeps equal elements in their original relative order and makes the sorting stable.
Algorithm
The array length
nis stored, and an empty array is returned immediately when no value is present.The maximum value
maxValueis found so the count array can cover every possible index from0throughmaxValue.A count array of size
maxValue + 1is created, and every position is initialized with0for frequency storage.Every value from
arris used as an index, and the matching count position is increased to record one more occurrence.Prefix sums are built inside the count array so each index stores the number of values less than or equal to the same index.
The input array is scanned from right to left, and each value is placed at
count[value] - 1inside the output array before the count is decreased.The filled output array is returned after every value has been placed in sorted position.
Dry Run
Couting Sort
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Sorts a non-negative integer array with stable counting sort. vector<int> countSort(vector<int>& arr) { int n = arr.size(); // Empty input has no value requiring a sorted position. if (n == 0) { return arr; } int maxValue = arr[0]; // The largest value decides the count array size. for (int value : arr) { // A larger value expands the required count index range. if (value > maxValue) { maxValue = value; } } vector<int> count(maxValue + 1, 0); // Each value is counted at the matching count index. for (int value : arr) { count[value]++; } // Prefix sums convert frequencies into ending positions. for (int index = 1; index <= maxValue; index++) { count[index] = count[index] + count[index - 1]; } vector<int> output(n); // Reverse traversal preserves the relative order of equal values. for (int index = n - 1; index >= 0; index--) { int value = arr[index]; // The prefix count points one position beyond the final slot. int position = count[value] - 1; output[position] = value; // Place the next equal value in the previous available slot. count[value]--; } return output; }};// Driver codeint main() { // Input array vector<int> arr = {4, 2, 2, 8, 3, 3, 1}; // Solution object creation Solution obj; // Result printing vector<int> answer = obj.countSort(arr); for (int value : answer) { cout << value << " "; } cout << endl; return 0;}Complexity Analysis
Time Complexity: O(N + maxValue), where maxValue is the largest number present in the input array. The input is scanned to find this value and count frequencies, while the count array of size maxValue + 1 is processed for prefix sums and stable placement.
Space Complexity: O(N + maxValue) because the output array stores N values and the count array stores indexes from 0 through maxValue.
Interview follow-up Questions
Standard Counting Sort uses values as direct indexes, so negative values do not fit a direct count array. A shifted-index version can support negative values by subtracting the minimum value before indexing.
Be the first to add a comment.