Count Occurrences of Element in Sorted Array in DSA Java - 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 - first + 1

↓

Return count

↓

End

The process finds the first and last positions of the target element using binary search, then calculates how many times it appears.

Execution Sample

DSA Java

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

This code counts how many times the target appears in the sorted array by finding first and last positions.

Execution Table

Step	Operation	Array State	Pointer Changes	Visual State
1	Start with array and target=2	[1,2,2,2,3,4,5]	first=-1, last=-1	Array unchanged
2	Find first occurrence of 2	Same	mid=3 (arr[3]=2), update high=2	Searching left half
3	Continue first occurrence search	Same	mid=1 (arr[1]=2), update high=0	Narrowing left
4	Continue first occurrence search	Same	mid=0 (arr[0]=1), update low=1	Narrowing right
5	First occurrence found at index 1	Same	first=1	First index located
6	Find last occurrence of 2	Same	mid=3 (arr[3]=2), update low=4	Searching right half
7	Continue last occurrence search	Same	mid=4 (arr[4]=3), update high=3	Narrowing left
8	Last occurrence found at index 3	Same	last=3	Last index located
9	Calculate count = last - first + 1	Same	count=3	Count calculated
10	Return count=3	Same	Return 3	Done
11	Exit	Same	-	Target count found

💡 Binary searches complete; count calculated as 3 because target 2 appears from index 1 to 3

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 6	After Step 8	Final
first	-1	-1	1	1	1	1
last	-1	-1	-1	4	3	3
low	0	0	1	4	4	4
high	6	2	0	6	3	3
mid	-	3	0	3	4	4
count	-	-	-	-	-	3

Key Moments - 3 Insights

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

Because one binary search finds only one occurrence (first or last). To count all, we must find both first and last indexes (see steps 2-5 and 6-8 in execution_table).

What if the target is not in the array?

The first occurrence search returns -1 (step 5). Then countOccurrences returns 0 immediately (step 10), stopping further search.

Why do we update 'high' or 'low' differently in first and last occurrence searches?

For first occurrence, we move 'high' left when mid matches target to find earliest index (steps 2-5). For last occurrence, we move 'low' right to find latest index (steps 6-8).

Visual Quiz - 3 Questions

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

A 3

B 1

C -1

D 0

💡 Hint

Check the 'Pointer Changes' column at step 5 in execution_table.

At which step does the algorithm find the last occurrence of the target?

A Step 8

B Step 5

C Step 3

D Step 10

💡 Hint

Look for 'Last index located' in the Visual State column.

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

A 1

B -1

C 0

D Array length

💡 Hint

Refer to step 10 where first == -1 causes immediate return of 0.

Concept Snapshot

Count Occurrences in Sorted Array:
- Use binary search twice: find first and last occurrence
- first occurrence: move high left when target found
- last occurrence: move low right when target found
- Count = last - first + 1
- If not found, count = 0

Full Transcript

To count how many times an element appears in a sorted array, we use two binary searches. First, we find the first position where the element appears by moving the search window left when we find the target. Then, we find the last position by moving right when we find the target. The count is the difference between last and first indexes plus one. If the element is not found, we return zero immediately. This method is efficient because it uses binary search, which runs in logarithmic time.

Practice

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

easy

A. It uses less memory than linear search

B. It reduces the search time to logarithmic complexity

C. It sorts the array automatically

D. It works only for unsorted arrays

Solution

1. Step 1: Understand binary search efficiency

   Binary search divides the search space in half each time, making it faster than checking every element.

2. Step 2: Compare with linear search

   Linear search checks each element one by one, which takes longer for large arrays.

3. Final Answer:

   It reduces the search time to logarithmic complexity -> Option B

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
• Confusing memory use with speed
• Assuming binary search works on unsorted arrays

2. Which Java method signature correctly represents a function to count occurrences of an integer target in a sorted array arr?

easy

A. public static int countOccurrences(int[] arr, int target)

B. public int countOccurrences(int target, int[] arr)

C. static void countOccurrences(int[] arr, int target)

D. int countOccurrences(int[] arr, int target)

Solution

1. Step 1: Check method return type and parameters

   The method should return an integer count and accept an integer array and target integer as parameters.

2. Step 2: Verify static and access modifiers

   Static is common for utility methods; public allows access. The order of parameters matters for clarity.

3. Final Answer:

   public static int countOccurrences(int[] arr, int target) -> Option A

4. Quick Check:

   Correct signature returns int and takes (int[], int) [OK]

Hint: Return count as int, parameters: array then target [OK]

Common Mistakes:

• Wrong parameter order
• Void return type instead of int
• Missing static keyword when needed

3. What is the output of the following Java code snippet?

int[] arr = {1, 2, 2, 2, 3, 4, 5};
int target = 2;
int count = countOccurrences(arr, target);
System.out.println(count);

public static int countOccurrences(int[] arr, int target) {
    int first = firstOccurrence(arr, target);
    if (first == -1) return 0;
    int last = lastOccurrence(arr, target);
    return last - first + 1;
}

public static int firstOccurrence(int[] arr, int target) {
    int low = 0, high = arr.length - 1, result = -1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            result = mid;
            high = mid - 1;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return result;
}

public static int lastOccurrence(int[] arr, int target) {
    int low = 0, high = arr.length - 1, result = -1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            result = mid;
            low = mid + 1;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return result;
}

medium

A. 2

B. 4

C. 3

D. 0

Solution

1. Step 1: Find first occurrence of 2 in array

   First occurrence is at index 1 (arr[1] = 2).

2. Step 2: Find last occurrence of 2 in array

   Last occurrence is at index 3 (arr[3] = 2).

3. Step 3: Calculate count

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

4. Final Answer:

   3 -> Option C

5. Quick Check:

   Occurrences of 2 = 3 [OK]

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

Common Mistakes:

• Confusing first and last indices
• Off-by-one errors in count calculation
• Returning 0 when element exists

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

public static int countOccurrences(int[] arr, int target) {
    int low = 0, high = arr.length - 1;
    int count = 0;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            count++;
            low = mid + 1;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return count;
}

medium

A. It counts only occurrences after the first found index

B. It counts only one occurrence instead of all

C. It counts duplicates multiple times incorrectly

D. It never terminates due to infinite loop

Solution

1. Step 1: Analyze counting logic in binary search

   The code increments count only when arr[mid] == target and moves low to mid + 1, skipping elements before mid.

2. Step 2: Understand missed occurrences

   This approach counts occurrences only from the first found index forward, missing any before mid.

3. Final Answer:

   It counts only occurrences after the first found index -> Option A

4. Quick Check:

   Counting misses earlier duplicates [OK]

Hint: Counting inside binary search loop misses earlier matches [OK]

Common Mistakes:

• Assuming count increments all occurrences
• Not updating low/high correctly
• Expecting binary search to count all duplicates directly

5. Given a sorted array arr that may contain multiple occurrences of target, how can you efficiently count the occurrences if the array is very large and you want to minimize the number of comparisons?

hard

A. Use a hash map to store counts of all elements

B. Use a linear scan from start to end counting matches

C. Sort the array first, then count occurrences

D. Use two binary searches to find first and last occurrence, then subtract indices

Solution

1. Step 1: Understand the problem constraints

   Array is sorted and large, so linear scan is costly and sorting again is unnecessary.

2. Step 2: Apply binary search twice

   Use binary search to find the first occurrence index and last occurrence index of target efficiently.

3. Step 3: Calculate count

   Count = last occurrence index - first occurrence index + 1, minimizing comparisons.

4. Final Answer:

   Use two binary searches to find first and last occurrence, then subtract indices -> Option D

5. Quick Check:

   Two binary searches = efficient counting [OK]

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

Common Mistakes:

• Using linear scan on large arrays
• Sorting already sorted array again
• Using extra memory unnecessarily