Algorithm question: Finding the cheapest flight

Question

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.

Answer 1

I'm perfectly happy with @user1984's solution. But if you really want to impress them:

from itertools import accumulate

monoQ = list(accumulate(reversed(R), min))
monoQ.reverse()

best = min(d + r for d, r in zip(D, monoQ))

Most people are familiar with list(accumulate((1, 2, 3, 4 5), operator.add)) which returns (1, 3, 6, 10, 15), but using min makes the result be the smallest element seen so far. Since you want the smallest element from here to the end, you have to reverse the list, accumulate, and then reverse it again.

---

Since this came up in a discussion one of the other answers, this could be rewritten to be O(1) space.

best = min(d + r for d, r in zip(reversed(D), accumulate(reversed(R), min)))

This is a bit hacky, and I wouldn't recommend it unless you're specifically asked for an O(1) space solution.

Unfortunately you have to use reverse(D) and work from the end of the list rather than reverse(accumulate(...)) because you can't apply reverse to an accumulation. zip, reversed, and accumulate all return iterators rather than lists or tuples.

Answer 2

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)