Java O(n^2) solution one pass
According to the description, any three rating values must satisfy i < j < k and rating[i] < rating[j] < rating[k] or rating[i] > rating[j] > rating[k]. \nIf we
According to the description, any three rating values must satisfy i < j < k and rating[i] < rating[j] < rating[k] or rating[i] > rating[j] > rating[k]. \nIf we select a value as rating[j] from the rating array, we only need to find rating values:\n* less than rating[j] and its index smaller than j as rating[i]\n* lager than rating[j] and its index lager than j as rating[k]\nor\n* less than rating[j] and its index lager than j as rating[i]\n* lager than rating[j] and its index smaller than j as rating[k].\n\n(in code, "less" or "lager" means values\' comparison, "before" or "after" means positions\' or indices\' comparison)\n\nAll team should meet the property that i < j < k. The first group rating values forms teams rating[i] < rating[j] < rating[k] and the second group forms teams rating[i] > rating[j] > rating[k].\n\nThe number of a rating value forming teams and being the middle value equals sum of the number of teams belong to the first and the second group.\n\nFor example,\n**Input:** rating = [2,5,3,4,1]\n1. 5 is rating[j], number of lessBefore is 1 (2) and number of lagerAfter is 0; number of lagerBefore is 0 and number of lessAfter is 3 (3, 4, 1). Number of teams in the first group is 0 and number of teams in the second group is 0. 0 teams can be formed when the value 5 is rating[j].\n2. 3 is rating[j], number of lessBefore is 1 (2) and number of lagerAfter is 1 (4); number of lagerBefore is 1 (5) and number of lessAfter is 1 (1). Number of teams in the first group is 1 and number of teams in the second group is 1. 2 teams can be formed when the value 5 is rating[j].\n3. 4 is rating[j], number of lessBefore is 2 (2, 3) and number of lagerAfter is 0; number of lagerBefore is 1 (5) and number of lessAfter is 1 (1). Number of teams in the first group is 0 and number of teams in the second group is 1. 1 team can be formed when the value 5 is rating[j].\n\nThe total number of teams can be formed based on the rating array is 3 (0 + 2 + 1 = 3).\n\n```\nclass Solution {\n    public int numTeams(int[] rating) {\n        int ans = 0, lagerAfter, lagerBefore, lessAfter, lessBefore;\n        for(int i = 1; i < rating.length - 1; i++) {\n            lagerAfter = lagerBefore = lessAfter = lessBefore = 0;\n            for(int j = 0; j < rating.length; j++) {\n                if(i == j) continue;\n                if(rating[i] < rating[j]) {\n                    if(i < j) {\n                        lessBefore++;\n                    } else {\n                        lessAfter++;\n                    }\n                } else {\n                    if(i < j) {\n                        lagerBefore++;\n                    } else {\n                        lagerAfter++;\n                    }\n                }\n            }\n            ans += lagerAfter * lessBefore + lagerBefore * lessAfter;\n        }\n        return ans;\n    }\n}\n```
[]