Marathon Timing Review Order
Indices of a sorted array ordered by absolute value, then index
A marathon organizer records how many seconds each runner crossed a checkpoint before or after their scheduled time. A negative offset means early, a positive offset means late, and zero means exactly on time.
You are given an integer array offsets, already sorted in nondecreasing order. Each entry's index identifies its record.
Return all record indices ordered from smallest to largest absolute offset. When two records have the same absolute offset, put the smaller original index first.
Return an empty list if there are no records.
Examples
Example 1
Input: offsets = [-4,-4,-1,1,4,4] Output: [2,3,0,1,4,5]
The records at indices 2 and 3 are each one second from their scheduled times, so they come first in index order. The remaining four records are each four seconds away and are also ordered by their original indices.
Example 2
Input: offsets = [-8,-7,-7,-2,0] Output: [4,3,1,2,0]
The exactly-on-time record comes first, followed by the record two seconds early. The two records seven seconds early retain their original index order, and the record eight seconds early comes last.
Example 3
Input: offsets = [-3,-3,3,3] Output: [0,1,2,3]
All records have the same absolute offset, even though some are early and some are late. Their original index order therefore determines the entire review order.
Constraints
- 0 <= offsets.length <= 6000
- -1000000 <= offsets[i] <= 1000000
- offsets is sorted in nondecreasing order.
Indices are zero-based. The required ordering is exactly the ordering by the pair (abs(offsets[i]), i). The intended solution uses O(n) time and O(n) space for the returned list.
Hints
Show hint 1Hint 1
Split the array into negative and nonnegative portions. Absolute offsets grow moving backward through the negative portion and forward through the nonnegative portion.
Show hint 2Hint 2
Equal negative offsets form a consecutive group. Emit that group's indices in increasing order, and process negative records before nonnegative records when their absolute offsets tie.
Follow-up questions
What an interviewer might ask once you have a working solution.
- Can you achieve O(n) time without sorting the record indices?
- If the offsets were not already sorted, how would you preserve the original-index tie rule?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem