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

Concept Flow - Count Occurrences of Element in Sorted Array

Start

↓

Input: Sorted Array, Target Element

↓

Find First Occurrence Index

↓

Find Last Occurrence Index

↓

Calculate Count = Last - First + 1

↓

Return Count

↓

End

The process finds the first and last positions of the target in the sorted array, then calculates how many times it appears.

Execution Sample

DSA C

int countOccurrences(int arr[], int n, int x) {
  int first = findFirst(arr, n, x);
  if (first == -1) return 0;
  int last = findLast(arr, n, x);
  return last - first + 1;
}

This code counts how many times x appears in the sorted array arr of size n.

Execution Table

Step	Operation	Index Checked	Condition	Result	Visual State
1	Find First Occurrence	mid=4	arr[4]=3 == 3?	Yes, move left to find first	[1,2,3,3,3,3,4,5]
2	Find First Occurrence	mid=2	arr[2]=3 == 3?	Yes, move left	[1,2,3,3,3,3,4,5]
3	Find First Occurrence	mid=1	arr[1]=2 < 3?	Yes, move right	[1,2,3,3,3,3,4,5]
4	Find First Occurrence	mid=2	arr[2]=3 == 3?	Yes, found first at index 2	[1,2,3,3,3,3,4,5]
5	Find Last Occurrence	mid=5	arr[5]=3 == 3?	Yes, move right to find last	[1,2,3,3,3,3,4,5]
6	Find Last Occurrence	mid=6	arr[6]=4 > 3?	Yes, move left	[1,2,3,3,3,3,4,5]
7	Find Last Occurrence	mid=5	arr[5]=3 == 3?	Yes, found last at index 5	[1,2,3,3,3,3,4,5]
8	Calculate Count	-	last=5, first=2	Count = 5 - 2 + 1 = 4	[1,2,3,3,3,3,4,5]
9	Return Count	-	-	4	[1,2,3,3,3,3,4,5]
10	End	-	-	Done	[1,2,3,3,3,3,4,5]

💡 Search ends when first and last occurrence indices are found, count calculated.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
first	undefined	undefined	undefined	undefined	2	2	2	2	2
last	undefined	undefined	undefined	undefined	undefined	undefined	undefined	5	5
count	undefined	undefined	undefined	undefined	undefined	undefined	undefined	undefined	4
mid	undefined	4	2	1	2	5	6	5	5

Key Moments - 3 Insights

Why do we need to find both first and last occurrence instead of just one?

Because the array is sorted, the target can appear multiple times consecutively. Finding only one occurrence doesn't tell how many times it appears. The execution_table rows 1-7 show how first and last indices are found separately to calculate the count.

What happens if the target element is not in the array?

The findFirst function returns -1, so the countOccurrences function returns 0 immediately. This is handled in the execution_sample code where if (first == -1) return 0.

Why do we add 1 when calculating count as last - first + 1?

Because indices are zero-based, the number of elements between first and last inclusive is last - first + 1. For example, if first=2 and last=5, count is 4. This is shown in execution_table row 8.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the value of 'first'?

A 4

B 1

C 2

D -1

💡 Hint

Check the 'Result' column at step 4 where first occurrence is found at index 2.

At which step does the condition arr[mid] > x become true during finding last occurrence?

A Step 6

B Step 5

C Step 7

D Step 3

💡 Hint

Look at step 6 in execution_table where arr[6]=4 > 3 triggers moving left.

If the target element was not present, what would be the returned count?

A 1

B 0

C -1

D Undefined

💡 Hint

Refer to the execution_sample code where if (first == -1) the count is 0.

Concept Snapshot

Count Occurrences in Sorted Array:
- Use binary search to find first occurrence index
- Use binary search to find last occurrence index
- Count = last - first + 1
- If element not found, count = 0
- Efficient O(log n) time due to binary search

Full Transcript

To count how many times an element appears in a sorted array, we find the first and last positions where it appears using binary search. Then we calculate the count by subtracting the first index from the last and adding one. If the element is not found, the count is zero. This method is efficient because it uses binary search twice, each in logarithmic time.

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 uses less memory than linear search

B. It sorts the array automatically

C. It reduces the search time from linear to logarithmic

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, reducing time complexity to O(log n).

2. Step 2: Compare with linear search

   Linear search checks each element one by one, taking O(n) time, which is slower for large arrays.

3. Final Answer:

   It reduces the search time from linear to logarithmic -> Option C

4. Quick Check:

   Binary search = faster search [OK]

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

Common Mistakes:

• Thinking binary search sorts the array
• Confusing memory usage with speed
• Assuming binary search works on unsorted arrays

2. Which of the following C code snippets correctly declares a function to count occurrences of an integer in a sorted array?

easy

A. void countOccurrences(int arr[], int n, int x);

B. int countOccurrences(int arr[], int n, int x);

C. int countOccurrences(int arr, int n, int x);

D. int countOccurrences(int arr[], int x);

Solution

1. Step 1: Check function return type and parameters

   The function should return an int (count), take array, size, and target element as parameters.

2. Step 2: Validate parameter types

   Array parameter must be int arr[] or int *arr, size as int n, and target as int x.

3. Final Answer:

   int countOccurrences(int arr[], int n, int x); -> Option B

4. Quick Check:

   Correct function signature = int countOccurrences(int arr[], int n, int x); [OK]

Hint: Function returns count as int, array passed as int[] [OK]

Common Mistakes:

• Using void return type instead of int
• Passing array as int instead of int[]
• Missing array size parameter

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

int arr[] = {1, 2, 2, 2, 3, 4, 5};
int n = 7;
int x = 2;
int count = 0;
for (int i = 0; i < n; i++) {
    if (arr[i] == x) count++;
}
printf("%d", count);

medium

A. 1

B. 2

C. 4

D. 3

Solution

1. Step 1: Iterate through the array and count matches

   Elements equal to 2 are at indices 1, 2, and 3, so count increments 3 times.

2. Step 2: Print the count

   The final count is 3, so printf outputs 3.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Count of 2 in array = 3 [OK]

Hint: Count elements equal to x by scanning array once [OK]

Common Mistakes:

• Counting only first occurrence
• Off-by-one errors in loop
• Printing count before loop ends

4. Identify the error in the following C function intended to count occurrences of x in a sorted array using binary search:

int countOccurrences(int arr[], int n, int x) {
    int count = 0;
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == x) {
            count++;
            mid++;
        } else if (arr[mid] < x) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return count;
}

medium

A. Incrementing mid inside the loop does not change low or high

B. The loop condition should be low < high

C. count should be initialized to -1

D. The function should return void

Solution

1. Step 1: Analyze loop variables and updates

   Incrementing mid does not affect low or high, so loop may become infinite or incorrect.

2. Step 2: Understand binary search update rules

   To move search window, low or high must be updated, not mid.

3. Final Answer:

   Incrementing mid inside the loop does not change low or high -> Option A

4. Quick Check:

   mid++ does not move search window [OK]

Hint: Update low/high, not mid, to move binary search window [OK]

Common Mistakes:

• Changing mid instead of low/high
• Wrong loop condition causing infinite loop
• Incorrect return type

5. Given a sorted array arr = {1, 2, 2, 2, 3, 3, 4, 5, 5, 5, 5}, write a function that uses binary search to count occurrences of x = 5. What is the count returned?

hard

A. 4

B. 6

C. 5

D. 3

Solution

1. Step 1: Use binary search to find first occurrence of 5

   First 5 is at index 7.

2. Step 2: Use binary search to find last occurrence of 5

   Last 5 is at index 10.

3. Step 3: Calculate count as last - first + 1

   Count = 10 - 7 + 1 = 4.

4. Final Answer:

   4 -> Option A

5. Quick Check:

   Count of 5 in array = 4 [OK]

Hint: Count = last index - first index + 1 using binary search [OK]

Common Mistakes:

• Counting total elements instead of occurrences
• Off-by-one errors in count calculation
• Using linear search instead of binary search