Counting All The Valid Teams with Simple Brute Force, Easy to Understand Solution!
Intuition\nSince the Constraints are in such a way that we can take our chances with a Brute Force Approach, We will go down that route, For any index i if we k
# Intuition\nSince the Constraints are in such a way that we can take our chances with a Brute Force Approach, We will go down that route, For any index *i* if we know exactly what sort of numbers are ahead of it and what sort of numbers are behind it we can easily tell how many teams can be formed.\n\n# Approach\nIn this problem We can see that the rating of the teammates should be either striclty increasing or decreasing.\nNow for a team with increasing rating values, for any index $$i$$, The Greater elements that are ahead of the current index and the Smaller elements that are behind the current index will end up making a valid team, so for this type of team we can easily find the elements that are ahead and greater and behind and smaller and simply multiply them to find the number of valid team that follow the given conditions\nSimilarily for the team that is valid with decreasing rating value, for every index $$i$$, We will find the number of greater elements that are behing it and the number the smaller elements that are ahead of it, we can multiply those numbers to find out the valid teams that we can make with that soldier at index $$i$$\nSeperately find the number of valid increasing and decreasing rating teams and return the sum of those team to get the total valid teams.\n\n# Complexity\n- Time complexity:\n$$O(n^2)$$ We have to traverse pretty much the whole array for every index\n\n- Space complexity:\n$$O(n)$$  We have to store the elements in a linear data structure, I have used a vector\n\n# Code\n```\n#include <bits/stdc++.h>\nusing namespace std;\n#define nline \'\\n\'\n#define sp \' \'\n#define all(x) x.begin(), x.end()\n#define rall(x) x.rbegin(), x.rend()\nstatic int fastIO = []\n{\n    ios_base::sync_with_stdio(false);\n    cin.tie(0);\n    cout.tie(0);\n    return 0;\n}();\n// Paste the Class here-\nclass Solution\n{\nprivate:\n    int increasingsubs(vector<int> &rating, int n)\n    {\n        vector<int> greaterahead(n);\n        vector<int> smallerbehind(n);\n        for (int i = 0; i < n; i++)\n        {\n            int count = 0;\n            for (int j = i + 1; j < n; j++)\n            {\n                if (rating[j] > rating[i])\n                    count++;\n            }\n            greaterahead[i] = count;\n        }\n        for (int i = 0; i < n; i++)\n        {\n            int count = 0;\n            for (int j = i - 1; j >= 0; j--)\n            {\n                if (rating[j] < rating[i])\n                    count++;\n            }\n            smallerbehind[i] = count;\n        }\n        int increasing = 0;\n        for (int i = 0; i < n; i++)\n        {\n            increasing += greaterahead[i] * smallerbehind[i];\n        }\n\n        return increasing;\n    }\n\n    int decreasingsubs(vector<int> &rating, int n)\n    {\n        vector<int> greaterbehind(n);\n        vector<int> smallerahead(n);\n        for (int i = 0; i < n; i++)\n        {\n            int count = 0;\n            for (int j = i + 1; j < n; j++)\n            {\n                if (rating[j] < rating[i])\n                    count++;\n            }\n            smallerahead[i] = count;\n        }\n        for (int i = 0; i < n; i++)\n        {\n            int count = 0;\n            for (int j = i - 1; j >= 0; j--)\n            {\n                if (rating[j] > rating[i])\n                    count++;\n            }\n            greaterbehind[i] = count;\n        }\n        int decreasing = 0;\n        for (int i = 0; i < n; i++)\n        {\n            decreasing += greaterbehind[i] * smallerahead[i];\n        }\n        return decreasing;\n    }\n\npublic:\n    int numTeams(vector<int> &rating)\n    {\n        int n = rating.size();\n        int increasing = increasingsubs(rating, n);\n        int decreasing = decreasingsubs(rating, n);\n        return increasing + decreasing;\n    }\n};\n```\n\n\n# Upvote\n![upvote meme.jpg](https://assets.leetcode.com/users/images/e12fc6b3-ab3f-4eae-8ee5-4db18d4266e2_1722245592.8670194.jpeg)\n
['C++']