Number of occurrence
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, Python, C++ and JavaScript, 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.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
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.
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 code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Linear count | O(n) | O(1) |
| Optimal (bisect_right - bisect_left) | O(log n) | O(1) |
1Linear count
O(n)O(1)Count matches in one pass.
- count++ for each element equal to target.
class Solution {
int countFreq(int[] arr, int target) {
int c = 0;
for (int x : arr) if (x == target) c++;
return c;
}
}class Solution:
def countFreq(self, arr: List[int], target: int) -> int:
c = 0
for x in arr:
if x == target:
c += 1
return cclass Solution {
public:
int countFreq(vector<int>& arr, int target) {
int c = 0;
for (int x : arr) if (x == target) c++;
return c;
}
};function countFreq(arr, target) {
let c = 0;
for (const x of arr) if (x === target) c++;
return c;
}2Optimal (bisect_right - bisect_left)
O(log n)O(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).
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;
}
}class Solution:
def countFreq(self, arr: List[int], target: int) -> int:
return self.bound(arr, target, True) - self.bound(arr, target, False)
def bound(self, a: List[int], x: int, strict: bool) -> int:
lo, hi = 0, len(a)
while lo < hi:
mid = (lo + hi) // 2
if (a[mid] > x) if strict else (a[mid] >= x):
hi = mid
else:
lo = mid + 1
return loclass Solution {
public:
int countFreq(vector<int>& arr, int target) {
return bound(arr, target, true) - bound(arr, target, false);
}
private:
int bound(vector<int>& a, int x, bool strict) {
int lo = 0, hi = a.size();
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (strict ? a[mid] > x : a[mid] >= x) hi = mid; else lo = mid + 1;
}
return lo;
}
};function countFreq(arr, target) {
return bound(arr, target, true) - bound(arr, target, false);
}
function bound(a, x, strict) {
let lo = 0, hi = a.length;
while (lo < hi) {
const 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.