# Wondering if there is a lower O(n) I can go to..

Stupid question: The below is O(n^3). I'm sure there is a way to improve this, so any help is appreciated.

``````//vector<string> flight_path; given as parameter
//vector<int> flight_number; need to fill
//vector<segment> 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<string> get_flight_numbers (vector<string> flight_path) {

vector<int> 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()));
}
}
}

}
}
``````
-
Your inner loops don't seem to find segment chains correctly. The first `if()` tests if the flight covers the current path segment. –  David Harkness Feb 17 '11 at 3:20
If you use hash table instead of a vector of segments, you can make it much faster. –  Aryabhata Feb 17 '11 at 23:58

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 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).

-
I think you misunderstood the requirement. As I see it you need to find an ordered combination of segments for each neighboring pair of cities in the path. In the example, the first set of flights (101 201 301) takes you from New York to London, and the second set (102 939) takes you from London to Kolkata. If you will be checking multiple paths given the same segments you could preprocess the segments to build a directed graph. It would still be O(n^3), but one of those n's would be very small. –  David Harkness Feb 17 '11 at 3:19
If you use my method and create multiple arrays instead of a single array (one for each segment) than ANY selection of one choice from each array (or the point where all arrays are non-empty) solves the problem. This is still O(n*m) in the worst case. There is no need to go through the flights more than m times. –  philosodad Feb 18 '11 at 13:40
thanks! I'll see if i can adapt your method correctly. @david: actually the flight numbers need not be ordered. i should have chosen better numbers... –  Sagar Feb 18 '11 at 13:56

c++ solution: i wrote result in common list, but you can make vector < vector< string > >.

``````#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <iostream>

class Segment
{
public:
Segment(std::string const& departure, std::string const& arrival, int flighNum)
:m_departure(departure)
,m_arrival(arrival)
,m_flightNumber(flighNum)
{
}
std::string Departure() const { return m_departure; }
std::string Arrival() const { return m_arrival; }
int FlightNumber() const { return m_flightNumber; }
private:
std::string m_departure;
std::string m_arrival;
int         m_flightNumber;
};

class FillFlightNumbers
{
public:
FillFlightNumbers(std::vector<std::string> &flights, std::string const& departure, std::string const& arrival)
:m_flights(flights)
,m_departure(departure)
,m_arrival(arrival)
{
}
void operator()(Segment const& item) const
{
if (m_departure == item.Departure() && m_arrival == item.Arrival())
{
std::ostringstream oss;
oss << item.FlightNumber();
m_flights.push_back(oss.str());
}
}
private:
std::vector<std::string>    &m_flights;
std::string                 m_departure;
std::string                 m_arrival;
};

void GetFlightNumbers(std::vector<Segment> const& segmentList, std::vector<std::string> const& roadList, std::vector<std::string> &result)
{
for ( ; iteratorPath != endPath; ++iteratorPath)
{
std::vector<std::string>::const_iterator nextIt = iteratorPath + 1;
if (endPath == nextIt)
{
return;
}
std::for_each(segmentList.begin(), segmentList.end(), FillFlightNumbers(result, (*iteratorPath), (*nextIt)));
}
}

// test solution
void main()
{
std::vector<std::string> result;
std::vector<Segment> segmentList;
segmentList.push_back(Segment("New York", "London", 101));
segmentList.push_back(Segment("New York", "London", 202));
segmentList.push_back(Segment("New York", "London", 909));
segmentList.push_back(Segment("London", "Kolkata", 2222));
segmentList.push_back(Segment("London", "Kolkata", 3333));
segmentList.push_back(Segment("London", "Kolkata1", 3344));