🔥All Approaches you can tell in an Interview 🔥
Approaches\nAll of them are pretty self explanatory and easy to understand if you are familiar with all the ds and algo used\n\n# Memoization\n\nclass Solution 
# Approaches\nAll of them are pretty self explanatory and easy to understand if you are familiar with all the ds and algo used\n\n# Memoization\n```\nclass Solution {\nprivate:\n    int dpi[1000][3];\n    int fi(int idx, int cnt, vector<int> &rating) {\n        // base cases\n        if(cnt == 3) return 1;\n        if(dpi[idx][cnt] != -1) return dpi[idx][cnt];\n\n        int res = 0;\n        for(int i=idx+1; i<rating.size(); ++i) {\n            if(rating[i] <= rating[idx]) continue;\n            res += fi(i, cnt+1, rating);\n        }\n        return dpi[idx][cnt] = res;\n    }\n    int dpd[1000][3];\n    int fd(int idx, int cnt, vector<int> &rating) {\n        // base cases\n        if(cnt == 3) return 1;\n        if(dpd[idx][cnt] != -1) return dpd[idx][cnt];\n\n        int res = 0;\n        for(int i=idx+1; i<rating.size(); ++i) {\n            if(rating[i] >= rating[idx]) continue;\n            res += fd(i, cnt+1, rating);\n        }\n        return dpd[idx][cnt] = res;\n    }\npublic:\n    int numTeams(vector<int>& rating) {\n        int res = 0;\n        memset(dpi, -1, sizeof(dpi));\n        memset(dpd, -1, sizeof(dpd));\n        for(int i=0; i<rating.size(); ++i) {\n            res += fi(i,1,rating);\n            res += fd(i,1,rating);\n        }\n        return res;\n    }\n};\n```\n## Complexity\n- Time complexity: $$O(n*n)$$ \n\n- Space complexity: $$O(n)$$\n\n# Tabulation\n```\nclass Solution {\npublic:\n    int numTeams(vector<int>& rating) {\n        int n = rating.size();\n        vector<vector<int>> dpi(n, vector<int>(4,0));\n        vector<vector<int>> dpd(n, vector<int>(4,0));\n\n        // base case\n        for(int i=0;i<n;++i) dpi[i][3] = dpd[i][3] = 1;\n        \n        for(int cnt=2; cnt>0; --cnt) {\n            for(int idx=0; idx<n; ++idx) {\n                int res1 = 0;\n                int res2 = 0;\n                for(int i=idx+1; i<n; ++i) {\n                    if(rating[i] > rating[idx]) res1 += dpi[i][cnt+1];\n                    if(rating[i] < rating[idx]) res2 += dpd[i][cnt+1];\n                }\n                dpi[idx][cnt] = res1;\n                dpd[idx][cnt] = res2;\n            }\n        }\n\n        int res = 0;\n        for(int i=0; i<n; ++i) {\n            res += dpi[i][1];\n            res += dpd[i][1];\n        }\n        return res;\n    }\n};\n```\n## Complexity\n- Time complexity: $$O(n*n)$$ \n\n- Space complexity:$$O(n)$$\n\n# Greedy\n```\nclass Solution {\npublic:\n    int numTeams(vector<int>& rating) {\n        int n = rating.size();\n        int res = 0;\n        for(int j=1; j<n-1; ++j) {\n            int lefti = 0;\n            int leftd = 0;\n            for(int i=0; i<j; ++i) {\n                lefti += (rating[i] < rating[j]);\n                leftd += (rating[i] > rating[j]);\n            }\n            int righti = 0;\n            int rightd = 0;\n            for(int k=j+1; k<n; ++k) {\n                righti += (rating[j] < rating[k]);\n                rightd += (rating[j] > rating[k]);\n            }\n            res += lefti * righti + leftd * rightd;\n        }\n        return res;\n    }\n};\n```\n## Complexity\n- Time complexity: $$O(n*n)$$ \n\n- Space complexity:$$O(1)$$\n\n# Range Query DS (Segment Tree)\n```\n#define ll int\n// My Segment Tree Template (inspired from Pashka)\nclass item {\n    public:\n    ll val;\n    \n    item() {\n        val = 0;\n    }\n    \n    item(ll v) {\n        val = v;\n    }\n};\n \nclass SegTree {\n    public:\n    ll size;\n    vector<item> values;\n \n    item NEUTRAL_ELEMENT = item();\n \n    item merge(item l,item r) {\n        return item(l.val + r.val);\n    }\n \n    item single(ll v) {\n        return item(v);\n    }\n \n    void init(ll n) {\n        size = 1;\n        while(size < n) size *= 2; //for last level array with some extra nodes for complete binary tree\n        values.resize(2*size -1);  //for complete binary tree\n    }\n    \n    void build(vector<int> &a,ll x,ll lx,ll rx) {\n        //base case\n        if(rx-lx == 1) {\n            if(lx < int(a.size())) {\n                values[x] = single(a[lx]);\n            }\n            return; \n        }\n \n        ll m = (lx+rx)/2;\n        build(a,2*x +1,lx,m);\n        build(a,2*x +2,m,rx);\n        values[x] = merge(values[2*x +1],values[2*x +2]);\n    }\n \n    void build(vector<int> &a) {\n        build(a,0,0,size);\n    }\n \n    void set(ll i,ll v,ll x,ll lx,ll rx) {\n        //base case\n        if(rx-lx == 1) {\n            values[x] = single(v);\n            return;\n        }\n \n        ll m = (lx+rx)/2;\n        if(i < m) {\n            set(i,v,2*x +1,lx,m);\n        }\n        else {\n            set(i,v,2*x +2,m,rx);\n        }\n        values[x] = merge(values[2*x+1],values[2*x+2]);\n    }\n \n    void set(ll i,ll v) {\n        set(i,v,0,0,size);\n    }\n\n    item calc(ll l,ll r,ll x,ll lx,ll rx) {\n        //base cases\n        if(lx >= r || l >= rx) return NEUTRAL_ELEMENT;\n        if(lx >= l && rx <= r) return values[x];\n \n        ll m = (lx+rx)/2;\n        item s1 = calc(l,r,2*x+1,lx,m);\n        item s2 = calc(l,r,2*x+2,m,rx);\n        return merge(s1,s2);\n    }   \n \n    item query(ll l,ll r) {\n        return calc(l,r+1,0,0,size);\n    }\n};\n\nclass Solution {\npublic:\n    int numTeams(vector<int>& rating) {\n        int mx = 1e5;\n        SegTree st1, st2;\n        st1.init(mx), st2.init(mx);\n        \n        int n = rating.size();\n        for(int i=0; i<n; ++i) st2.set(rating[i], 1);\n\n        int res = 0;\n        for(int i=0; i<n; ++i) {\n            int lefti = st1.query(0,rating[i]-1).val;\n            int leftd = st1.query(rating[i]+1,mx).val;\n            int righti = st2.query(rating[i]+1,mx).val - leftd;\n            int rightd = st2.query(0,rating[i]-1).val - lefti;\n            st1.set(rating[i], 1);\n            res += lefti * righti + leftd * rightd;\n        }\n        return res;\n\n    }\n};\n```\n## Complexity\n- Time complexity: $$O(n*log(mx))$$ \n\n- Space complexity:$$O(mx)$$\n\n\n# PBDS\n```\n// PBDS template starts\n\n#include <ext/pb_ds/assoc_container.hpp>\n#include <ext/pb_ds/tree_policy.hpp>\n#include <ext/pb_ds/detail/standard_policies.hpp>\n#include <functional>\nusing namespace __gnu_pbds;\n\ntypedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;\n// ordered_set st; (use less_equal for multiset else use less for set)\n// st.order_of_key(k); Returns the number of elements strictly smaller than k.\n// st.find_by_order(k); Returns the address of the element at kth index in the set while using zero-based indexing\n// Each of these operations has a time complexity of O(log2(n))\n\n// PBDS template ends\n\nclass Solution {\npublic:\n    int numTeams(vector<int>& rating) {\n        ordered_set st1, st2;\n        int n = rating.size();\n        for(int i=0; i<n; ++i) st2.insert(rating[i]);\n        \n        int res = 0;\n        for(int i=0; i<n; ++i) {\n            int lefti = st1.order_of_key(rating[i]);\n            int leftd = st1.size() - lefti;\n            st1.insert(rating[i]);\n\n            st2.erase(rating[i]);\n            int rightd = st2.order_of_key(rating[i]);\n            int righti = st2.size() - rightd;\n\n            res += lefti * righti + leftd * rightd;\n        } \n        return res;\n    }\n};\n```\n## Complexity\n- Time complexity: $$O(n*log(n))$$ \n\n- Space complexity:$$O(n)$$\n\n\n\n\n**Hope you found this helpful\nIf so please do Upvote it\nHappy Coding!!**\n\n![leetcode.png](https://assets.leetcode.com/users/images/7a98ada3-fb9b-4413-8538-92fe790f4577_1701070150.1852815.png)\n\n
['Dynamic Programming', 'Greedy', 'Segment Tree', 'Ordered Set', 'C++']