Find the fastest duration for a certain distance in a walk

Question

I apologize in advance if the wording of my problem is inappropriate for this forum. Or if another platform i more suitable for it. I'm new here and typically do not have to solve complex algorithmic problems.

I'm looking for an algorithm that is able to find a answer to the following question:

If I ran 10 km this morning, how can I find out how fast my fastest kilometer was? (=searching for duration of fastest km)

My "run" datastructure consists of a list of data records, where each entry contains the following information:

• timestamp in milliseconds
• distance since start in meter

The data structure is arranged chronologically.

I already got a pretty straight forward solution to the problem, but I guess I would end up with a poor performance on this one:

1. start with the last entry of the list (i=size) and stop if available / remaining distance data[i] is smaller than 1km
2. search backwards in the list and calculate the distance delta for each entry until the delta for the distance is >= 1km OR (if we got a duration candidate from a previous iteration) the current calculated duration is already exceeding out current best.
3. if duration is too high start all over with i=i-1 until end condition is met
4. if a duration candidate is found remember this candidate decrease "i" and proceed with 1)

I really believe there must be an algorithm or better approach out there that can be applied to this question. Does anyone have an idea or can steer me in the right direction?

Answer 1

I suggest you use exactly your algorithm, except use binary search during your binary search. You will want to store the events in an array rather than a linked list, to allow efficient random access into it. The total running time will be $O(n \log n)$, where $n$ is the number of events in your data structure. That seems quite reasonable, and this should be quite efficient in practice.

Answer 2

I'm not certain I understand your algorithm, but the "start all over" part makes it sound like it will take $O(n^2)$ time for $n$ data points, which starts to take a while once you have more than 10000 or so. You can solve this problem in linear time by "walking two pointers forward" (or backward):

1. Set bestTime to a huge time.
2. Set s to 1. s will be the index of the start of our "current interval".
3. Set e to 1. e will be the index of the end of our "current interval".
4. While dist[e] - dist[s] < 1km:
   • Increment e.
5. At this point, we know that the index range s..e identifies a range of 1km. (Or possibly just over, but by the smallest possible amount -- we know that s..(e-1) is shorter than 1km.)
6. Is time[e] - time[s] < bestTime?
   • If yes: We have a new fastest 1km interval. Set bestTime to time[e] - time[s], and set bestStart to s.
7. Increment s.
8. Go to 4.

The key idea is that, after we have finished dealing with the 1km interval starting at some index s (that is, at time time[s]), to find the endpoint of 1km interval starting at index s+1, we don't need to "start from scratch": We know it must end at or after the end of the interval that began at position s. Although any particular starting point s might require many iterations of step 4 to find its corresponding endpoint e, this actually isn't a problem, since we never move e backwards: this means that across the entire algorithm's execution, e is only ever incremented in step 4 at most $n$ times.