Choose the Cheapest Round Trip
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Choose the Cheapest Round Trip
You are given two arrays of equal length. `departure[i]` is the cost of departing on day `i`, and `return_cost[j]` is the cost of returning on day `j`. Choose indices `i` and `j` with `i < j` that minimize `departure[i] + return_cost[j]`.
Return `[i, j]`. If several pairs have the same minimum total cost, choose the pair with the earliest departure index. If there is still a tie for that departure, choose the latest return index.
### Function Signature
```python
def cheapest_round_trip(departure: list[int], return_cost: list[int]) -> list[int]:
```
### Example
```text
departure = [10, 7, 8, 3, 6]
return_cost = [5, 4, 10, 7, 5]
Output: [3, 4]
```
Departing on day 3 costs 3 and returning on day 4 costs 5, for a total of 8.
### Constraints
- `2 <= len(departure) == len(return_cost) <= 200_000`
- Every cost is a non-negative integer that fits in signed 64-bit arithmetic.
- At least one valid pair always exists because the length is at least two.
### Clarifications
- Indices, not costs, are returned.
- A departure and return on the same day is not valid.
### Hints
- First describe the direct quadratic solution and its tie-breaking behavior.
- For a linear solution, consider what information about earlier departure days is sufficient when examining a return day.
Quick Answer: Choose departure and return days that minimize a round-trip cost while requiring departure before return. Derive a linear scan that retains the best earlier departure and implements exact ties by earliest departure index and then latest return index.
Choose departure index i and later return index j minimizing their combined costs, breaking ties by earliest i then latest j.
Constraints
- Both arrays have equal length at least two
- Costs are nonnegative integers
- Departure must be strictly earlier than return
Examples
Input: {'departure': [10, 7, 8, 3, 6], 'return_cost': [5, 4, 10, 7, 5]}
Expected Output: [3, 4]
Explanation: The prompt example chooses cost three plus five.
Input: {'departure': [1, 2], 'return_cost': [9, 3]}
Expected Output: [0, 1]
Explanation: Two days provide exactly one pair.
Hints
- Maintain the cheapest eligible earlier departure while scanning return days.
- On equal departure costs, keep the earlier index.