Katkat
Back

Find the Cheapest Valid Round Trip

UberSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

Find the cheapest round-trip flight pair satisfying a minimum stay duration constraint in linear time with deterministic tie-breaking.

Problem Statement

You are building a travel search feature for a ride and flight booking service. You are given two integer arrays of equal length n, outbound and return_flights, representing daily flight prices over an n-day calendar window (indexed from 0 to n - 1). You are also given an integer min_stay representing the minimum number of days a traveler must spend between departure and return.

A round trip is defined by a departure day i and a return day j such that:

  • 0 = i + min_stay

The total cost of the trip is outbound[i] + return_flights[j].

Find the valid round trip with the minimum total cost. If there are multiple pairs (i, j) that achieve the minimum cost, choose the one with the smallest i. If there is still a tie, choose the one with the smallest j.

If no valid round trip exists, return (-1, -1, -1).

Function Signature

def find_cheapest_round_trip(outbound: list[int], return_flights: list[int], min_stay: int) -> tuple[int, int, int]:
    """
    Returns (min_total_cost, depart_day, return_day).
    """
    pass

Input & Output Format

  • Input:
    • outbound: List of positive integers of length n.
    • return_flights: List of positive integers of length n.
    • min_stay: An integer representing the minimum stay duration.
  • Output: A tuple (min_cost, depart_day, return_day).

Constraints

  • 1 <= n <= 2 * 10^5
  • 1 <= outbound[i], return_flights[i] <= 10^9
  • 0 <= min_stay <= n

Examples

Example 1

Input: 
outbound = [120, 150, 90, 200]
return_flights = [100, 180, 110, 80]
min_stay = 2

Output: (200, 0, 3)
Explanation:
- Valid departure day 0: return days can be 2 (cost = 120 + 110 = 230) or 3 (cost = 120 + 80 = 200).
- Valid departure day 1: return day can only be 3 (cost = 150 + 80 = 230).
- Departure day 2 has no valid return day since 2 + 2 = 4 >= n.
The cheapest round trip costs 200 with depart_day = 0 and return_day = 3.

Example 2

Input: 
outbound = [100, 100]
return_flights = [100, 100]
min_stay = 3

Output: (-1, -1, -1)
Explanation: No departure day allows for a stay of at least 3 days within the 2-day window.

Hints

Hint 1

For any departure day i, the earliest valid return day is i + min_stay; you need the minimum return flight price on or after that day.

Hint 2

Precompute the minimum return flight price and its corresponding day index for each suffix of the return_flights array.

Hint 3

To handle ties deterministically, ensure that suffix minima break ties by preferring the earlier return day index.

Follow-up questions

  • How can you achieve O(1) auxiliary space by processing the days in reverse order instead of storing a full suffix array?
  • How would your approach change if a maximum stay constraint was also introduced (i.e., min_stay <= j - i <= max_stay)?
  • If flight prices update dynamically via a streaming API, what data structure would you use to maintain the optimal trip?