N^2 explained (with pictures) ^^
Time O(N^2), space O(N)\n\n\nint numTeams(vector<int>& r) \n{\n\tmap<int, int> m;\n\tfor(auto i{0}; i<size(r); ++i) \n\t{\n\t\tm[r[i]] = i;\n\t\tr[i] = distance
**Time `O(N^2)`, space `O(N)`**\n\n```\nint numTeams(vector<int>& r) \n{\n\tmap<int, int> m;\n\tfor(auto i{0}; i<size(r); ++i) \n\t{\n\t\tm[r[i]] = i;\n\t\tr[i] = distance(begin(m), m.find(r[i]));\n\t}\n\n    int out{0};\n\tfor(auto i{begin(m)}; i!=end(m); ++i)\n\t{\n\t\tauto L = r[i->second];\n\t\tauto R = distance(begin(m), i) - L;            \n\t\tout += L*(size(r)-i->second-1-R) + R*(i->second-L);\n\t}\n\n\treturn out;            \n}\n```\n\n**Brief explanation**\n\nThe main idea is to consider every element in a vector as a potential middle element in a tripple and to count the raitings that are less/greater and are to the left/right:\n\n![image](https://assets.leetcode.com/users/images/88624a32-ea51-4965-bf29-be3808b4d7a4_1606151754.1310136.png)\n\n\n\n<br>\n\n\nI use ordered `map m` to store pairs `{rating, index}` and alter the input vector `r` on the fly, as I tranfer data from it to the `map`.\nI reuse `r[i]` to store the number of `ratings` with indices **less** than `i` that are **less** than the `rating` previously store at `r[i]`.\nIn other words in `r[i]` I store the number of `ratings` that were less than `r[i]` and were to the **left** of it (left green bars). With it I can calculate the number of `ratings` that were greater than `r[i]` and were to the **left** of it (left red bars).\nTo find out number of `ratings` that were less/greater than `r[i]` and were to the **right** of it I need a fully constructed map.\n\nIn the second loop \n* I use `r` to find out the number of `ratings` `L` **less** than the current one with the indices **less** than the index of the current `rating`.\n* I use the `map` to find out the number of `ratings` `R` **less** than the current one with the indices **greater** than the index of the current `rating`.\n\nI use `L` and `R` and the index of the current `rating` to cook up the number of triples which have current `rating` as a middle element.\n\n**P.S.** Map construction that takes `O(Nlog(N))` but `std::distance` is `O(N)`.
['C', 'C++']