Katkat
Back

Choose the Cheapest Round Trip

MetaSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests the ability to optimize a two-step decision process by maintaining track of the best previous state, requiring a linear scan approach.

Problem Statement

You are given an array of integers prices, where prices[i] represents the price of a flight on day i. You need to book a round-trip consisting of a departure day i and a return day j such that i < j. The cost of the round-trip is defined as prices[i] + prices[j].

Your goal is to find the pair (i, j) that minimizes the total cost. If there are multiple pairs with the same minimum cost, follow these tie-breaking rules:

  1. Choose the pair with the smallest i (earliest departure day).
  2. If there is still a tie, choose the pair with the largest j (latest return day).

Function Signature

def find_cheapest_round_trip(prices: List[int]) -> List[int]:

Constraints

  • 2 <= len(prices) <= 10^5
  • 1 <= prices[i] <= 10^6

Examples

Example 1: Input: prices = [5, 2, 8, 3, 4] Output: [1, 3] Explanation: Possible pairs (i, j) with i < j: (0, 1) cost 7; (0, 2) cost 13; (1, 3) cost 5; (1, 4) cost 6. The minimum cost is 5, achieved at index [1, 3].

Example 2: Input: prices = [3, 1, 4, 1, 5] Output: [0, 1] Explanation: Pairs with minimum cost 4 are (0, 1), (0, 3), and (1, 3). Following tie-breakers (smallest i=0, then largest j), (0, 3) is chosen over (0, 1). Wait—re-evaluating: (0, 1) cost 4, (0, 3) cost 4, (1, 3) cost 2. The minimum is 2, pair [1, 3].

Edge Cases

  • Array length of 2.
  • Prices that are all identical.
  • Prices that are strictly increasing or strictly decreasing.

Hints

Hint 1

Instead of a nested loop, iterate through the array once while keeping track of the index of the minimum price seen so far.

Hint 2

For each day `j` (as the potential return day), consider `j` as the return and the `min_index` seen in the range `[0, j-1]` as the departure.

Hint 3

Update your global best pair only when you find a strictly lower cost, or an equal cost that satisfies the tie-breaking logic.

Follow-up questions

  • How would the solution change if we introduced a minimum gap constraint, such as requiring at least 3 days between departure and return?
  • What if we wanted to find the top K cheapest round trips instead of just the single cheapest?
  • How would you handle a scenario where prices are provided as a stream and you need to provide the best pair seen so far at any given moment?