Counting Sort Algorithm in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Counting Sort on a small array

What is the output of the following Java code that uses counting sort on the array [4, 2, 2, 8, 3, 3, 1]?

DSA Java

import java.util.Arrays;
public class Main {
    public static void countingSort(int[] arr) {
        int max = Arrays.stream(arr).max().getAsInt();
        int[] count = new int[max + 1];
        for (int num : arr) {
            count[num]++;
        }
        int index = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0) {
                arr[index++] = i;
                count[i]--;
            }
        }
    }
    public static void main(String[] args) {
        int[] arr = {4, 2, 2, 8, 3, 3, 1};
        countingSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

A [8, 4, 3, 3, 2, 2, 1]

B [1, 2, 2, 3, 3, 4, 8]

C [1, 2, 3, 4, 8]

D [1, 1, 2, 2, 3, 3, 4, 8]

💡 Hint

Counting sort counts how many times each number appears and then rebuilds the array in order.

Counting sort creates a count array for each number's frequency, then writes numbers back in sorted order. The input array is sorted as [1, 2, 2, 3, 3, 4, 8].

🧠 Conceptual

intermediate

Counting Sort Stability Property

Which statement correctly describes the stability property of counting sort?

A Counting sort is stable because it preserves the relative order of equal elements.

B Counting sort is unstable because it rearranges equal elements randomly.

C Counting sort is stable only if the input array is already sorted.

D Counting sort is unstable because it uses a hash map internally.

💡 Hint

Stability means equal elements keep their original order after sorting.

Counting sort is stable because it places elements in the output array in the order they appear in the input, preserving relative order of duplicates.

🔧 Debug

advanced

Identify the bug in this counting sort implementation

What error will occur when running this counting sort code on input [3, 1, 2]?

DSA Java

public static void countingSort(int[] arr) {
    int max = 0;
    for (int num : arr) {
        if (num > max) max = num;
    }
    int[] count = new int[max + 1];
    for (int num : arr) {
        count[num]++;
    }
    int index = 0;
    for (int i = 0; i < count.length; i++) {
        while (count[i] > 0) {
            arr[index++] = i;
            count[i]--;
        }
    }
}

A ArrayIndexOutOfBoundsException

B Infinite loop

C No error, outputs [1, 2, 3]

D NullPointerException

💡 Hint

Check how the count array size is defined compared to max value.

The count array size is max, but indices go up to max, causing out-of-bounds access when num == max.

🚀 Application

advanced

Counting Sort with Negative Numbers

How can counting sort be adapted to sort an array containing negative numbers like [-5, -10, 0, -3, 8, 5, -1, 10]?

A Use a hash map to store counts for negative keys directly.

B Counting sort cannot be used with negative numbers at all.

C Shift all numbers by adding the absolute value of the minimum number before sorting, then shift back after sorting.

D Sort only the positive numbers and append negative numbers at the start.

💡 Hint

Counting sort needs non-negative indices for counting array.

By shifting all numbers to be non-negative, counting sort can count frequencies correctly. After sorting, shift back to original values.

🧠 Conceptual

expert

Time Complexity of Counting Sort

What is the time complexity of counting sort for sorting n elements with maximum value k, and why?

A O(n^2) because it uses nested loops to count elements.

B O(n log n) because it uses comparisons to sort elements.

C O(k^2) because it iterates over the count array multiple times.

D O(n + k) because it counts frequencies and then reconstructs the sorted array.

💡 Hint

Counting sort does not compare elements but uses counting arrays.

Counting sort runs in linear time relative to input size n plus the range k of input values, making it O(n + k).

Practice

1. What is the main idea behind the Counting Sort algorithm?

easy

A. Count the occurrences of each element and use counts to place elements in order

B. Compare each element with every other element to sort

C. Divide the array into halves and sort recursively

D. Swap adjacent elements if they are in wrong order repeatedly

Solution

1. Step 1: Understand Counting Sort principle

   Counting Sort counts how many times each value appears in the input.

2. Step 2: Use counts to place elements

   These counts help to place elements directly in the sorted output without comparisons.

3. Final Answer:

   Count the occurrences of each element and use counts to place elements in order -> Option A

4. Quick Check:

   Counting occurrences = main idea [OK]

Hint: Counting Sort uses counts, not comparisons, to sort [OK]

Common Mistakes:

• Thinking Counting Sort compares elements
• Confusing Counting Sort with Quick Sort or Merge Sort
• Assuming Counting Sort works well with all data types

2. Which of the following is the correct way to declare the count array for Counting Sort in Java if the input values range from 0 to 9?

easy

A. int[] count = new int[10];

B. int count[] = new int(10);

C. int count = new int[10];

D. int[] count = new int();

Solution

1. Step 1: Understand Java array declaration syntax

   In Java, arrays are declared with type[], name = new type[size];

2. Step 2: Check each option for correct syntax

   int[] count = new int[10]; uses correct syntax: int[] count = new int[10]; int count[] = new int(10); uses parentheses instead of brackets, invalid. int count = new int[10]; misses brackets on left side. int[] count = new int(); misses size in brackets.

3. Final Answer:

   int[] count = new int[10]; -> Option A

4. Quick Check:

   Correct Java array syntax = int[] count = new int[10]; [OK]

Hint: Use square brackets and specify size for arrays in Java [OK]

Common Mistakes:

• Using parentheses instead of square brackets
• Not specifying array size when creating
• Incorrect placement of brackets in declaration

3. What will be the output of the following Java code snippet using Counting Sort?

int[] arr = {4, 2, 2, 8, 3, 3, 1};
int max = 8;
int[] count = new int[max + 1];
for (int num : arr) {
    count[num]++;
}
int index = 0;
for (int i = 0; i <= max; i++) {
    while (count[i] > 0) {
        arr[index++] = i;
        count[i]--;
    }
}
System.out.println(java.util.Arrays.toString(arr));

medium

A. [4, 2, 2, 8, 3, 3, 1]

B. [8, 4, 3, 3, 2, 2, 1]

C. [1, 2, 3, 4, 8]

D. [1, 2, 2, 3, 3, 4, 8]

Solution

1. Step 1: Count occurrences of each number

   Count array after loop: count[1]=1, count[2]=2, count[3]=2, count[4]=1, count[8]=1, others=0.

2. Step 2: Rebuild sorted array using counts

   Fill arr with 1 once, 2 twice, 3 twice, 4 once, 8 once in order.

3. Final Answer:

   [1, 2, 2, 3, 3, 4, 8] -> Option D

4. Quick Check:

   Sorted array matches [1, 2, 2, 3, 3, 4, 8] [OK]

Hint: Count frequencies, then overwrite array in order [OK]

Common Mistakes:

• Not initializing count array size correctly
• Forgetting to decrement count during placement
• Printing original array without sorting

4. Identify the error in this Counting Sort code snippet and select the correct fix:

int[] arr = {3, 1, 2};
int max = 3;
int[] count = new int[max];
for (int num : arr) {
    count[num]++;
}

medium

A. Change 'count[num]++' to 'count[num - 1]++' to fix indexing

B. Change 'int[] count = new int[max];' to 'int[] count = new int[max + 1];' to include max index

C. Initialize count array with size 'max - 1' instead of 'max' to save space

D. No error, code is correct as is

Solution

1. Step 1: Check count array size for indexing

   Array 'count' size is max=3, so indices 0,1,2 are valid but input has value 3 which is out of bounds.

2. Step 2: Fix count array size to include max index

   Size should be max+1=4 to allow index 3 access safely.

3. Final Answer:

   Change 'int[] count = new int[max];' to 'int[] count = new int[max + 1];' to include max index -> Option B

4. Quick Check:

   Array size must cover max value index [OK]

Hint: Count array size = max value + 1 to avoid index errors [OK]

Common Mistakes:

• Using count array size equal to max value only
• Adjusting indices incorrectly instead of size
• Ignoring ArrayIndexOutOfBoundsException

5. Given an array arr = {5, 3, 0, 2, 3, 0, 1}, how would you modify the Counting Sort algorithm to sort it if the input can contain negative numbers as well? Choose the best approach.

hard

A. Use a hash map instead of an array for counts

B. Ignore negative numbers as Counting Sort cannot handle them

C. Shift all numbers by adding the absolute value of the minimum negative number before counting

D. Sort only the positive numbers and append negatives at the end

Solution

1. Step 1: Understand Counting Sort limitation with negatives

   Counting Sort uses array indices as counts, so negative indices are invalid.

2. Step 2: Shift values to non-negative range

   Find minimum value, add its absolute value to all elements to make them non-negative, then apply Counting Sort.

3. Final Answer:

   Shift all numbers by adding the absolute value of the minimum negative number before counting -> Option C

4. Quick Check:

   Shift negatives to positive range for Counting Sort [OK]

Hint: Add offset to handle negatives before counting [OK]

Common Mistakes:

• Trying to use negative indices in count array
• Ignoring negative values in input
• Using incorrect data structures without reason