The range of a value
Combine both searches into one answer, with one check for "not found." About 9 minutes.
Two searches, one answer
You already have both halves. One search finds where a value's block of copies starts, and the other finds where it ends. Call them back to back on the same x and you have the whole block: its range of positions.
It is like finding the first and last page of a chapter.
def find(x, go_left):
low, high, at = 0, len(nums) - 1, -1
while low <= high:
mid = (low + high) // 2
if nums[mid] == x:
at = mid
if go_left:
high = mid - 1
else:
low = mid + 1
elif nums[mid] < x:
low = mid + 1
else:
high = mid - 1
return at
answers = []
for x in queries:
first = find(x, True)
if first == -1:
answers.append([-1, -1])
else:
last = find(x, False)
answers.append([first, last])
return answersSearch 1 (first occurrence): halving lands on index 1, the first 3.
Don't run the second search for nothing
The two searches ask almost the same question, so if the first says x is missing, the second could only agree. Skipping it doesn't change the answer, it just saves the work.
In the code above, one helper leans left or right depending on a flag, so you don't write the loop twice.
nums = [5, 5, 5, 5, 9]. first_occurrence(5) is 0 and last_occurrence(5) is 3. What's the range for 5?
[5, 5, 5, 5, 9]
- A[0, 3]
- B[0, 4]
- C[-1, -1]
Show the answer
[0, 3]. That's exactly first_occurrence and last_occurrence, called and paired up — no extra work needed.
The first and last position of a value
nums is sorted from smallest to largest and may have repeats. For each value in queries, return [first, last]: the first and last index where it appears in nums. If it never appears, return [-1, -1].
nums = [2, 4, 4, 4, 4, 7, 9], queries = [4, 7, 2] → [[1, 4], [5, 5], [0, 0]]
0 ≤ n ≤ 2,000,000 · sorted ascending, may repeat · −1,000,000,000 ≤ every value ≤ 1,000,000,000 · up to 2,500 queries