Latest Reading Not After a Time
EasyBinary Search
Problem
A weather station logs readings at the timestamps in times, sorted in strictly increasing order. To answer 'what was the reading at time t?', the dashboard uses the latest reading taken at or before t.
Return the index of the largest timestamp that is ≤ t, or -1 if every reading was taken after t.
Example 1
- Input:
- times = [2, 5, 9, 14], t = 10
- Output:
- 2
9 is the latest timestamp not after 10.
Example 2
- Input:
- times = [2, 5, 9, 14], t = 1
- Output:
- -1
The first reading happened at 2, after t.
Example 3
- Input:
- times = [2, 5, 9, 14], t = 14
- Output:
- 3
Constraints
- 0 ≤ times.length ≤ 10^5
- -10^9 ≤ times[i], t ≤ 10^9
- times is strictly increasing.
Hint
Show the first hint
Find the first timestamp that is strictly after t. Where is the answer relative to it?
Walkthrough
How to approach it
01Clarify before coding
- Does a reading exactly at t count? Yes, 'at or before'.
- What if every reading is after t? Return -1.
- Can the log be empty? Yes: -1.
02Brute force
Scan from the right and return the first index with times[i] ≤ t.
Cost: O(n) per query. A dashboard asks this for every point on a chart, so O(log n) matters.
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.