Optimize Travel Costs and Generate Rotational Symmetric Numbers

Scenario

You are building a travel-search engine that must

1. show customers the cheapest round-trip they can book if departure and return prices vary by day, and
2. generate all k-digit numbers that still look the same after a 180° rotation for fraud-detection image checks.

Question

Given two arrays, dep[i] = outbound ticket price on day i and ret[j] = return ticket price on day j, design an algorithm that returns the minimum possible total cost for any valid round-trip (depart before return). Analyze time and space complexity and discuss possible optimizations or alternative solutions. Given an integer k, generate all k-digit numbers that remain identical when rotated 180°. Provide an algorithm, analyze its complexity, and explain how your code handles corner cases.

Hints

Cheapest flight: pre-compute suffix minima or use two-pointer scan. Strobogrammatic: recurse from outer to inner, pairing digits {0,0},{1,1},{6,9},{8,8},{9,6}.

Cheapest Round-Trip Booking

You are building a travel-search engine. You are given two integer arrays of the same conceptual timeline: dep, where dep[i] is the outbound (departure) ticket price on day i, and ret, where ret[j] is the return ticket price on day j.

A valid round-trip departs on some day i and returns on a strictly later day j (i < j). The total cost of that trip is dep[i] + ret[j].

Return the minimum possible total cost over all valid round-trips. If no valid round-trip exists (for example, when either array is empty or there is no day pair with i < j), return -1.

Example: dep = [10, 2, 8, 6], ret = [4, 9, 1, 7]. Departing on day 1 (price 2) and returning on day 2 (price 1) costs 3, which is the minimum, so the answer is 3.

Constraints

• 0 <= len(dep), len(ret)
• A valid trip requires a departure day i and return day j with i < j.
• Prices fit in a 32-bit signed integer; the sum of two prices fits in a 64-bit integer.
• Return -1 when no valid round-trip exists.

Hints

1. Fix the return day and ask: what is the cheapest departure available strictly before it? Or fix the departure day and ask for the cheapest return strictly after it.
2. Pre-compute a suffix-minimum array over ret so that for each departure day i you can look up the cheapest return on or after day i+1 in O(1).
3. Handle the infeasible cases up front: an empty array, or a timeline where every departure has no later return day, must yield -1.

Generate Strobogrammatic Numbers of Length k

A strobogrammatic number reads the same after a 180° rotation. Only certain digits map to valid digits under rotation: 0->0, 1->1, 8->8, 6->9, and 9->6. The pairs that may sit at mirrored positions are therefore {0,0}, {1,1}, {6,9}, {8,8}, {9,6}; the digit that may sit at the exact center (for odd lengths) is one of 0, 1, 8.

Given an integer k, return a list (sorted in ascending lexicographic order) of all k-digit strings that are strobogrammatic. A k-digit number may not have a leading zero, except in the single case k == 1, where "0" itself is a valid 1-digit strobogrammatic number.

If k <= 0, return an empty list.

Example: for k = 2 the answer is ["11", "69", "88", "96"] ("00" is excluded because of the leading zero).

Constraints

• k may be any integer; for k <= 0 return an empty list.
• Valid rotation digits: 0<->0, 1<->1, 8<->8, 6<->9, 9<->6.
• Leading zeros are not allowed for k > 1; for k == 1, "0" is included.
• Results are returned as strings in ascending lexicographic order.

Hints

1. Build the number from the outside in, choosing a mirrored pair (a, b) for the outermost positions and recursing on the inner length k-2.
2. The base cases are length 0 (one empty string) and length 1 (the self-rotating digits 0, 1, 8).
3. After generation, drop any string with a leading '0' unless k == 1, then sort the survivors.