Retrieving list of flight numbers from flight path

The below is \$O(n^3)\$. I'm sure there is a way to improve this..

//vector flight_path; given as parameter
//vector flight_number; need to fill
//vector flight_segments; known, contains segments (dep, arr, flightnum)

//Purpose of the function is to take in a flight_path and give back a list of
// flight numbers for each segment
//
// Input: New York, London, Kolkata
// Output: 101 201 301, 102 939

vector get_flight_numbers (vector flight_path) {

    vector flight_number;

    for (int i = 0; i < flight_path.size() - 1; i++) {

        string dep = flight_path.at(i);
        string arr = flight_path.at(i+1);

        for (int j = 0; j < flight_segments.size(); j ++) {
            if (flight_segments.at(j).departure == dep && flight_segments.at(j).arrival == arr) {
                for (int k = 0; k < flight_segments.at(j).segment_numbers.size(); k++) {
                    flight_numbers.push_back(atoi(flight_segments.at(j).segment_numbers.at(k).c_str()));
                }
            }
        }

    }
}

If I understand this, you have a directed graph that consists of a series of flight segments. You are given a series of flight segments, say, A -> B -> C, that makes up a flight path.

In addition, you have a group of flight numbers. The flight numbers correspond to paths. Flight number 1 will be tagged as [A,B,1], for example. Time is not an issue, all flights are assumed to be available at all times.

Can you, in less than \$O(n^3)\$ time, figure out what flight numbers can take you from one segment to the next?

Well, on approach might be to go through the array exactly once in order to separate out all the flights that depart from your first departure gate, your second departure gate, and so forth. That's order n.

Then go through each of those lists (once) and remove all the flights that don't have the right destination gate. That's order n again.

At that point, you're pretty much done.

So think your big mistake here is going through your big loop (the flights) INSIDE your little loop (your flight path). You'd be much better off going through the small loop inside the big loop and breaking if you find a match. This loop only nests once, also, instead of twice. If you really really wanted to, you could check each departure as you find it to see if it matches an arrival.

In psuedo-code:

for (i in each flight) do
    for (j in each pathpoint except the last one) do
        if flight[i][departure][i] == pathpoint[j] then
            if flight[j][arrival] == pathpoint[j+1]
                put flight in the good flights vector
            end if
        end if
    end for
end for

That's \$O(n*m)\$, where \$m\$ is the length of the path and n is the number of flights. This should be, in any reasonable world, \$O(n)\$.

StackExchange Code Review Q#808, answer score: 10