-
Notifications
You must be signed in to change notification settings - Fork 0
LC 1395 [M] Count Number of Teams
Code with Senpai edited this page May 20, 2022
·
5 revisions
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