Easy Approach
Intuition\n Describe your first thoughts on how to solve this problem. \nInstead of checking all possible triplets, which would be computationally expensive (O(
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nInstead of checking all possible triplets, which would be computationally expensive (O(n^3)), the code uses a more efficient approach by iterating over each possible middle element and counting potential valid configurations.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Iterate Over Each Element as Middle Element (rating[i]):\nFor each element in the list, treat it as the middle element of the triplet. The goal is to determine how many valid triplets can be formed with this element as the middle element.\n\n2. Count Elements Less Than and Greater Than the Middle Element:\nFor the current middle element rating[i]:\nCount left: Number of elements before i that are less than rating[i]. This counts how many smaller elements can be a part of an increasing sequence where rating[i] is the middle element.\nCount right: Number of elements after i that are greater than rating[i]. This counts how many larger elements can follow rating[i] to form a valid increasing sequence.\nMultiply these counts to get the number of valid increasing triplets with rating[i] as the middle element.\n\n3. Count Elements Greater Than and Less Than the Middle Element:\nSimilarly:\nCount left: Number of elements before i that are greater than rating[i]. This counts how many larger elements can be a part of a decreasing sequence where rating[i] is the middle element.\nCount right: Number of elements after i that are less than rating[i]. This counts how many smaller elements can follow rating[i] to form a valid decreasing sequence.\nMultiply these counts to get the number of valid decreasing triplets with rating[i] as the middle element.\n\n4. Update Total Count (ans):\nSum up the counts from both increasing and decreasing sequences for each element to get the total number of valid teams.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nThe time complexity of the given solution is \uD835\uDC42(\uD835\uDC5B^2). This is because for each element (total \uD835\uDC5B elements), we perform two passes to count elements before and after it. Each pass involves iterating through parts of the list, resulting in \uD835\uDC42(\uD835\uDC5B^2) operations in total.\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThe space complexity is \uD835\uDC42(1) because we use only a few extra variables (e.g., ans, left, right) regardless of the input size. No additional space is used that scales with input size.\n\n# Code\n```python []\nclass Solution:\n    def numTeams(self, rating: List[int]) -> int:\n        ans=0\n        n=len(rating)\n        for i in range(n):\n            left=sum(1 for j in range(i) if rating[i]<rating[j])\n            right=sum(1 for j in range(i+1,n) if rating[i]>rating[j])\n            ans+=left*right\n            left=sum(1 for j in range(i) if rating[i]>rating[j])\n            right=sum(1 for j in range(i+1,n) if rating[i]<rating[j])\n            ans+=left*right\n        return ans\n```\n```java []\nclass Solution {\n    public int numTeams(List<Integer> rating) {\n        int ans = 0;\n        int n = rating.size();\n        \n        for (int i = 0; i < n; i++) {\n            // Count how many elements to the left are smaller than rating[i]\n            int left = 0;\n            for (int j = 0; j < i; j++) {\n                if (rating.get(i) < rating.get(j)) {\n                    left++;\n                }\n            }\n            // Count how many elements to the right are larger than rating[i]\n            int right = 0;\n            for (int j = i + 1; j < n; j++) {\n                if (rating.get(i) > rating.get(j)) {\n                    right++;\n                }\n            }\n            ans += left * right;\n            \n            // Count how many elements to the left are larger than rating[i]\n            left = 0;\n            for (int j = 0; j < i; j++) {\n                if (rating.get(i) > rating.get(j)) {\n                    left++;\n                }\n            }\n            // Count how many elements to the right are smaller than rating[i]\n            right = 0;\n            for (int j = i + 1; j < n; j++) {\n                if (rating.get(i) < rating.get(j)) {\n                    right++;\n                }\n            }\n            ans += left * right;\n        }\n        \n        return ans;\n    }\n}\n\n```\n```cpp []\n#include <vector>\n\nclass Solution {\npublic:\n    int numTeams(std::vector<int>& rating) {\n        int ans = 0;\n        int n = rating.size();\n        \n        for (int i = 0; i < n; i++) {\n            int left = 0, right = 0;\n            \n            // Count how many elements to the left are smaller than rating[i]\n            for (int j = 0; j < i; j++) {\n                if (rating[i] < rating[j]) {\n                    left++;\n                }\n            }\n            // Count how many elements to the right are larger than rating[i]\n            for (int j = i + 1; j < n; j++) {\n                if (rating[i] > rating[j]) {\n                    right++;\n                }\n            }\n            ans += left * right;\n            \n            // Count how many elements to the left are larger than rating[i]\n            left = 0;\n            for (int j = 0; j < i; j++) {\n                if (rating[i] > rating[j]) {\n                    left++;\n                }\n            }\n            // Count how many elements to the right are smaller than rating[i]\n            right = 0;\n            for (int j = i + 1; j < n; j++) {\n                if (rating[i] < rating[j]) {\n                    right++;\n                }\n            }\n            ans += left * right;\n        }\n        \n        return ans;\n    }\n};\n\n```\n```c []\n#include <stdio.h>\n\nint numTeams(int* rating, int ratingSize) {\n    int ans = 0;\n    \n    for (int i = 0; i < ratingSize; i++) {\n        int left = 0, right = 0;\n        \n        // Count how many elements to the left are smaller than rating[i]\n        for (int j = 0; j < i; j++) {\n            if (rating[i] < rating[j]) {\n                left++;\n            }\n        }\n        // Count how many elements to the right are larger than rating[i]\n        for (int j = i + 1; j < ratingSize; j++) {\n            if (rating[i] > rating[j]) {\n                right++;\n            }\n        }\n        ans += left * right;\n        \n        // Count how many elements to the left are larger than rating[i]\n        left = 0;\n        for (int j = 0; j < i; j++) {\n            if (rating[i] > rating[j]) {\n                left++;\n            }\n        }\n        // Count how many elements to the right are smaller than rating[i]\n        right = 0;\n        for (int j = i + 1; j < ratingSize; j++) {\n            if (rating[i] < rating[j]) {\n                right++;\n            }\n        }\n        ans += left * right;\n    }\n    \n    return ans;\n}\n\n```
['Array', 'C', 'C++', 'Java', 'Python3']