Count Occurrences of Element in Sorted Array in DSA Java

Mental Model

In a sorted list, all copies of the same number are next to each other. We find where the number starts and ends to count how many times it appears.

Analogy: Imagine a row of identical books on a shelf sorted by title. To count how many copies of one title there are, find the first copy and the last copy, then count all books between them.

Array: [1, 2, 2, 2, 3, 4, 5]
Find occurrences of 2:
Positions: 0  1  2  3  4  5  6
Values:   1 -> 2 -> 2 -> 2 -> 3 -> 4 -> 5
               ↑           ↑
          first occurrence last occurrence

Dry Run Walkthrough

Input: array: [1, 2, 2, 2, 3, 4, 5], element to count: 2

Goal: Find how many times 2 appears in the sorted array

Step 1: Find first occurrence of 2 using binary search

mid at index 3 (value 2), check left half to find earlier 2
Array: 1 -> 2 -> 2 -> [2] -> 3 -> 4 -> 5

Why: We want the earliest position where 2 appears

Step 2: Move left to index 1 (value 2), check if it's first occurrence

Array: 1 -> [2] -> 2 -> 2 -> 3 -> 4 -> 5

Why: Index 1 is 2 and index 0 is 1, so index 1 is first occurrence

Step 3: Find last occurrence of 2 using binary search

mid at index 2 (value 2), check right half to find later 2
Array: 1 -> 2 -> [2] -> 2 -> 3 -> 4 -> 5

Why: We want the last position where 2 appears

Step 4: Move right to index 3 (value 2), check if it's last occurrence

Array: 1 -> 2 -> 2 -> [2] -> 3 -> 4 -> 5

Why: Index 3 is 2 and index 4 is 3, so index 3 is last occurrence

Step 5: Calculate count as last occurrence index - first occurrence index + 1

Count = 3 - 1 + 1 = 3

Why: Number of times 2 appears is the range length

Result:

Array: 1 -> [2] -> 2 -> [2] -> 3 -> 4 -> 5
Count of 2 = 3

Annotated Code

DSA Java

public class CountOccurrences {

    // Find first occurrence of target in sorted array
    public static int firstOccurrence(int[] arr, int target) {
        int low = 0, high = arr.length - 1;
        int result = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] == target) {
                result = mid; // record current match
                high = mid - 1; // search left half for earlier occurrence
            } else if (arr[mid] < target) {
                low = mid + 1; // target is right
            } else {
                high = mid - 1; // target is left
            }
        }
        return result;
    }

    // Find last occurrence of target in sorted array
    public static int lastOccurrence(int[] arr, int target) {
        int low = 0, high = arr.length - 1;
        int result = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] == target) {
                result = mid; // record current match
                low = mid + 1; // search right half for later occurrence
            } else if (arr[mid] < target) {
                low = mid + 1; // target is right
            } else {
                high = mid - 1; // target is left
            }
        }
        return result;
    }

    // Count occurrences of target in sorted array
    public static int countOccurrences(int[] arr, int target) {
        int first = firstOccurrence(arr, target);
        if (first == -1) {
            return 0; // target not found
        }
        int last = lastOccurrence(arr, target);
        return last - first + 1;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 2, 2, 3, 4, 5};
        int target = 2;
        int count = countOccurrences(arr, target);
        System.out.println("Count of " + target + " = " + count);
    }
}

result = mid; // record current match high = mid - 1; // search left half for earlier occurrence

record first occurrence and continue searching left to find earlier one

result = mid; // record current match low = mid + 1; // search right half for later occurrence

record last occurrence and continue searching right to find later one

if (first == -1) { return 0; }

handle case when target is not found

return last - first + 1;

calculate count as difference between last and first indices plus one

Output

Count of 2 = 3

Complexity Analysis

Time: O(log n) because binary search halves the search space each step

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Naive approach scans entire array O(n), this uses binary search O(log n) for faster counting

Edge Cases

target not in array

firstOccurrence returns -1, countOccurrences returns 0

DSA Java

if (first == -1) { return 0; }

array is empty

firstOccurrence returns -1 immediately, countOccurrences returns 0

DSA Java

while (low <= high) { ... } handles empty array by skipping loop

all elements are target

firstOccurrence returns 0, lastOccurrence returns last index, count is array length

DSA Java

return last - first + 1;

When to Use This Pattern

When you need to count how many times a number appears in a sorted list, use binary search to find first and last positions for efficient counting.

Common Mistakes

Mistake: Stopping binary search when first match is found instead of continuing to find first or last occurrence
Fix: Continue searching left (for first) or right (for last) after finding a match to find exact boundary

Mistake: Calculating count as last - first without adding 1
Fix: Add 1 to include both ends in the count

Summary

Counts how many times a target appears in a sorted array by finding first and last positions.

Use when you have a sorted array and want to count occurrences efficiently.

The key is to use binary search twice to find boundaries instead of scanning the whole array.

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