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

Challenge - 5 Problems

❓ Predict Output

intermediate

Count occurrences of 3 in a sorted array

What is the output of the following code that counts how many times 3 appears in the sorted array?

DSA Python

def count_occurrences(arr, x):
    return arr.count(x)

arr = [1, 2, 3, 3, 3, 4, 5]
print(count_occurrences(arr, 3))

A 3

B 2

C 1

D 0

💡 Hint

Use the list method that counts how many times an element appears.

The number 3 appears three times in the list, so the count is 3.

❓ Predict Output

intermediate

Count occurrences using binary search boundaries

What is the output of this code that uses binary search to count occurrences of 2 in a sorted array?

DSA Python

def binary_search_left(arr, x):
    low, high = 0, len(arr)
    while low < high:
        mid = (low + high) // 2
        if arr[mid] < x:
            low = mid + 1
        else:
            high = mid
    return low

def binary_search_right(arr, x):
    low, high = 0, len(arr)
    while low < high:
        mid = (low + high) // 2
        if arr[mid] <= x:
            low = mid + 1
        else:
            high = mid
    return low

arr = [1, 2, 2, 2, 3, 4]
count = binary_search_right(arr, 2) - binary_search_left(arr, 2)
print(count)

A 0

B 2

C 1

D 3

💡 Hint

Count is right boundary minus left boundary of the target element.

The number 2 appears three times between the left and right binary search boundaries.

🔧 Debug

advanced

Find the bug in counting occurrences with binary search

What error does this code raise when counting occurrences of 5 in the sorted array?

DSA Python

def count_occurrences(arr, x):
    left = 0
    right = len(arr) - 1
    count = 0
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == x:
            count += 1
            left = mid + 1
        elif arr[mid] < x:
            left = mid + 1
        else:
            right = mid - 1
    return count

arr = [1, 2, 3, 4, 6, 7]
print(count_occurrences(arr, 5))

A 0

B Infinite loop

C 1

D IndexError

💡 Hint

Check if the loop can get stuck when the element is not found.

The code increments count only when arr[mid] == x but moves left pointer forward, causing the loop to never end if x is not in the array.

🧠 Conceptual

advanced

Why use binary search to count occurrences in sorted array?

Which reason best explains why binary search is efficient for counting occurrences of an element in a sorted array?

A It uses recursion to count all elements

B It sorts the array first, then counts the element

C It finds the first and last positions of the element quickly, so count is last - first + 1

D It converts the array to a set to count unique elements

💡 Hint

Think about how binary search narrows down positions in a sorted list.

Binary search quickly finds the boundaries of the target element, so counting is just subtracting indices.

🚀 Application

expert

Count occurrences of multiple elements efficiently

Given a sorted array and a list of query elements, which approach efficiently counts occurrences of each query element?

A For each query, use binary search to find left and right boundaries and subtract to get count

B Sort the array for each query and count occurrences

C For each query, scan the entire array and count matches

D Convert array to a dictionary with counts, then lookup each query

💡 Hint

Think about repeated queries and how to avoid scanning the whole array each time.

Using binary search for each query on a sorted array is efficient (O(Q log N)) compared to scanning (O(Q N)). Preprocessing with a dictionary is possible but not always efficient if queries are few or array is large.

Practice

1. What does the problem "Count Occurrences of Element in Sorted Array" ask you to find?

easy

A. The number of times a given element appears in a sorted array

B. The sum of all elements in the array

C. The largest element in the array

D. The position of the first element in the array

Solution

1. Step 1: Understand the problem statement

   The problem asks to find how many times a specific element appears in a sorted array.

2. Step 2: Identify the required output

   The output is the count of occurrences of that element, not its position or sum.

3. Final Answer:

   The number of times a given element appears in a sorted array -> Option A

4. Quick Check:

   Count occurrences = number of times element appears [OK]

Hint: Count how many times the element repeats in the sorted list [OK]

Common Mistakes:

• Confusing count with element position
• Trying to sum elements instead of counting
• Ignoring that array is sorted

2. Which of the following Python code snippets correctly counts occurrences of x in a sorted list arr using built-in methods?

easy

A. count = arr.find(x)

B. count = arr.count(x)

C. count = arr.index(x)

D. count = arr.length(x)

Solution

1. Step 1: Recall Python list methods

   count() returns how many times an element appears in a list.

2. Step 2: Check other methods

   find() and index() find positions, not counts; length() is invalid.

3. Final Answer:

   count = arr.count(x) -> Option B

4. Quick Check:

   Use count() to get occurrences [OK]

Hint: Use list.count(element) to get occurrences fast [OK]

Common Mistakes:

• Using index() instead of count()
• Trying to use find() which is for strings
• Using length() which is not a list method

3. What is the output of the following code?

def count_occurrences(arr, x):
    return arr.count(x)

arr = [1, 2, 2, 2, 3, 4]
x = 2
print(count_occurrences(arr, x))

medium

A. 0

B. 2

C. 1

D. 3

Solution

1. Step 1: Understand the input array and element

   The array is [1, 2, 2, 2, 3, 4] and the element to count is 2.

2. Step 2: Count occurrences of 2 in the array

   2 appears three times in the array.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Count of 2 in array = 3 [OK]

Hint: Count how many times 2 appears in the list [OK]

Common Mistakes:

• Counting unique elements instead of occurrences
• Miscounting the number of 2s
• Confusing count with index

4. Find the error in this code that tries to count occurrences of x in a sorted array arr:

def count_occurrences(arr, x):
    count = 0
    for i in range(len(arr)):
        if arr[i] == x:
            count += 1
        else:
            break
    return count

arr = [1, 2, 2, 2, 3, 4]
x = 2
print(count_occurrences(arr, x))

medium

A. The loop breaks too early, missing some occurrences

B. The count variable is not initialized

C. The function does not return any value

D. The comparison operator is incorrect

Solution

1. Step 1: Analyze the loop and break condition

   The loop breaks on first element not equal to x, so it counts only consecutive occurrences from start.

2. Step 2: Check the input array and x

   Since x=2 and array starts with 1, the loop breaks immediately, count remains 0.

3. Final Answer:

   The loop breaks too early, missing some occurrences -> Option A

4. Quick Check:

   Break stops counting early, so count is wrong [OK]

Hint: Don't break loop; count all matching elements [OK]

Common Mistakes:

• Breaking loop on first non-match in unsorted array
• Not counting all occurrences
• Assuming array starts with x

5. Given a sorted array arr = [1, 2, 2, 2, 3, 4, 4, 5], which approach efficiently counts occurrences of x = 4 without scanning the entire array?

hard

A. Use a for loop to count all 4s by scanning from start to end

B. Use arr.count(4) which scans entire array internally

C. Use binary search to find first and last positions of 4, then calculate count

D. Sort the array again and count 4s

Solution

1. Step 1: Understand the array is sorted

   Since the array is sorted, all 4s are together in a block.

2. Step 2: Use binary search to find first and last occurrence

   Binary search finds first and last index of 4 quickly, then count = last - first + 1.

3. Step 3: Compare other options

   For loop and count() scan entire array, sorting again is unnecessary and inefficient.

4. Final Answer:

   Use binary search to find first and last positions of 4, then calculate count -> Option C

5. Quick Check:

   Binary search + index difference = count [OK]

Hint: Find first and last index with binary search, subtract [OK]

Common Mistakes:

• Scanning entire array instead of using binary search
• Sorting array again unnecessarily
• Using count() without considering efficiency