3 Java solutions: Brute force / DP / Math
Method 1: Brute force\n\n Time: O(N^3)\n Space: O(1)\n\n\nclass Solution {\n    public int numTeams(int[] rating) {\n        int n = rating.length, cnt = 0;\n  
**Method 1: Brute force**\n\n* Time: ```O(N^3)```\n* Space: ```O(1)```\n\n```\nclass Solution {\n    public int numTeams(int[] rating) {\n        int n = rating.length, cnt = 0;\n        for(int i = 0; i < n; i++) {\n            for(int j = 0; j < i; j++) {\n                if(rating[i] < rating[j]) {\n                    for(int k = 0; k < j; k++) {\n                        if(rating[j] < rating[k]) cnt++;\n                    }\n                }\n                if(rating[i] > rating[j]) {\n                    for(int k = 0; k < j; k++) {\n                        if(rating[j] > rating[k]) cnt++;\n                    }\n                }\n            }\n        }\n        return cnt;\n    }\n}\n```\n\n---\n\n\n**Method 2: DP solution**\n\n\n**Idea:**\n\n1. First, we calculate this case ```rating[i] > rating[j] > rating[k]``` given that ```i > j > k```. Then, calculate the case ```rating[i] < rating[j] < rating[k]```.\n2. Define ```dp[i]```: How many items in rating from ```0``` to ```i-1``` are smaller than ```rating[i]```.\n3. For every time we found ```rating[i] > rating[j]```, we accumulate ```dp[j]```. Here, ```dp[j]``` means how many ```rating[k]``` exist from ```0``` to ```j-1```. That is, how many cases satisfy ```rating[i] > rating[j] > rating[k]```.\n\n\n* Time: ```O(N^2)```\n* Space: ```O(N)```\n\n```\nclass Solution {\n    public int numTeams(int[] rating) {\n        return helper(rating) + helper(reverse(rating));\n    }\n    private int helper(int[] rating) {\n        int n = rating.length, ans = 0;\n        int[] dp = new int[n];\n        for(int i = 0; i < n; i++) {\n            for(int j = 0; j < i; j++) {\n                if(rating[i] > rating[j]) {\n                    dp[i]++;\n                    ans += dp[j];\n                }\n            }\n        }\n        return ans;\n    }\n    private int[] reverse(int[] rating) {\n        int l = 0, r = rating.length-1;\n        while(l < r) {\n            int tmp = nums[i];\n            nums[i] = nums[j];\n            nums[j] = tmp;\n            l++;\n            r--;\n        }\n        return rating;\n    }\n}\n```\n\n---\n\n**Method 3: Mathematic solution**\n\n**Idea:**\n\n1. For a given ```rating[j]```,\n\t1. Find how many items on the left side ```rating[i]``` are smaller than ```rating[j]```.\n\t2. Find how many items on the left side ```rating[i]``` are larger than ```rating[j]```.\n\t3. \tFind how many items on the right side ```rating[k]``` are smaller than ```rating[j]```.\n\t4. \tFind how many items on the right side ```rating[k]``` are larger than ```rating[j]```.\n2. For a given ```rating[j]```, accumulate \n\t1. ```leftsmaller * rightlarger``` which means how many cases are ```rating[i] < rating[j] < rating[k]```, and\n\t2. ```leftlarger * rightsmaller```, which means how many cases are ```rating[i] > rating[j] > rating[k]```.\n\n\n* Time: ```O(N^2)```\n* Space: ```O(1)```\n\n```\nclass Solution {\n    public int numTeams(int[] rating) {\n        int ans = 0, n = rating.length;\n        for(int j = 0; j < n; j++) {\n            int leftsmaller = 0, leftlarger = 0, rightsmaller = 0, rightlarger = 0;\n            // On the left side of j\n            for(int i = 0; i < j; i++) {\n                if(rating[i] < rating[j]) leftsmaller++;\n                if(rating[i] > rating[j]) leftlarger++;\n            }\n            // On the right side of j\n            for(int k = j+1; k < n; k++) {\n                if(rating[k] < rating[j]) rightsmaller++;\n                if(rating[k] > rating[j]) rightlarger++;\n            }\n            ans += leftsmaller * rightlarger + leftlarger * rightsmaller;\n        }\n        return ans;\n    }\n}\n\n```
[]