🐼 Beats 96.63% (14ms)🔥 | 3 Solutions | ✅
\n\n# Solution 1: Brute Force\n- Complexity:\n    - Time: O(n^3)\n    - Space: O(1)\n# Code\nC++ []\nclass Solution {\npublic:\n    int numTeams(vector<int>& ra
![image.png](https://assets.leetcode.com/users/images/d34b4840-fc1e-4303-b29d-50a632af34b5_1722233126.3701148.png)\n\n# Solution 1: Brute Force\n- Complexity:\n    - Time: O(n^3)\n    - Space: O(1)\n# Code\n```C++ []\nclass Solution {\npublic:\n    int numTeams(vector<int>& rating) {\n        int res = 0;\n        for(int i=0; i<rating.size()-2; i++){\n            for(int j=i+1; j<rating.size()-1; j++){\n                for(int k=j+1; k<rating.size(); k++){\n                    if(rating[i] > rating[j] && rating[j]  > rating[k]){\n                        res++;\n                    }\n                    if(rating[i] < rating[j] && rating[j] < rating[k]){\n                        res++;\n                    }\n                }\n            }\n        }\n        return res;\n    }\n}; \n```\n```Java []\nclass Solution {\n    public int numTeams(int[] rating) {\n        int res = 0;\n        for (int i = 0; i < rating.length - 2; i++) {\n            for (int j = i + 1; j < rating.length - 1; j++) {\n                for (int k = j + 1; k < rating.length; k++) {\n                    if ((rating[i] < rating[j] && rating[j] < rating[k]) || (rating[i] > rating[j] && rating[j] > rating[k])) {\n                        res++;\n                    }\n                }\n            }\n        }\n        return res;\n    }\n}\n```\n```Python []\n# TLE\nclass Solution(object):\n    def numTeams(self, rating):\n        res = 0\n        n = len(rating)\n        for i in range(n - 2):\n            for j in range(i + 1, n - 1):\n                for k in range(j + 1, n):\n                    if (rating[i] < rating[j] < rating[k]) or (rating[i] > rating[j] > rating[k]):\n                        res += 1\n        return res\n        \n```\n```Javascript []\n// TLE\nvar numTeams = function(rating) {\n    let res = 0;\n    for (let i = 0; i < rating.length - 2; i++) {\n        for (let j = i + 1; j < rating.length - 1; j++) {\n            for (let k = j + 1; k < rating.length; k++) {\n                if ((rating[i] < rating[j] && rating[j] < rating[k]) || (rating[i] > rating[j] && rating[j] > rating[k])) {\n                    res++;\n                }\n            }\n        }\n    }\n    return res;\n};\n```\n# Solution 2: Adjacency Lists\n\n# Intuition\nUse adjacency lists to store pairs of ratings where one is greater or less than the other. Then use these lists to count the number of valid triplets.\n# Approach\n- Create two adjacency lists to store ratings that are greater or less than the current rating.\n- Iterate through the ratings and count the number of valid triplets using the adjacency lists.\n# Complexity\n- Time: O(n*n)\n- Space: O(n*n)\n# Code\n```C++ []\nclass Solution {\npublic:\n    int numTeams(vector<int>& rating) {\n        int maxi = 0;\n        for(const int & i : rating){\n            maxi = max(maxi,i);\n        }\n        vector<vector<int>> adj1(maxi+1),adj2(maxi+1);\n        for(int i=0; i<rating.size(); i++){\n            for(int j=i+1; j<rating.size(); j++){\n                if(rating[i] > rating[j]){\n                    adj1[rating[i]].push_back(rating[j]);\n                }else if(rating[i] < rating[j]){\n                    adj2[rating[i]].push_back(rating[j]);\n                }\n            }\n        }\n        int res = 0;\n        for(const int & i : rating){\n            for(const int & j : adj1[i])\n                res += adj1[j].size();\n            for(const int & j : adj2[i])\n                res += adj2[j].size();\n        }\n\n        return res;\n    }\n};\n```\n```Java []\nclass Solution {\n    public int numTeams(int[] rating) {\n        int n = rating.length;\n        int maxRating = 0;\n        for (int r : rating) {\n            maxRating = Math.max(maxRating, r);\n        }\n        List<Integer>[] adj1 = new List[maxRating + 1];\n        List<Integer>[] adj2 = new List[maxRating + 1];\n        for (int i = 0; i <= maxRating; i++) {\n            adj1[i] = new ArrayList<>();\n            adj2[i] = new ArrayList<>();\n        }\n        for (int i = 0; i < n; i++) {\n            for (int j = i + 1; j < n; j++) {\n                if (rating[i] > rating[j]) {\n                    adj1[rating[i]].add(rating[j]);\n                } else if (rating[i] < rating[j]) {\n                    adj2[rating[i]].add(rating[j]);\n                }\n            }\n        }\n        int res = 0;\n        for (int r : rating) {\n            for (int j : adj1[r]) {\n                res += adj1[j].size();\n            }\n            for (int j : adj2[r]) {\n                res += adj2[j].size();\n            }\n        }\n        return res;\n    }\n}\n```\n```Python []\nclass Solution(object):\n    def numTeams(self, rating):\n        n = len(rating)\n        maxi = max(rating)\n        adj1 = [[] for _ in range(maxi + 1)]\n        adj2 = [[] for _ in range(maxi + 1)]\n        \n        for i in range(n):\n            for j in range(i + 1, n):\n                if rating[i] > rating[j]:\n                    adj1[rating[i]].append(rating[j])\n                elif rating[i] < rating[j]:\n                    adj2[rating[i]].append(rating[j])\n        \n        res = 0\n        for r in rating:\n            for j in adj1[r]:\n                res += len(adj1[j])\n            for j in adj2[r]:\n                res += len(adj2[j])\n        \n        return res\n```\n```Javascript []\nvar numTeams = function(rating) {\n    let maxi = Math.max(...rating);\n    let adj1 = Array.from({ length: maxi + 1 }, () => []);\n    let adj2 = Array.from({ length: maxi + 1 }, () => []);\n    \n    for (let i = 0; i < rating.length; i++) {\n        for (let j = i + 1; j < rating.length; j++) {\n            if (rating[i] > rating[j]) {\n                adj1[rating[i]].push(rating[j]);\n            } else if (rating[i] < rating[j]) {\n                adj2[rating[i]].push(rating[j]);\n            }\n        }\n    }\n    \n    let res = 0;\n    for (let r of rating) {\n        for (let j of adj1[r]) {\n            res += adj1[j].length;\n        }\n        for (let j of adj2[r]) {\n            res += adj2[j].length;\n        }\n    }\n    return res;\n};\n```\n# Solution 3: Counting with Prefix Sums\n\n# Intuition\nUse a single loop to iterate through each soldier\'s rating and count the number of valid soldiers on the left and right sides.\n# Approach\n- For each soldier, count the number of ratings less and greater on the left and right sides.\n- Use these counts to calculate the number of valid triplets.\n# Complexity\n- Time: O(n*n)\n- Space: O(1)\n# Code\n```C++ []\nclass Solution {\npublic:\n    int numTeams(vector<int>& rating) {\n        int res = 0,n=rating.size();\n        for(int i=1; i<n; i++){\n            int ls,lg,rs,rg;\n            ls = lg = rs = rg = 0;\n            for(int j=0; j<i; j++){\n                if(rating[j] < rating[i]) ls++;\n                else lg++;\n            }\n            for(int j=i+1; j<n; j++){\n                if(rating[j] < rating[i]) rs++;\n                else rg++;\n            }\n            res += (ls*rg) + (rs*lg);\n        }\n        return res;\n    }\n};\n\n```\n```Java []\nclass Solution {\n    public int numTeams(int[] rating) {\n        int res = 0, n = rating.length;\n        for (int i = 1; i < n; i++) {\n            int ls = 0, lg = 0, rs = 0, rg = 0;\n            for (int j = 0; j < i; j++) {\n                if (rating[j] < rating[i]) ls++;\n                else lg++;\n            }\n            for (int j = i + 1; j < n; j++) {\n                if (rating[j] < rating[i]) rs++;\n                else rg++;\n            }\n            res += (ls * rg) + (rs * lg);\n        }\n        return res;\n    }\n}\n```\n```Python []\nclass Solution(object):\n    def numTeams(self, rating):\n        res = 0\n        n = len(rating)\n        for i in range(1, n):\n            ls = lg = rs = rg = 0\n            for j in range(i):\n                if rating[j] < rating[i]:\n                    ls += 1\n                else:\n                    lg += 1\n            for j in range(i + 1, n):\n                if rating[j] < rating[i]:\n                    rs += 1\n                else:\n                    rg += 1\n            res += (ls * rg) + (rs * lg)\n        return res\n```\n```Javascript []\nvar numTeams = function(rating) {\n    let res = 0;\n    let n = rating.length;\n    \n    for (let i = 1; i < n; i++) {\n        let ls = 0, lg = 0, rs = 0, rg = 0;\n        \n        for (let j = 0; j < i; j++) {\n            if (rating[j] < rating[i]) {\n                ls++;\n            } else {\n                lg++;\n            }\n        }\n        \n        for (let j = i + 1; j < n; j++) {\n            if (rating[j] < rating[i]) {\n                rs++;\n            } else {\n                rg++;\n            }\n        }\n        \n        res += (ls * rg) + (rs * lg);\n    }\n    return res;\n};\n```\n![Please hit the upvote button (1).png](https://assets.leetcode.com/users/images/bcdb6ec5-cf10-46d7-aa29-847472512981_1722233446.5427694.png)\n
['Array', 'Python', 'C++', 'Java', 'JavaScript']