Number of occurrence

Easy Binary Search Bisect Original on GeeksforGeeks

Number of occurrence is a easy binary search problem solved with the bisect pattern. The best approach, optimal (bisect_right - bisect_left), runs in O(log n) time and O(1) space. Below are 2 approaches in Java, from linear count up.

Problem

Given a sorted array and a target, return how many times target occurs.

Examples

Example 1

Input: arr = [1, 1, 2, 2, 2, 2, 3], target = 2
Output: 4

Example 2

Input: arr = [1, 3, 5], target = 4
Output: 0

Constraints

1 <= arr.length <= 10^6, sorted non-decreasing.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Code

Code appears here once we start writing it.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

Approach	Time	Space
Linear count	`O(n)`	`O(1)`
Optimal (bisect_right - bisect_left)	`O(log n)`	`O(1)`

1Linear count

TimeO(n)

SpaceO(1)

Count matches in one pass.

count++ for each element equal to target.

Java

class Solution {
    int countFreq(int[] arr, int target) {
        int c = 0;
        for (int x : arr) if (x == target) c++;
        return c;
    }
}

2Optimal (bisect_right - bisect_left)

TimeO(log n)

SpaceO(1)

All copies of target sit between the first index >= target and the first index > target. Their difference is the count.

Return bound(target, strict) - bound(target, non-strict).

Java

class Solution {
    int countFreq(int[] arr, int target) {
        return bound(arr, target, true) - bound(arr, target, false);
    }

    private int bound(int[] a, int x, boolean strict) {
        int lo = 0, hi = a.length;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (strict ? a[mid] > x : a[mid] >= x) hi = mid; else lo = mid + 1;
        }
        return lo;
    }
}

Edge cases to test

Target missing (0)
Whole array is the target

Hints

Hint 1

count = bisect_right - bisect_left.

FAQ

What is the best time complexity for Number of occurrence?

Optimal (bisect_right - bisect_left) runs in O(log n) time and O(1) extra space.

Which pattern does Number of occurrence use?

It is a binary search problem that uses the bisect pattern. Other problems with the same pattern: bisect_left, bisect_right, Search Insert Position, Floor in a Sorted Array.

Is there a brute force solution for Number of occurrence?

Yes. Linear count takes O(n) time and O(1) space. Count matches in one pass.

Which edge cases should I test for Number of occurrence?

Target missing (0); Whole array is the target.