Counting Sort Algorithm in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Counting Sort on a small array

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

DSA Go

package main
import "fmt"
func countingSort(arr []int) []int {
    max := arr[0]
    for _, v := range arr {
        if v > max {
            max = v
        }
    }
    count := make([]int, max+1)
    for _, v := range arr {
        count[v]++
    }
    index := 0
    for i, c := range count {
        for c > 0 {
            arr[index] = i
            index++
            c--
        }
    }
    return arr
}
func main() {
    arr := []int{4, 2, 2, 8, 3, 3, 1}
    sorted := countingSort(arr)
    fmt.Println(sorted)
}

A [1 2 3 3 4 8 8]

B [4 2 2 8 3 3 1]

C [8 4 3 3 2 2 1]

D [1 2 2 3 3 4 8]

💡 Hint

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

The counting sort algorithm counts the frequency of each number and then places them back in sorted order. The output is the sorted array [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 only if the input array is already sorted.

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

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

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 the following Go code produce when run, and why? func countingSort(arr []int) []int { max := 0 for _, v := range arr { if v > max { max = v } } count := make([]int, max) for _, v := range arr { count[v]++ } index := 0 for i, c := range count { for c > 0 { arr[index] = i index++ c-- } } return arr }

A Runtime panic: nil pointer dereference

B Runtime panic: index out of range because count slice size is max instead of max+1

C Compilation error due to missing import statement

D No error, outputs sorted array correctly

💡 Hint

Check how the count slice size relates to the max value in the array.

The count slice is created with length max, but since array indices go from 0 to max, it should be max+1. Accessing count[max] causes index out of range panic.

🚀 Application

advanced

Counting Sort Usage Scenario

Which scenario is best suited for using counting sort instead of comparison-based sorting algorithms?

A Sorting a large list of integers where the range of values is small compared to the list size.

B Sorting a list of integers where the range is very large compared to the list size.

C Sorting a list of strings alphabetically.

D Sorting a list of floating-point numbers with many decimal places.

💡 Hint

Counting sort works best when the range of input values is not too large.

Counting sort is efficient when the range of input values is small relative to the number of elements, allowing linear time sorting.

❓ Predict Output

expert

Output of Counting Sort with Negative Numbers

What will happen if you run the following Go code that tries to apply counting sort on an array containing negative numbers? arr := []int{3, -1, 2, -1, 0} sorted := countingSort(arr) fmt.Println(sorted) Assume countingSort is the standard implementation that uses the maximum value to create the count array size.

A Runtime panic: index out of range due to negative index access in count array

B [ -1 -1 0 2 3 ]

C [ 0 2 3 -1 -1 ]

D Compilation error due to negative numbers

💡 Hint

Counting sort uses array indices for counts, which cannot be negative.

Counting sort does not handle negative numbers because it uses array indices to count occurrences. Negative numbers cause invalid negative indices, leading to runtime panic.

Practice

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

easy

A. Swapping adjacent elements if they are in wrong order

B. Comparing each element with every other element

C. Counting the number of occurrences of each element to sort

D. Dividing the array into halves and sorting recursively

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 in order

   Using these counts, it places elements directly in sorted order without comparisons.

3. Final Answer:

   Counting the number of occurrences of each element to sort -> Option C

4. Quick Check:

   Counting occurrences = D [OK]

Hint: Counting sort counts elements, no comparisons needed [OK]

Common Mistakes:

• Thinking it compares elements like bubble sort
• Confusing with divide and conquer methods
• Assuming it swaps elements repeatedly

2. Which of the following is the correct way to declare the count array in Go for counting sort when input values range from 0 to 9?

easy

A. count := make([]int, 10)

B. count := make([]int, 9)

C. count := make([]int, 11)

D. count := make([]int, 0)

Solution

1. Step 1: Determine size of count array

   For values 0 to 9, we need 10 slots to count each number.

2. Step 2: Use make function with correct length

   Using make([]int, 10) creates an integer slice of length 10, perfect for counting 0-9.

3. Final Answer:

   count := make([]int, 10) -> Option A

4. Quick Check:

   Length 10 for 0-9 range = A [OK]

Hint: Count array length = max value + 1 [OK]

Common Mistakes:

• Using length 9 misses counting number 9
• Using length 0 creates empty slice
• Using length 11 wastes space unnecessarily

3. What will be the output of the following Go code snippet using counting sort logic?

arr := []int{4, 2, 2, 8, 3, 3, 1}
count := make([]int, 9)
for _, v := range arr {
    count[v]++
}
var sorted []int
for i, c := range count {
    for j := 0; j < c; j++ {
        sorted = append(sorted, i)
    }
}
fmt.Println(sorted)

medium

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

B. [4 2 2 8 3 3 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: Build sorted slice using counts

   Append each number i count[i] times: 1 once, 2 twice, 3 twice, 4 once, 8 once.

3. Final Answer:

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

4. Quick Check:

   Sorted array = [1 2 2 3 3 4 8] [OK]

Hint: Count then expand counts in order to sort [OK]

Common Mistakes:

• Printing original array instead of sorted
• Including zero counts as elements
• Miscounting duplicates

4. Identify the bug in this Go code snippet implementing counting sort:

arr := []int{3, 1, 4, 1, 5}
count := make([]int, 6)
for _, v := range arr {
    count[v]++
}
var sorted []int
for i, c := range count {
    for j := 0; j <= c; j++ {
        sorted = append(sorted, i)
    }
}
fmt.Println(sorted)

medium

A. Inner loop uses <= instead of < causing extra elements

B. Count array size is too small for max value 5

C. Appending index instead of value

D. Missing initialization of sorted slice

Solution

1. Step 1: Check count array size

   Count array size 6 covers indices 0-5, correct for max value 5.

2. Step 2: Analyze inner loop condition

   Inner loop uses j <= c, which runs one extra time than needed, adding one extra element per non-zero count.

3. Final Answer:

   Inner loop uses <= instead of < causing extra elements -> Option A

4. Quick Check:

   Loop condition off by one = A [OK]

Hint: Use < not <= in loops counting occurrences [OK]

Common Mistakes:

• Ignoring off-by-one errors in loops
• Assuming count array size error causes runtime panic
• Confusing index and value in append

5. Given an array with negative and positive integers: arr := []int{-2, -1, 0, 1, 2}, how can you adapt counting sort to sort this array correctly?

hard

A. Use counting sort directly without changes

B. Shift all values by adding 2 to make them non-negative, then apply counting sort

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

D. Counting sort cannot be used with negative numbers

Solution

1. Step 1: Identify problem with negatives in counting sort

   Counting sort uses array indices as counts, so negative values cause invalid indices.

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

   Add the absolute value of the minimum (2) to all elements, making them 0 to 4, then apply counting sort.

3. Final Answer:

   Shift all values by adding 2 to make them non-negative, then apply counting sort -> Option B

4. Quick Check:

   Shift negatives to zero-based index = B [OK]

Hint: Shift negatives to zero or positive before counting [OK]

Common Mistakes:

• Trying to use negative indices directly
• Ignoring negative values in sorting
• Assuming counting sort works on all integers without adjustment