LC 1395 [M] Count Number of Teams - ALawliet/algorithms GitHub Wiki

total number of combinations = number of ascending + descending combinations for each pivot

for every rating = pivot = b we can build number of ascending combinations = left side less than b * right side greater than b number of descending combinations = left side greater than b * right side less than b

PS. Detailed explanation of the formula lower_left * higher_right + higher_left * lower_right :

The formula comes from the fact that we need to create triplets with the form a<b<c or a>b>c. Since b can be regarded as the pivotal point dividing the sequence, we notice that we can form triplets by choosing:

For a<b<c, choose any number a (to the left) lower than b, and any number c to the right which is higher. The total number of combinations for this case is lower_left*higher_right.
For a>b>c, reverse the previous process. Choose any number a to the left higher than b, and any subsequent number c which is lower. This creates a total number of combinations higher_left*lower_right.
As you can see, summing the combinations for both alternatives gives us the formula total = lower_left*higher_right + higher_left*lower_right. The rest of the code is just book-keeping, and choosing good Data Structures to handle the problem easily.

# O(n^2)
class Solution:
    def numTeams(self, rating: List[int]) -> int:
        asc = dsc = 0
        
        for i, b in enumerate(rating):
            ll = rg = lg = rl = 0
            
            for l in rating[:i]:
                if l < b:
                    ll += 1
                if l > b:
                    lg += 1
                    
            for r in rating[i+1:]:
                if r > b:
                    rg += 1
                if r < b:
                    rl += 1
                    
            asc += ll * rg
            dsc += lg * rl

        return asc + dsc

sortedlist kind of like how a balanced binary search tree or red-black tree or BIT fenwick tree can add and search in logn time

# Version A:  [Top Speed] O(n log n) solution using SortedLists to calculate our 4 counting variables in Log(n) time.
from sortedcontainers import SortedList
class Solution:
    def count_low_high(self,sl,x):
        lo =           sl.bisect_left(x)
        hi = len(sl) - lo
        return lo, hi
    
    def numTeams(self, A):
        result = 0
        left   = SortedList()
        right  = SortedList(A)
        for x in A:
            right.remove(x)
            lo_L, hi_L  =  self.count_low_high(left ,x)
            lo_R, hi_R  =  self.count_low_high(right,x)
            result     +=  lo_L*hi_R + hi_L*lo_R
            left .add(x)
        return result

footer

⚠️ **GitHub.com Fallback** ⚠️