Tally of a Value in a Sorted Log
EasyBinary Search
Problem
A sensor log stores readings in non-decreasing order in the array readings. Return how many times the value target appears.
Aim for O(log n): the log can be very long and is queried often.
Example 1
- Input:
- readings = [1, 2, 2, 2, 5, 7], target = 2
- Output:
- 3
The 2s occupy indices 1 to 3.
Example 2
- Input:
- readings = [1, 3, 5], target = 4
- Output:
- 0
Example 3
- Input:
- readings = [4, 4, 4, 4], target = 4
- Output:
- 4
Constraints
- 0 ≤ readings.length ≤ 10^5
- -10^9 ≤ readings[i], target ≤ 10^9
- readings is sorted in non-decreasing order.
Hint
Show the first hint
All copies of target sit in one contiguous block. What two positions describe that block?
Walkthrough
How to approach it
01Clarify before coding
- Is the log sorted? Yes, non-decreasing, so equal readings are adjacent.
- What if target does not appear? Return 0.
- Are values integers? Yes, so 'first value > target' equals 'first value ≥ target + 1'.
02Brute force
Count matches with a linear scan, or binary search one copy and expand left and right.
Cost: O(n) time. The expand-from-a-hit version is also O(n) in the worst case: think of an array that is all 4s.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.