Count Occurrences of Element in Sorted Array in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of counting occurrences in a sorted array

What is the output of the following Go code that counts occurrences of the number 3 in a sorted array?

DSA Go

package main
import "fmt"

func countOccurrences(arr []int, x int) int {
    left, right := 0, len(arr)-1
    first, last := -1, -1

    // Find first occurrence
    for left <= right {
        mid := (left + right) / 2
        if arr[mid] == x {
            first = mid
            right = mid - 1
        } else if arr[mid] < x {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    if first == -1 {
        return 0
    }

    left, right = 0, len(arr)-1
    // Find last occurrence
    for left <= right {
        mid := (left + right) / 2
        if arr[mid] == x {
            last = mid
            left = mid + 1
        } else if arr[mid] < x {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    return last - first + 1
}

func main() {
    arr := []int{1, 2, 3, 3, 3, 4, 5}
    fmt.Println(countOccurrences(arr, 3))
}

A 4

B 2

C 0

D 3

💡 Hint

Count how many times 3 appears consecutively in the sorted array.

The number 3 appears three times consecutively at indices 2, 3, and 4. The code finds the first and last occurrence indices and returns their difference plus one.

🧠 Conceptual

intermediate

Understanding the binary search approach for counting occurrences

Why does the algorithm use two binary searches to count occurrences of an element in a sorted array?

A To find the first and last positions of the element, then calculate the count from these indices.

B To sort the array twice before counting the element.

C To count the element by checking every element twice.

D To find the middle element twice and sum their values.

💡 Hint

Think about how to find the range of the element's positions efficiently.

The two binary searches locate the first and last occurrence of the element, allowing calculation of total occurrences by subtracting indices.

🔧 Debug

advanced

Identify the error in counting occurrences code

What error will this Go code produce when counting occurrences of 3 in the array?

DSA Go

package main
import "fmt"

func countOccurrences(arr []int, x int) int {
    left, right := 0, len(arr)-1
    first := -1

    // Find first occurrence
    for left <= right {
        mid := (left + right) / 2
        if arr[mid] == x {
            first = mid
            left = mid + 1 // Incorrect update
        } else if arr[mid] < x {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    if first == -1 {
        return 0
    }

    return 1
}

func main() {
    arr := []int{1, 2, 3, 3, 3, 4, 5}
    fmt.Println(countOccurrences(arr, 3))
}

A The code returns 0 even though 3 is present.

B The code causes a runtime panic due to index out of range.

C The code returns 1 instead of the correct count of 3.

D The code enters an infinite loop.

💡 Hint

Check how the first occurrence is found and what the function returns.

The code incorrectly updates 'left' when finding the first occurrence, causing it to find the last occurrence instead. Also, it returns 1 instead of the count.

❓ Predict Output

advanced

Output of counting occurrences for element not in array

What is the output of this Go code when counting occurrences of 6 in the sorted array?

DSA Go

package main
import "fmt"

func countOccurrences(arr []int, x int) int {
    left, right := 0, len(arr)-1
    first, last := -1, -1

    for left <= right {
        mid := (left + right) / 2
        if arr[mid] == x {
            first = mid
            right = mid - 1
        } else if arr[mid] < x {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    if first == -1 {
        return 0
    }

    left, right = 0, len(arr)-1
    for left <= right {
        mid := (left + right) / 2
        if arr[mid] == x {
            last = mid
            left = mid + 1
        } else if arr[mid] < x {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    return last - first + 1
}

func main() {
    arr := []int{1, 2, 3, 3, 3, 4, 5}
    fmt.Println(countOccurrences(arr, 6))
}

A -1

B 0

C 1

D 5

💡 Hint

Check what happens when the element is not found in the array.

The element 6 is not in the array, so the first occurrence index remains -1 and the function returns 0.

🧠 Conceptual

expert

Time complexity of counting occurrences in a sorted array

What is the time complexity of counting occurrences of an element in a sorted array using the two binary searches approach?

A O(log n)

B O(n)

C O(n log n)

D O(1)

💡 Hint

Consider how many times the array is divided during binary search.

Each binary search runs in O(log n) time, and since two binary searches are performed, the total time complexity remains O(log n).

Practice

1. What is the main advantage of using a binary search approach to count occurrences of an element in a sorted array?

easy

A. It counts all elements without searching.

B. It sorts the array automatically.

C. It reduces the search time to logarithmic complexity.

D. It works only on unsorted arrays.

Solution

1. Step 1: Understand binary search efficiency

   Binary search divides the search space in half each time, making it faster than linear search.

2. Step 2: Apply to counting occurrences

   By finding the first and last positions of the element, we can count occurrences efficiently.

3. Final Answer:

   It reduces the search time to logarithmic complexity. -> Option C

4. Quick Check:

   Binary search = O(log n) time [OK]

Hint: Binary search halves search space each step [OK]

Common Mistakes:

• Thinking binary search sorts the array
• Using linear search for counting in sorted array
• Assuming binary search works on unsorted arrays

2. Which Go code snippet correctly declares a function to count occurrences of an integer in a sorted slice?

easy

A. func countOccurrences(arr []int, target int) int { return 0 }

B. func countOccurrences(arr int[], target int) int { return 0 }

C. func countOccurrences(arr []int, target int) string { return "0" }

D. func countOccurrences(arr []int, target int) { return 0 }

Solution

1. Step 1: Check function signature syntax

   In Go, slices are declared as []int, and return type int is correct for count.

2. Step 2: Validate return statement matches return type

   Returning 0 as int matches the return type int.

3. Final Answer:

   func countOccurrences(arr []int, target int) int { return 0 } -> Option A

4. Quick Check:

   Correct Go function syntax [OK]

Hint: Use []int for slices and match return type [OK]

Common Mistakes:

• Using array syntax int[] instead of []int
• Mismatching return type and return value
• Omitting return type in function signature

3. What will be the output of the following Go code snippet?

func countOccurrences(arr []int, target int) int {
    left := 0
    right := len(arr) - 1
    first := -1
    for left <= right {
        mid := (left + right) / 2
        if arr[mid] == target {
            first = mid
            right = mid - 1
        } else if arr[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    if first == -1 {
        return 0
    }
    left = 0
    right = len(arr) - 1
    last := -1
    for left <= right {
        mid := (left + right) / 2
        if arr[mid] == target {
            last = mid
            left = mid + 1
        } else if arr[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return last - first + 1
}

func main() {
    arr := []int{1, 2, 2, 2, 3, 4, 5}
    count := countOccurrences(arr, 2)
    fmt.Println(count)
}

medium

A. 2

B. 3

C. 1

D. 0

Solution

1. Step 1: Find first occurrence of 2

   Binary search finds first index of 2 at position 1.

2. Step 2: Find last occurrence of 2

   Binary search finds last index of 2 at position 3.

3. Step 3: Calculate count

   Count = last - first + 1 = 3 - 1 + 1 = 3.

4. Final Answer:

   3 -> Option B

5. Quick Check:

   Occurrences of 2 = 3 [OK]

Hint: Find first and last index, then subtract [OK]

Common Mistakes:

• Returning index instead of count
• Not updating left/right correctly in binary search
• Confusing first and last occurrence indices

4. Identify the bug in the following Go function that counts occurrences of a target in a sorted array:

func countOccurrences(arr []int, target int) int {
    left, right := 0, len(arr)-1
    count := 0
    for left <= right {
        mid := (left + right) / 2
        if arr[mid] == target {
            count++
            break
        } else if arr[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return count
}

medium

A. It counts only one occurrence, not all.

B. It causes an infinite loop.

C. It returns the index instead of count.

D. It does not handle empty arrays.

Solution

1. Step 1: Analyze loop behavior

   The loop breaks after finding one occurrence, so count increments only once.

2. Step 2: Understand counting logic

   Counting all occurrences requires searching for first and last positions, not just one match.

3. Final Answer:

   It counts only one occurrence, not all. -> Option A

4. Quick Check:

   Loop breaks early, count = 1 [OK]

Hint: Break stops counting after first match [OK]

Common Mistakes:

• Using break instead of continuing search
• Not searching for first and last indices
• Assuming one match equals total count

5. Given a sorted array with possible duplicates, how would you modify the binary search approach to count occurrences of multiple target values efficiently? Choose the best approach.

hard

A. Perform separate binary searches for first and last occurrences of each target, then sum counts.

B. Use a linear scan for each target to count occurrences.

C. Sort the array again before counting each target.

D. Use a hash map to store counts after one full scan.

Solution

1. Step 1: Consider efficiency for multiple targets

   Binary search per target is O(k log n) for k targets, which can be costly.

2. Step 2: Use hash map after one scan

   A single linear scan builds a map of counts for all elements in O(n), allowing O(1) lookup per target.

3. Step 3: Compare approaches

   Hash map approach is more efficient for multiple queries than repeated binary searches.

4. Final Answer:

   Use a hash map to store counts after one full scan. -> Option D

5. Quick Check:

   Hash map = efficient multiple counts [OK]

Hint: Build counts once, then query fast [OK]

Common Mistakes:

• Repeating binary search for each target
• Sorting array multiple times unnecessarily
• Ignoring hash map for frequency counting