Count Occurrences of Element in Sorted Array in DSA Java - Deep Dive

Overview - Count Occurrences of Element in Sorted Array

What is it?

Counting occurrences of an element in a sorted array means finding how many times that element appears in the list. Since the array is sorted, all copies of the element are next to each other. This makes it easier and faster to count than in an unsorted array. We use special searching methods to find the first and last place the element appears, then calculate the count.

Why it matters

Without this method, counting occurrences would require checking every item, which is slow for large lists. Using the sorted property lets us find the count quickly, saving time and computing power. This is important in real-world tasks like searching databases, analyzing data, or processing logs where speed matters.

Where it fits

Before learning this, you should understand arrays and basic searching methods like linear and binary search. After this, you can learn more advanced searching and sorting algorithms, or how to handle similar problems in unsorted data or with different data structures.

Mental Model

Core Idea

In a sorted array, the count of an element equals the difference between the positions of its last and first occurrence plus one.

Think of it like...

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

Sorted Array: [1, 2, 2, 2, 3, 4, 5]
Element to count: 2
First occurrence index: 1
Last occurrence index: 3
Count = (3 - 1) + 1 = 3

Build-Up - 7 Steps

1

Foundation

Understanding Sorted Arrays

Concept: Learn what a sorted array is and why elements are grouped together.

A sorted array is a list where elements are arranged in order, like numbers from smallest to largest. Because of this order, if an element appears multiple times, all its copies are next to each other. For example, in [1, 2, 2, 3], the number 2 appears twice and both are side by side.

Result

You know that duplicates in a sorted array form a continuous block.

Understanding that duplicates are grouped lets us use efficient methods to find them quickly.

2

Foundation

Basic Linear Counting Method

Concept: Count occurrences by checking each element one by one.

To count how many times an element appears, start from the beginning and check each item. Increase a counter when you find the element. Stop when you reach the end or a different element if the array is sorted.

Result

For array [1, 2, 2, 2, 3], counting 2 gives 3.

This method works but can be slow for large arrays because it checks every element.

3

Intermediate

Binary Search for First Occurrence

🤔Before reading on: do you think binary search can find the first occurrence of an element directly or just any occurrence? Commit to your answer.

Concept: Use binary search to find the first place the element appears.

Binary search splits the array in half repeatedly to find an element quickly. To find the first occurrence, when you find the element, check if it's the first or if the same element appears before it. If yes, continue searching the left half; if no, this is the first occurrence.

Result

In [1, 2, 2, 2, 3], first occurrence of 2 is at index 1.

Knowing how to adjust binary search to find the first occurrence saves time compared to linear search.

4

Intermediate

Binary Search for Last Occurrence

🤔Before reading on: do you think finding the last occurrence is the same as the first but searching right side? Commit to your answer.

Concept: Use binary search to find the last place the element appears.

Similar to first occurrence, but when you find the element, check if it's the last or if the same element appears after it. If yes, continue searching the right half; if no, this is the last occurrence.

Result

In [1, 2, 2, 2, 3], last occurrence of 2 is at index 3.

Adjusting binary search to find the last occurrence completes the information needed to count duplicates efficiently.

5

Intermediate

Calculate Count from Indices

Concept: Use the first and last occurrence indices to find the total count.

Once you have the first and last positions of the element, subtract the first index from the last and add one. This gives the total number of times the element appears.

Result

Count = (3 - 1) + 1 = 3 for element 2 in [1, 2, 2, 2, 3].

This simple calculation leverages the sorted property to avoid checking every element.

6

Advanced

Complete Java Implementation

🤔Before reading on: do you think the code should handle cases where the element is not found? Commit to your answer.

Concept: Combine first and last occurrence binary searches into a full Java method to count occurrences.

public class CountOccurrences { public static int firstOccurrence(int[] arr, int x) { int low = 0, high = arr.length - 1, result = -1; while (low <= high) { int mid = low + (high - low) / 2; if (arr[mid] == x) { result = mid; high = mid - 1; // search left side } else if (arr[mid] < x) { low = mid + 1; } else { high = mid - 1; } } return result; } public static int lastOccurrence(int[] arr, int x) { int low = 0, high = arr.length - 1, result = -1; while (low <= high) { int mid = low + (high - low) / 2; if (arr[mid] == x) { result = mid; low = mid + 1; // search right side } else if (arr[mid] < x) { low = mid + 1; } else { high = mid - 1; } } return result; } public static int countOccurrences(int[] arr, int x) { int first = firstOccurrence(arr, x); if (first == -1) return 0; // element not found int last = lastOccurrence(arr, x); return last - first + 1; } public static void main(String[] args) { int[] arr = {1, 2, 2, 2, 3, 4, 5}; int x = 2; System.out.println("Count of " + x + " is: " + countOccurrences(arr, x)); } }

Result

Count of 2 is: 3

Writing the full code shows how the theory translates into practice and handles edge cases like missing elements.

7

Expert

Handling Edge Cases and Performance

🤔Before reading on: do you think this method works well for very large arrays or arrays with no duplicates? Commit to your answer.

Concept: Understand how the method behaves with empty arrays, missing elements, and very large data.

The binary search approach runs in O(log n) time, which is very fast even for large arrays. If the element is not present, the method returns zero quickly. For arrays with no duplicates, the first and last occurrence are the same, so count is one. This method is stable and efficient across all cases.

Result

Fast and correct counts for all input types, including empty or large arrays.

Knowing the method's robustness helps trust it in production and avoid bugs with unusual inputs.

Under the Hood

Binary search works by repeatedly dividing the search range in half. For first occurrence, when the element is found, the search continues to the left half to find if an earlier copy exists. For last occurrence, the search continues to the right half. This ensures the exact boundary positions are found. The count is then the difference plus one.

Why designed this way?

This approach was designed to leverage the sorted property of arrays to reduce search time from linear (checking every element) to logarithmic. Alternatives like linear search are simpler but slower. Using binary search for boundaries is a classic optimization in computer science.

Array indices: 0  1  2  3  4  5  6
Array values:  1  2  2  2  3  4  5

First Occurrence Search:
Start low=0, high=6
mid=3 (value=2) found, move high=2
mid=1 (value=2) found, move high=0
mid=0 (value=1) not found, move low=1
Result first=1

Last Occurrence Search:
Start low=0, high=6
mid=3 (value=2) found, move low=4
mid=5 (value=4) > 2, move high=4
mid=4 (value=3) > 2, move high=3
Result last=3

Myth Busters - 3 Common Misconceptions

Quick: Does binary search always find the first occurrence of an element? Commit to yes or no.

Common Belief: Binary search always returns the first occurrence of the element.

Reality: Standard binary search returns any occurrence, not necessarily the first. You must modify it to find the first occurrence.

Why it matters: Assuming binary search finds the first occurrence can cause wrong counts and bugs in programs.

Quick: If an element is not in the array, does the count method return -1? Commit to yes or no.

Common Belief: If the element is missing, the method returns -1 or an error.

Reality: The method returns 0 to indicate no occurrences, handling missing elements gracefully.

Why it matters: Misunderstanding this can cause crashes or incorrect error handling in applications.

Quick: Is linear search always slower than binary search for counting occurrences? Commit to yes or no.

Common Belief: Linear search is always slower than binary search for counting occurrences in sorted arrays.

Reality: Linear search can be faster for very small arrays or when the element is near the start, but binary search is better for large arrays.

Why it matters: Knowing when to use which method helps optimize performance in real systems.

Expert Zone

1

Binary search for boundaries must carefully handle mid calculation to avoid infinite loops or missing edge cases.

2

When the array contains many duplicates, binary search reduces time drastically compared to linear counting.

3

In some languages or environments, built-in functions exist for these searches, but understanding the algorithm helps debug and optimize.

When NOT to use

This method only works on sorted arrays. For unsorted arrays, use hash maps or linear counting. If the array is very small, linear search might be simpler and faster.

Production Patterns

Used in database indexing to quickly count records matching a key, in search engines to count keyword occurrences, and in analytics to process sorted logs or timestamps efficiently.

Connections

Binary Search

Builds-on

Understanding binary search is essential because counting occurrences in sorted arrays is a direct application of finding boundaries using binary search.

Hash Maps

Alternative approach

Hash maps count occurrences in unsorted data efficiently, showing different strategies depending on data order.

Database Indexing

Real-world application

Counting occurrences in sorted arrays is similar to how databases use indexes to quickly count rows matching a condition.

Common Pitfalls

#1 Assuming binary search returns the first occurrence without modification.

Wrong approach:

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

Correct approach:

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

Root cause:

Not realizing that standard binary search stops at any occurrence, not necessarily the first.

#2 Not handling the case when the element is missing, causing wrong count or errors.

Wrong approach:

int countOccurrences(int[] arr, int x) {
int first = firstOccurrence(arr, x);
int last = lastOccurrence(arr, x);
return last - first + 1;
}

Correct approach:

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

Root cause:

Forgetting to check if the element exists before calculating count.

#3 Using linear search for large sorted arrays, causing slow performance.

Wrong approach:

int countOccurrencesLinear(int[] arr, int x) {
int count = 0;
for (int num : arr) {
if (num == x) count++;
}
return count;
}

Correct approach:

Use binary search based methods for first and last occurrence to achieve O(log n) time.

Root cause:

Not leveraging the sorted property to optimize search.

Key Takeaways

Counting occurrences in a sorted array is efficient because duplicates are grouped together.

Binary search can be adapted to find the first and last positions of an element, enabling fast counting.

Always handle the case where the element is not found to avoid errors.

This method runs in logarithmic time, making it suitable for large datasets.

Understanding these techniques is essential for optimizing search and count operations in real-world applications.

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