HackerRank Counting Sort 1 Java Solution Explained
Problem Overview
Original Problem: Counting Sort 1 | HackerRank
Difficulty: Easy
Category: Arrays, Counting Sort
Description: Given an array of integers, create a frequency array that counts the occurrences of each value within a fixed range (0 to 99). Return a frequency array of 100 elements, where each index represents a value and its corresponding value is the count of occurrences in the input array.
This problem, part of HackerRank’s One Week Preparation Kit, introduces beginners to the counting sort technique, a non-comparison-based sorting method useful for coding interviews.
Understanding the Problem
The Counting Sort 1 problem requires you to count how many times each integer (from 0 to 99) appears in an input array and return a frequency array of size 100. For example, given the array [1, 2, 3, 1, 1], the frequency array would have 3 at index 1 (since 1 appears three times), 1 at index 2, 1 at index 3, and 0 at all other indices (0 to 99). This is a simplified version of counting sort, focusing on generating the frequency array rather than producing a sorted output. The problem is ideal for learning how to use arrays for counting and understanding the basics of non-comparison sorting.
Input and Output
Input:
First line: An integer n, the size of the array.
Second line: n space-separated integers arr[i].
Output:
A list of 100 integers representing the frequency of each value from 0 to 99 in the input array.
Constraints:
100 ≤ n ≤ 1,000,000
0 ≤ arr[i] ≤ 99
The output array must always have exactly 100 elements.
Initial Reasoning
To solve this, we need to:
Create a frequency array of size 100 initialized with zeros.
Iterate through the input array, incrementing the count in the frequency array at the index corresponding to each element’s value.
Return the frequency array as a List<Integer>.
Use the fact that input values are limited to 0–99 to ensure the frequency array is fixed-size.
This approach leverages the counting sort technique, achieving O(n) time complexity and O(1) extra space (since the output array size is fixed at 100).
Thought Process
Here’s the step-by-step logic:
Initialize Frequency Array: Create a list or array of size 100, initialized with zeros, where each index represents a possible input value (0 to 99).
Count Frequencies: Iterate through the input array once, and for each element arr[i], increment the count at index arr[i] in the frequency array.
Return the Result: The frequency array is the required output, with each index i containing the count of how many times i appears in the input.
Handle Constraints:
The input array can be large (up to 10^6 elements), so a single-pass solution is ideal.
Input values are constrained to 0–99, ensuring the frequency array is fixed at 100 elements.
The output must be a List<Integer> to match the function signature.
Edge Cases:
If n = 1, the frequency array will have a count of 1 at the single element’s value and 0 elsewhere.
If a value doesn’t appear (e.g., no 5 in the input), its frequency remains 0.
The constraints guarantee valid inputs, so no additional validation is needed.
Pseudocode
// countingSort method:
Initialize frequency array
For each element in the input array
Increment the corresponding position in the frequency array
Return frequency array
Solution Code
// Note: This is one of many possible solutions
// Note: Variable names have been updated from the original template for clarity and to follow Java naming conventions (e.g., 'n' to 'size')
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;
class Result {
public static List countingSort(List<Integer> arr) {
// Initialize frequency array of size 100 with zeros
List<Integer> frequency = new ArrayList<>(Collections.nCopies(100, 0));
// Count occurrences of each value
for (int num : arr) {
frequency.set(num, frequency.get(num) + 1);
}
return frequency;
}
}
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
int size = Integer.parseInt(bufferedReader.readLine().trim());
List<Integer> arr = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
.map(Integer::parseInt)
.collect(toList());
List<Integer> result = Result.countingSort(arr);
bufferedWriter.write(
result.stream()
.map(Object::toString)
.collect(joining(" "))
+ "\n");
bufferedReader.close();
bufferedWriter.close();
}
} Step-by-Step Explanation
Let’s break down the Java solution for beginners:
Input Handling:
The main method reads:
The array size, using Integer.parseInt(bufferedReader.readLine().trim()).
A line of space-separated integers, processed into a List<Integer> using Stream.of and map(Integer::parseInt).
Initialize Frequency Array:
In countingSort, create a List<Integer> of size 100, initialized with zeros, using Collections.nCopies(100, 0).
This creates a list where each index i will store the count of value i in the input array.
Count Frequencies:
Iterate through the input array using a for-each loop.
For each element num, increment the count at index num in the frequency list using frequency.set(num, frequency.get(num) + 1).
For example, if num = 1, increment frequency[1] by 1.
Return the Result:
Return the frequency list, which contains 100 elements, where frequency[i] is the count of how many times i appears in arr.
Output Handling:
In the main method, write the result as space-separated integers using result.stream().map(Object::toString).collect(joining(" ")).
Add a newline with "\n".
Close bufferedReader and bufferedWriter to prevent resource leaks.
Common Mistakes to Avoid
Here are common pitfalls for beginners:
Incorrect Array Size: Creating a frequency array smaller or larger than 100 fails the requirement to return exactly 100 elements, even if some values don’t appear. Always initialize with 100 elements.
Using Comparison Sorting: Sorting the array (e.g., with Collections.sort) is unnecessary and less efficient (O(n log n)) than the O(n) counting approach.
Not Handling Large Inputs: For n up to 1,000,000, ensure the solution is efficient. The single-pass loop avoids performance issues.
Real-World Application
Counting sort techniques, like the one in this problem, are used in data processing and analytics. For example, in database systems, counting frequencies of values (e.g., product sales by category) helps generate histograms or summary statistics. In machine learning, frequency arrays can represent feature distributions. This problem teaches non-comparison sorting, a technique used in scenarios with fixed or limited value ranges, such as radix sort or histogram generation.
FAQs
Q: Why return a frequency array of size 100?
A: The problem specifies a fixed output size of 100 to cover all possible input values (0 to 99), ensuring counts for all values, even those not present in the input.
Q: Can I use an int[] instead of a List<Integer>?
A: Yes, an int[] could be used internally for counting, but you’d need to convert it to a List<Integer> to match the function’s return type. The List-based approach simplifies compatibility with the template.
Q: Why is counting sort faster than comparison sorts?
A: Counting sort is O(n) because it doesn’t compare elements; it counts occurrences using array indices. Comparison sorts like quicksort are O(n log n) in the best case.