Minimum Round-Trip Flight Cost
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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.
Quick Answer: 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`, 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.
Constraints
- 1 <= n <= 100000
- departure.length == arrival.length == n
- 0 <= departure[i], arrival[j] <= 1000000000
- Return -1 when n < 2 (no pair with j > i exists)
Examples
Input: ([4, 2, 5, 1], [6, 3, 2, 7])
Expected Output: 4
Explanation: Depart day 1 (price 2), return day 2 (price 2): 2 + 2 = 4 is the cheapest pair with j > i.
Input: ([5], [5])
Expected Output: -1
Explanation: n = 1, so there is no return day strictly after the departure day.
Input: ([3, 10], [10, 1])
Expected Output: 4
Explanation: Only valid pair is i=0, j=1: 3 + 1 = 4.
Input: ([5, 4, 3, 2, 1], [1, 1, 1, 1, 1])
Expected Output: 3
Explanation: Departures fall over time, but j must be > i. Best is depart day 3 (price 2), return day 4 (price 1): 2 + 1 = 3.
Input: ([0, 0], [0, 0])
Expected Output: 0
Explanation: Zero prices are allowed; the only pair costs 0 + 0 = 0.
Input: ([1000000000, 1], [1, 1000000000])
Expected Output: 2000000000
Explanation: Only pair is i=0, j=1: 1000000000 + 1000000000 = 2000000000; verifies 64-bit accumulation.
Input: ([], [])
Expected Output: -1
Explanation: Empty arrays (n = 0): no valid round trip exists.
Input: ([7, 2, 8, 3, 6], [5, 9, 4, 1, 2])
Expected Output: 3
Explanation: Cheapest departure before day 3 is 2 (day 1); pairing with arrival day 3 (price 1) gives 2 + 1 = 3.
Hints
- You need a pair of indices i < j minimizing departure[i] + arrival[j]. Fixing the return day j, the best you can do is pair it with the cheapest departure available strictly before j.
- Sweep j from left to right while maintaining the minimum of departure[0..j-1]. For each j >= 1, candidate cost = (min departure so far) + arrival[j]; keep the smallest candidate.
- This runs in O(n) time and O(1) extra space. Watch for overflow in fixed-width languages: two prices up to 1e9 sum to 2e9, which exceeds 32-bit int, so accumulate in a 64-bit type.