[C++] O(n^2) count
Find all the triplets in an rating array that satisfiy i<j<k and rating[i]<rating[j]<rating[k] or i<j<k and rating[i]>rating[j]>rating[k].\n\n# Explanation\n\nB
Find all the triplets in an `rating` array that satisfiy `i<j<k` and `rating[i]<rating[j]<rating[k]` or `i<j<k` and `rating[i]>rating[j]>rating[k]`.\n\n# Explanation\n\nBecause `n` is small (only 200), an O(n^3) algorithm is ok. But it is easy to optimize the algorithm to O(n^2). For each `rating[j]`, the number of triplets satisfying `i<j<k` and `rating[i]<rating[j]<rating[k]` is `cnt(i<j, rating[i]<rating[j]) * cnt(j<k, rating[j]<rating[k])`, and the number of triplets satisfying `i<j<k` and `rating[i]>rating[j]>rating[k]` is `cnt(i<j, rating[i]>rating[j]) * cnt(j<k, rating[j]>rating[k])`.\n\n# C++ Solution\n\n```cpp\nclass Solution {\npublic:\n    int numTeams(vector<int>& rating) {\n        int n = rating.size();\n        int ans = 0;\n        for (int i = 0; i < n; i++) {\n            int leftLarger = 0, leftSmaller = 0, rightLarger = 0, rightSmaller = 0;\n            for (int j = 0; j < i; j++)\n                if (rating[j] < rating[i])\n                    leftSmaller++;\n                else if (rating[j] > rating[i])\n                    leftLarger++;\n            for (int j = i + 1; j < n; j++)\n                if (rating[j] < rating[i])\n                    rightSmaller++;\n                else if (rating[j] > rating[i])\n                    rightLarger++;\n            ans += leftSmaller * rightLarger + leftLarger * rightSmaller;\n        }\n        return ans;\n    }\n};\n```\n
[]