Why Count Occurrences of Element in Sorted Array in DSA Python?

The Big Idea

What if you could count repeated items in a huge sorted list without checking each one?

The Scenario

Imagine you have a long list of sorted numbers, like a phone book sorted by last name. You want to find out how many times a particular name appears.

Doing this by checking each name one by one would take a lot of time.

The Problem

Manually counting each occurrence means looking through every item, even if the list is very long.

This is slow and tiresome, and easy to make mistakes by losing track or skipping items.

The Solution

By using a smart method that takes advantage of the list being sorted, we can quickly find where the target starts and ends.

This way, we count occurrences without checking every item, saving time and effort.

Before vs After

✗ Before

count = 0
for number in sorted_list:
    if number == target:
        count += 1
print(count)

✓ After

def count_occurrences(sorted_list, target):
    start = find_first(sorted_list, target)
    end = find_last(sorted_list, target)
    if start == -1:
        return 0
    return end - start + 1

What It Enables

This technique lets you quickly find how many times a value appears in a sorted list, even if the list is huge.

Real Life Example

In a library catalog sorted by book titles, quickly finding how many copies of a specific book are available without scanning every entry.

Key Takeaways

Manual counting is slow and error-prone for large sorted lists.

Using the sorted order helps find occurrences fast by locating start and end positions.

This method saves time and reduces mistakes when counting repeated elements.

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