Multiple condition on a sort (c++)

Question

I'm trying to do this LeetCode problem using only the c++ sort function, but I can seem to find the correct way to sort elements depending on multiple condition.

The problem wants you to return the destination city which don't have any path outgoing to another city. In my sorting, I want this city to be the last element of my vector. Right now, this is the code that I have :

class Solution {
public:
    string destCity(vector<vector<string>>& paths) {
        sort(paths.begin(), paths.end(),[](vector<string> a, vector<string> b ){return (a[1] == b[0]);});
        return (paths[paths.size() -1][1]);   
    }
};`

The input is a vector of paths ([cityA -> cityB], [cityM -> city N] , ... ).

In the following picture, we can see the input, output, my stdout and the expected result of the function :

You can withness that my sort only insures that two paths will be consecutive if the outgoing city of a path equal to the ingoing city of another path [cityA-> cityB], [cityB -> cityC], ... . But my issue is that my sort doesn't treat the case of a city (aka the destination city) that don't have any path outgoing to another city. I would like to place it this particular city as the last element of my vector. Can I do this by adding some code (conditions) to my sort function ? If yes, how ?

Thank you.

The problem with those useless online competition sites, like that one, is that they don't actually help anyone learn C++. They don't explain, for example, that the comparator function must implement "strict weak ordering", and what it means. That explanation can only be found [in a good C++ textbook](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). P.S. They also don't explain how horribly inefficient is passing entire vectors, ***by value***, to the comparator function, and the better way to do it. Again, please see a good textbook for the explanation. — Sam Varshavchik, Jul 31 '20 at 02:58
@sam to be fair, the passing by value is OP's fault. They use pass by reference. But yeah, on vector of vectors and throwing newbies at algorithms without guidance, I'm with you. — Jeffrey, Jul 31 '20 at 03:05

score 3 · Answer 1 · answered Jul 31 '20 at 03:02

You cannot do it with the std::sort. The sort function requires a total order over the elements. You only have a partial one. Once you put all your pairs in, the sort might decide to compare two unrelated elements. It won't try to find a way to compare them in the "right" order.

You need to find a new algorithm. May I suggest:

std::map<string, string> destinations;

And simply following the destination until you get to the end?

score 0 · Answer 2 · answered Jul 31 '20 at 15:07

Sorting is O(N Log N), even though you might find ways to sort, we'd ideally want to avoid sorting here, and reduce the time complexity to O(N) for this problem.

This'll pass through:

#include <string>
#include <unordered_set>

struct Solution {
    static std::string destCity(
        const std::vector<std::vector<std::string>>& paths
    ) {
        std::unordered_set<std::string> starts_map;

        for (const auto& path : paths) {
            starts_map.insert(path[0]);
        }

        for (const auto& path : paths) {
            if (!starts_map.count(path[1])) {
                return path[1];
            }
        }

        return "";
    }
};

References

For additional details, you can see the Discussion Board. There are plenty of accepted solutions with a variety of languages and explanations, efficient algorithms, as well as asymptotic time/space complexity analysis^{1, 2} in there.

Multiple condition on a sort (c++)

2 Answers2

References