Skip to content
AlgoVisual

Race Overtaking

01 · Question

You are given two arrays of positive integers, p1 and p2, representing players in a racing game. The two arrays are sorted, non-empty, and have the same length, n. The i-th element of each array corresponds to where that player was on the track at the i-th second of the race. We know that:

  1. player 1 started ahead (p1[0] > p2[0]),
  2. player 2 overtook player 1 once, and
  3. player 2 remained ahead until the end (p1[n - 1] < p2[n - 1]).

Assume the arrays have no duplicates, and that p1[i] != p2[i] for any index.

Return the index at which player 2 overtook player 1.

Example:

  • Input: p1 = [2, 4, 6, 8, 10], p2 = [1, 3, 5, 9, 11]
  • Output: 3

02 · Solution

Reference solution

1def raceOvertaking(p1: List[int], p2: List[int]) -> int:
2    l, r = 0, len(p1) - 1
3    # We want the first index i where p2[i] > p1[i]
4    # Invariant: p1[l] > p2[l] (p1 ahead), p1[r] < p2[r] (p2 ahead)
5    
6    while l + 1 < r:
7        mid = (l + r) // 2
8        if p1[mid] > p2[mid]:
9            # p1 still ahead, so mid is in "before"
10            l = mid
11        else:
12            # p2 ahead, mid is in "after"
13            r = mid
14            
15    return r
Previous
Target Count Divisible By K
Next
Search in Sorted Grid