How does 'find()' work in a 'std::set<std::pair<int,int>>'?

Question

I'm solving the LeetCode problem 'Path Crossing', where I use a set<pair<int,int>>, trying to find whether the point x,y is already in the path or not. But I don't get the desired result.

bool isPathCrossing(string s) {
    set <pair <int, int>> st;
    int x = 0, y = 0;
    st.insert(make_pair(x,y));
    for(int i = 0; i < s.size(); i++) {
        if(s[i] == 'N') y++;
        else if(s[i] == 'W') x++;
        else if(s[i] == 'S') y--;
        else x--;
        pair <int, int> pr = make_pair(x, y);
        if(st.find(pr) != st.end()) return false;
        st.insert(pr);
    } 
    return true;
}

Does the find() method work only for the first element of the pair, or for both elements?

Answer 1

To answer your question, when find() is comparing 2 pair objects, both first and second values are looked at, not just the first value.

That said, the reason you are not getting the desired result is simply because you did not follow the instructions that LeetCode gave you:

• Your return values are backwards.

  You need to return true if your loop finds an existing point in the set, otherwise return false if the entire string is consumed without finding a match.

• Your movements of the x coordinate are backwards.

  West moves to the left, and East moves to the right, so you need to decrease x on 'W' and increase x on 'E'.

Here is the corrected code:

bool isPathCrossing(string s) {
    set <pair <int, int>> st;
    int x = 0, y = 0;
    st.insert(make_pair(x,y));
    for(int i = 0; i < s.size(); i++) {
        if(s[i] == 'N') y++;
        else if(s[i] == 'W') x--;
        else if(s[i] == 'S') y--;
        else x++;
        pair <int, int> pr = make_pair(x, y);
        if(st.find(pr) != st.end()) return true;
        st.insert(pr);
    } 
    return false;
}  

Online demo