Counting Sort Algorithm in DSA Go - Time & Space Complexity

Time Complexity: Counting Sort Algorithm

O(n + k)

Understanding Time Complexity

Counting Sort is a sorting method that uses counting to sort numbers quickly.

We want to know how the time it takes changes as the list gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

package main

func countingSort(arr []int, maxVal int) []int {
    count := make([]int, maxVal+1)
    for _, num := range arr {
        count[num]++
    }
    index := 0
    for num, freq := range count {
        for freq > 0 {
            arr[index] = num
            index++
            freq--
        }
    }
    return arr
}

This code sorts an array of numbers by counting how many times each number appears, then rebuilding the sorted array.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Two loops: one to count frequencies, one to rebuild the sorted array.
• How many times: First loop runs once for each element in input (n times). Second loop runs once for each possible number (k times), and inside it runs as many times as the frequency of that number.

How Execution Grows With Input

Explain the growth pattern intuitively.

Input Size (n)	Approx. Operations
10	About 10 + k operations
100	About 100 + k operations
1000	About 1000 + k operations

Pattern observation: The time grows mostly with the number of elements (n) plus the range of numbers (k).

Final Time Complexity

Time Complexity: O(n + k)

This means the time to sort depends on both how many numbers you have and the range of those numbers.

Common Mistake

[X] Wrong: "Counting Sort always runs in linear time O(n)."

[OK] Correct: The time also depends on the range of numbers (k). If k is very large compared to n, the algorithm can be slower.

Interview Connect

Understanding Counting Sort's time complexity helps you explain when it is efficient and when it is not, showing your grasp of algorithm choices.

Self-Check

"What if the range of numbers (k) is much larger than the number of elements (n)? How would the time complexity change?"

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