C++ easy to understand solution
I tried the brute force solution first and as expected, it showed me an TLE (big discovery! as stupid me previously thought leetcode will give TLE above 10^9 an
I tried the brute force solution first and as expected, it showed me an TLE (big discovery! as stupid me previously thought leetcode will give TLE above 10^9 and not 10^9 itself).\nAnyways, here is the optimal solution that traverses the vector and first calculates the number of ratings that are both less and greater than the current rating on both left and right side. \nBasically the idea being, the current element is the middle element of the sequence rating[i]<rating[j]<rating[k] OR rating[i]>rating[j]>rating[k]. And hence, by calculating the count of these 4 values, we can find the number of teams that have ascending rating (leftless * rightgreater) and number of teams having descending rating (leftgreater * rightless). Again, remember,  current element is the middle element and hence we multiply and add the both ascending and descending teams. \nAtlast return the summation of total number of teams.\n```\nclass Solution {\npublic:\n    int numTeams(vector<int>& rating) {\n        int n = rating.size();\n        int teams = 0;\n        for(int i=1; i<n-1; i++)\n        {\n            int leftless = 0, rightgreater = 0, leftgreater = 0, rightless = 0;\n            for(int j=i-1; j>=0; j--)\n            {\n                if(rating[j]>rating[i])\n                    leftgreater++;\n                else\n                    leftless++;\n            }\n            for(int j = i+1; j<n; j++)\n            {\n                if(rating[j]>rating[i])\n                    rightgreater++;\n                else\n                    rightless++;\n            }\n            teams+=(leftless*rightgreater) + (leftgreater*rightless);\n        }\n        return teams;\n    }\n};\n```\nTime complexity: O(n^2)\nSpace complexity: O(1)
['C', 'C++']