Binary Search O(nlogn) Approach (Without DP/ Tree) 🔥
Intuition\nThe solution can be found by calculating the number of previous and next smaller and greater elements. \nBinary Search can give place of element in a
# Intuition\nThe solution can be found by calculating the number of previous and next smaller and greater elements. \nBinary Search can give place of element in a sorted array which is basically number of previous smaller elements.\nManipulating it we can find rest three also.\n\n# Approach\nThe helper function will use lower bound implementation of inbuilt C++ stlto calculate desired vector which stores number of previous smaller elements and further 3 similar implementations.\n\n# Complexity\n- Time complexity: O(nlogn)\n\n- Space complexity: O(n)\n\n# Code\n```\nclass Solution {\npublic:\n    vector<int> prevSmaller(vector<int>& nums) {\n        int n = nums.size();\n        vector<int> temp;\n        vector<int> ans(n);\n\n        for (int i = 0; i < n; i++) {\n            int lb =\n                lower_bound(temp.begin(), temp.end(), nums[i]) - temp.begin();\n            temp.insert(temp.begin() + lb, nums[i]);\n            ans[i] = lb;\n        }\n\n        return ans;\n    }\n\n    vector<int> prevGreater(vector<int>& nums) {\n        int n = nums.size();\n        vector<int> temp;\n        vector<int> ans(n);\n\n        for (int i = 0; i < n; i++) {\n            int lb =\n                lower_bound(temp.begin(), temp.end(), nums[i]) - temp.begin();\n            temp.insert(temp.begin() + lb, nums[i]);\n            ans[i] = i - lb;\n        }\n\n        return ans;\n    }\n\n    vector<int> nextGreater(vector<int>& nums) {\n        int n = nums.size();\n        vector<int> temp;\n        vector<int> ans(n);\n\n        for (int i = n - 1; i >= 0; i--) {\n            int lb =\n                lower_bound(temp.begin(), temp.end(), nums[i]) - temp.begin();\n            temp.insert(temp.begin() + lb, nums[i]);\n            ans[i] = n - 1 - i - lb;\n        }\n\n        return ans;\n    }\n\n    vector<int> nextSmaller(vector<int>& nums) {\n        int n = nums.size();\n        vector<int> temp;\n        vector<int> ans(n);\n\n        for (int i = n - 1; i >= 0; i--) {\n            int lb =\n                lower_bound(temp.begin(), temp.end(), nums[i]) - temp.begin();\n            temp.insert(temp.begin() + lb, nums[i]);\n            ans[i] = lb;\n        }\n\n        return ans;\n    }\n\n    int numTeams(vector<int>& rating) {\n        vector<int> prevSmall = prevSmaller(rating);\n        vector<int> prevGreat = prevGreater(rating);\n        vector<int> nextSmall = nextSmaller(rating);\n        vector<int> nextGreat = nextGreater(rating);\n\n        int count = 0;\n        for (int i = 1; i < rating.size() - 1; i++) {\n            count +=\n                (prevSmall[i] * nextGreat[i]) + (prevGreat[i] * nextSmall[i]);\n        }\n        return count;\n    }\n};\n```
['Array', 'Binary Search', 'C++']