[C++] Beats 100%, O(N^2) with Explanation
Idea :\nWe start a j loop between 1...n-1 to check all valid positions to fix j.\nAt every such position, we check how many elements towards the left are smalle
Idea :\nWe start a j loop between 1...n-1 to check all valid positions to fix j.\nAt every such position, we check how many elements towards the left are smaller than j and how many such elements are greater than j i.e count of i<j & count of i>j\nSimilarly, we check how many elements towards the right of j are greater than j (j<k) and how many such elements are smaller than j (k>j)\nAfter we get this count, the answer for that particular position of j will be :-\n(count of i<j * count of j<k) + (count of i>j * count of j>k)\nThus this comes down to :- answer += (i_smaller * k_larger + i_larger * k_smaller);\nAnd this brings the time complexity down from the brute force O(N^3) to O(N^2) i.e Quadratic runtime.\n\n```\nint numTeams(vector<int>& rating) { //O(N^2)\n        if(rating.empty()) return 0;\n        int ans = 0;\n        for(int j=1; j<rating.size()-1; j++) { //Fixing j\'s position\n            int i_smaller=0, i_larger=0, k_smaller=0, k_larger=0;\n            for(int i=0; i<j; i++) { //check towards j\'s left\n                if(rating[i] < rating[j]) i_smaller++;\n                else if(rating[i] > rating[j]) i_larger++;\n            }\n            for(int k=j+1; k<rating.size(); k++) { //check towards j\'s right\n                if(rating[j] < rating[k]) k_larger++;\n                else if(rating[j] > rating[k]) k_smaller++;\n            }\n            ans += i_smaller * k_larger + i_larger * k_smaller;\n        }\n        return ans;\n    }\n```\nTime Complexity : O(N^2)\nSpace Complexity : O(1)
['C', 'C++']