Number of occurrence

JavaView on GFG

Intuition

Count occurrences of a target in sorted array. Binary search for leftmost and rightmost positions.

Algorithm

1Find first occurrence (lower_bound). Find last occurrence (upper_bound - 1).
2Count = last - first + 1 if first <= last.

Common Pitfalls

•Two binary searches. Same as LC 34. Check if target exists before computing count.

Number of occurrence.java

Java

// Approach: Binary search for first and last occurrence of target. Count = last - first + 1.
// Time: O(log n) Space: O(1)
class Solution {
    int countFreq(int[] arr, int target) {
        int ans = 0;
        for (int num : arr) {
            if (num == target)
                ans++;
        }
        return ans;
    }
}

Was this solution helpful?