Count the copies
Two searches find where a value's run starts and ends. About 9 minutes.
Copies sit together
In a sorted list, all copies of a value sit in one block, like every copy of the same book on a library shelf. So counting them is "where does the block end, minus where does it start".
You already have a search for the start: the first position holding a value at least x.
Search 1: the first value ≥ 5 is at position 1. The 5s start here.
The end is another start
Just past the last x is the first value bigger than x. For whole numbers, that is the first value at least x plus one. So run the same search again with x plus one.
Put the search in its own function and call it twice. The difference of the two answers is the count.
def first_at_least(x):
low, high = 0, len(nums)
while low < high:
mid = (low + high) // 2
if nums[mid] >= x:
high = mid
else:
low = mid + 1
return low
answers = []
for x in queries:
start = first_at_least(x)
end = first_at_least(x + 1)
answers.append(end - start)
return answersHow many 4s are in the list?
[2, 4, 4, 4, 4, 6] · first spot ≥ 4 is 1 · first spot ≥ 5 is 5
- A4
- B5
- C3
Show the answer
4. 5 − 1 = 4. Positions 1, 2, 3 and 4 hold the 4s.
Count each value
nums is sorted from smallest to largest and may have repeats. For each value in queries, return how many times it appears in nums.
nums = [1, 3, 3, 3, 6, 8, 8], queries = [3, 8, 5] → [3, 2, 0]
0 ≤ n ≤ 2,000,000 · sorted ascending · −1,000,000,000 ≤ every value ≤ 1,000,000,000 · up to 2,500 queries