Katkat
Back

Minimum Round-Trip Flight Cost

MetaSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This question evaluates a candidate's ability to optimize over paired sequences using array traversal and running-minimum tracking, a core array-processing technique in coding interviews. It tests practical application of single-pass optimization under an ordering constraint rather than brute-force pairwise comparison, commonly used to assess algorithmic efficiency and edge-case handling.

You are planning a round trip and want to spend as little as possible on flights.

You are given two integer arrays of equal length n:

  • departure[i] — the price of a one-way outbound ticket that leaves on day i.
  • arrival[j] — the price of a one-way return ticket that arrives back on day j.

Days are indexed 0, 1, ..., n - 1 in chronological order. A valid round trip chooses an outbound day i and a return day j with j > i (you must return on a strictly later day than you depart). The cost of that round trip is departure[i] + arrival[j].

Return the minimum total cost over all valid round trips. If no valid round trip exists (that is, n < 2, so there is no pair with j > i), return -1.

Examples

Example 1

Input: departure = [4, 2, 5, 1], arrival = [6, 3, 2, 7]
Output: 4

Explanation: Departing on day 1 (price 2) and returning on day 2 (price 2) gives a total cost of 2 + 2 = 4, which is the cheapest valid pair with j > i.

Example 2

Input: departure = [5], arrival = [5]
Output: -1

Explanation: With only one day there is no return day strictly after the departure day, so no valid round trip exists.

Constraints

  • 1 <= n <= 100000
  • departure.length == arrival.length == n
  • 0 <= departure[i], arrival[j] <= 1000000000

Output

Return a single integer: the minimum cost departure[i] + arrival[j] over all pairs with j > i, or -1 if no such pair exists.