I recently took an interview at a company (starting with M and ending in A) which asked me this question. Still practicing my algorithms, so I was hoping someone could help me understand how to solve this problem, and these types of problems.
The problem:
You are given 2 arrays. For example:
D = [10,7,13,12,4]
R = [5,12,7,10,12]
D denotes the departure prices for flights from city A to city B. R denotes the return prices for flights from city B to city A. Find the minimum cost of a round trip flight between city A and city B. For example, the minimum in the example is D[1] + R[2].
(possible only to take the return flight on same or higher index from the departure flight)
The tricky part is that, obviously, you must depart before returning.
The naïve approach is just a double for loop combining all the possibilities. However, I know there is a better approach, but I can't wrap my head around it. I believe we want to create some sort of temporary array with the minimum so far or something like that...
Thanks for reading.
Create a mono queue/stack out of the return prices array R, then you can solve it in O(n) where n is the length of D.
R = [5, 12, 9, 10, 12] => [5, 9, 9, 10, 12]
As you can see at each step we have access to the cheapest return flight that is possible at index i and above.
Now, iterate over elements of D and look at that index in monoQ. Since that index at monoQ is the smallest possible in R for i and above, you now that you can't do better at that point.
In code:
D = [10,7,15,12,4]
R = [5,12,9,10,12]
monoQ = [0]*len(R)
monoQ[-1] = R[-1]
for i in range(len(R)-2, -1, -1):
monoQ[i] = min(monoQ[i+1], R[i])
best = R[0]+D[0]
for i, el in enumerate(D):
best = min(best, D[i]+monoQ[i])
print(best)