C++ | Count Number of Teams with O(n²) Complexity | Efficient 23ms Solution
Intuition\nTo solve the problem of counting valid teams of 3 soldiers, we iterate over each soldier as the middle one, then count how many soldiers before it ar
# Intuition\nTo solve the problem of counting valid teams of 3 soldiers, we iterate over each soldier as the middle one, then count how many soldiers before it are smaller or larger and how many soldiers after it are smaller or larger. Using these counts, we calculate the number of valid triplets (i, j, k) that satisfy either **rating[i] < rating[j] < rating[k]** or **rating[i] > rating[j] > rating[k]**, ensuring **0 <= i < j < k < n**. This approach efficiently counts the valid teams by leveraging nested loops to fix the middle soldier and count possible preceding and succeeding soldiers.\n\n# Approach\nFor each soldier **j**, count the number of soldiers **i** before **j** that are either smaller or larger than **rating[j]**, and count the number of soldiers **k** after **j** that are either smaller or larger than **rating[j]**. Combine these counts to calculate the total number of valid teams where **(rating[i] < rating[j] < rating[k])** or **(rating[i] > rating[j] > rating[k])**.\n\n# Complexity\n- Time complexity $$O(n^2)$$ due to the nested loops iterating through the soldiers.\n- Space complexity $$O(1)$$ as we are using a constant amount of extra space.\n\n# Code\n```\nclass Solution {\npublic:\n    int numTeams(vector<int>& rating) {\n        int n = rating.size(),totalTeams{0};\n        for (int j{0}; j < n; ++j) {\n            int leftSmaller{0}, leftLarger{0}, rightSmaller{0}, rightLarger{0};\n            for (int i{0}; i < j; ++i) {\n                if (rating[i] < rating[j]) ++leftSmaller;\n                else if (rating[i] > rating[j]) ++leftLarger;\n            }\n            for (int k = j + 1; k < n; ++k) {\n                if (rating[k] < rating[j]) ++rightSmaller;\n                else if (rating[k] > rating[j]) ++rightLarger;\n            }\n            totalTeams += leftSmaller * rightLarger + leftLarger * rightSmaller;\n        }\n        return totalTeams;\n    }\n};\n\n```\n**Example 1:** **rating = [2,5,3,4,1]** outputs **3** with valid teams (2, 3, 4), (5, 4, 1), and (5, 3, 1) for increasing or decreasing sequences; **Example 2:** **rating = [2,1,3]** outputs **0** as no valid teams exist; **Example 3:** **rating = [1,2,3,4]** outputs **4** with valid teams (1, 2, 3), (1, 2, 4), (1, 3, 4), and (2, 3, 4) for increasing sequences.\n\n## **If you found this solution helpful, please upvote! \uD83D\uDE0A**
['C++']