Count Occurrences of Element in Sorted Array in DSA Python - Execution Trace

Concept Flow - Count Occurrences of Element in Sorted Array

Start

↓

Input: Sorted Array, Target Element

↓

Find first occurrence index using binary search

↓

Find last occurrence index using binary search

↓

Calculate count = last_index - first_index + 1

↓

Return count

↓

End

We use two binary searches to find the first and last positions of the target element, then calculate how many times it appears.

Execution Sample

DSA Python

def count_occurrences(arr, target):
    def find_first():
        low, high = 0, len(arr) - 1
        while low <= high:
            mid = (low + high) // 2
            if arr[mid] < target:
                low = mid + 1
            else:
                high = mid - 1
        return low

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

    first = find_first()
    last = find_last()
    if first <= last:
        return last - first + 1
    else:
        return 0

This code finds the first and last positions of the target in the sorted array using binary search, then returns the count of occurrences.

Execution Table

Step	Operation	low	high	mid	Condition	Pointer Changes	Visual State
1	Start find_first	0	6	-	-	-	[2, 4, 4, 4, 6, 6, 7]
2	find_first mid calc	0	6	3	arr[3]=4 >= target=4	high = mid - 1 = 2	[2, 4, 4, 4, 6, 6, 7]
3	find_first mid calc	0	2	1	arr[1]=4 >= target=4	high = mid - 1 = 0	[2, 4, 4, 4, 6, 6, 7]
4	find_first mid calc	0	0	0	arr[0]=2 < target=4	low = mid + 1 = 1	[2, 4, 4, 4, 6, 6, 7]
5	find_first loop ends	1	0	-	low > high	-	[2, 4, 4, 4, 6, 6, 7]
6	Start find_last	0	6	-	-	-	[2, 4, 4, 4, 6, 6, 7]
7	find_last mid calc	0	6	3	arr[3]=4 <= target=4	low = mid + 1 = 4	[2, 4, 4, 4, 6, 6, 7]
8	find_last mid calc	4	6	5	arr[5]=6 > target=4	high = mid - 1 = 4	[2, 4, 4, 4, 6, 6, 7]
9	find_last mid calc	4	4	4	arr[4]=6 > target=4	high = mid - 1 = 3	[2, 4, 4, 4, 6, 6, 7]
10	find_last loop ends	4	3	-	low > high	-	[2, 4, 4, 4, 6, 6, 7]
11	Calculate count	-	-	-	first=1 <= last=3	count = 3 - 1 + 1 = 3	[2, 4, 4, 4, 6, 6, 7]
12	Return count	-	-	-	-	return 3	[2, 4, 4, 4, 6, 6, 7]

💡 Loop ends when low > high in both find_first and find_last searches.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 7	After Step 8	After Step 9	After Step 10	Final
low (find_first)	0	0	0	1	1	-	-	-	-	-
high (find_first)	6	2	0	0	0	-	-	-	-	-
mid (find_first)	-	3	1	0	-	-	-	-	-	-
low (find_last)	0	-	-	-	-	4	4	4	4	-
high (find_last)	6	-	-	-	-	6	4	3	3	-
mid (find_last)	-	-	-	-	-	3	5	4	-	-
first	-	-	-	-	1	-	-	-	-	1
last	-	-	-	-	-	-	-	-	3	3
count	-	-	-	-	-	-	-	-	-	3

Key Moments - 3 Insights

Why do we use two separate binary searches instead of one?

Because the first search finds the first position where the target appears (lowest index), and the second finds the last position (highest index). This ensures we count all occurrences correctly. See steps 2-5 for first occurrence and 7-10 for last occurrence.

Why does find_first move 'high' when arr[mid] >= target?

Because we want to find the earliest index where target appears, so if arr[mid] is equal or greater, we move high left to narrow down to the first occurrence. This is shown in steps 2 and 3 where high moves left.

What happens if the target is not in the array?

The first index will be greater than the last index, so the count calculation returns 0. This is checked in step 11 where first <= last is false.

Visual Quiz - 3 Questions

Look at the execution table, what is the value of 'mid' during step 3 in find_first?

A 1

B 3

C 0

D 2

💡 Hint

Check the 'mid' column in row with Step 3 in the execution_table.

At which step does the find_last function set 'high' to 3?

A Step 8

B Step 9

C Step 7

D Step 10

💡 Hint

Look at the 'Pointer Changes' column for steps 8 and 9 in the execution_table.

If the target was 5 instead of 4, what would the count be according to the variable_tracker?

A 3

B 1

C 0

D 2

💡 Hint

If target is not found, first index > last index, so count is 0 as explained in key_moments.

Concept Snapshot

Count Occurrences in Sorted Array:
- Use binary search twice: find first and last occurrence.
- find_first: move high left if arr[mid] >= target.
- find_last: move low right if arr[mid] <= target.
- Count = last_index - first_index + 1 if valid, else 0.
- Runs in O(log n) time due to binary search.

Full Transcript

To count how many times an element appears in a sorted array, we use two binary searches. The first finds the earliest position of the element, the second finds the last position. We then subtract these indices and add one to get the count. If the element is not found, the count is zero. This method is efficient and works by narrowing down the search space step-by-step, adjusting low and high pointers based on comparisons. The execution table shows each step's low, high, mid values and pointer changes, helping visualize how the search zones shrink until the positions are found.

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