O(N3), O(N2) || All Solutions Explained⭐🏆
Counting Number of Valid Teams\n\n## Intuition\nThe problem is to count the number of valid teams of 3 soldiers based on their ratings. A team is valid if it is
# Counting Number of Valid Teams\n\n## Intuition\nThe problem is to count the number of valid teams of 3 soldiers based on their ratings. A team is valid if it is either strictly increasing or strictly decreasing in terms of ratings. \n\n### Approach 1: Triple Nested Loops\nThe most straightforward way is to use three nested loops to iterate through all possible triplets and check if they form a valid team.\n\n### Approach 2: Optimized Counting\nA more efficient way is to count for each soldier how many soldiers to the left are smaller/greater and how many soldiers to the right are smaller/greater. This allows us to calculate the number of valid teams in a single pass for each soldier.\n\n## Approach\n### Triple Nested Loops Approach\n1. Use three nested loops to iterate through all possible triplets `(i, j, k)` where `i < j < k`.\n2. For each triplet, check if it forms a strictly increasing or strictly decreasing sequence.\n3. Count the number of valid triplets.\n\n### Optimized Counting Approach\n1. For each soldier `i`, count how many soldiers to the left are smaller (`leftsmaller`) and greater (`leftgreater`) than `rating[i]`.\n2. Similarly, count how many soldiers to the right are smaller (`rightsmaller`) and greater (`rightgreater`) than `rating[i]`.\n3. For each `i`, the number of valid teams where `i` is the middle soldier is given by `leftsmaller * rightgreater + leftgreater * rightsmaller`.\n\n## Complexity\n### Triple Nested Loops Approach\n- **Time complexity**: \\(O(n^3)\\)\n- **Space complexity**: \\(O(1)\\), not counting the input size\n\n### Optimized Counting Approach\n- **Time complexity**: \\(O(n^2)\\)\n- **Space complexity**: \\(O(1)\\), not counting the input size\n\n## Code\n### Triple Nested Loops Approach\n```cpp\nclass Solution {\npublic:\n    int numTeams(vector<int>& rating) {\n        int n = rating.size();\n        int count = 0;\n\n        for (int i = 0; i < n; i++) {\n            for (int j = i + 1; j < n; j++) {\n                for (int k = j + 1; k < n; k++) {\n                    if ((rating[i] < rating[j] && rating[j] < rating[k]) || \n                        (rating[i] > rating[j] && rating[j] > rating[k])) {\n                        count++;\n                    }\n                }\n            }\n        }\n\n        return count;\n    }\n};\n\n```\n### Optimized Counting Approach\n```\nclass Solution {\npublic:\n    int numTeams(vector<int>& rating) {\n        \n        int n = rating.size();\n        int count = 0;\n\n        for(int i=0; i<n; i++){\n\n            int leftsmaller = 0, leftgreater = 0;\n            int rightsmaller = 0, rightgreater = 0;\n\n            for(int j=0; j<i ; j++){\n                if(rating[j] > rating[i]){\n                    leftgreater++;\n                }\n                if(rating[j] < rating[i]){\n                    leftsmaller++;\n                }\n            }\n\n            for(int j=i+1; j<n ; j++){\n                if(rating[j] > rating[i]){\n                    rightgreater++;\n                }\n                if(rating[j] < rating[i]){\n                    rightsmaller++;\n                }\n            }\n\n            count += leftsmaller*rightgreater + leftgreater*rightsmaller;\n        }\n\n        return count;\n    }\n};\n```
['Array', 'Dynamic Programming', 'Binary Indexed Tree', 'C++']