[Python] From DP O(N^2) >88%, to BIT O(NlogN) > 98%, and thought about 100%
Preface\n\nThis post is a summary about my trip exploring this problem. The question can be solved naively in O(N^3). By a simple "DP" , it can be solved in O(N
**Preface**\n\nThis post is a summary about my trip exploring this problem. The question can be solved naively in O(N^3). By a simple "DP" , it can be solved in O(N^2). I will choose the DP version as the baseline, and show improvements over it. For people not familiar with DP, please check <u>[post #1](https://leetcode.com/problems/count-number-of-teams/discuss/554918/Python-Easy-O(N2)-DP-solution)</u> for the intuition of "DP" solution.\n\n**Abstract Pickup**\n\nThe DP-like O(N^2) solution should be fine for simple interviews. For advanced ones, one should either be familiar with the implementation of BIT, or use the `bisect.insort` cleverly.\n\nTo scale, `SortedList`  may be a competitive solution for single server, while SQL window operations in O(N^2) is more practical for distributed situation.\n\n\n**Runtime and Menory table**\n\n<img src="https://assets.leetcode.com/users/images/a96191af-4b56-46a3-80e6-50a0cb3a9f51_1624235989.3516107.png" style="width:600px;height:250px">\n\n**Start From "DP"**\n\nThe basic idea of DP is to keep memo about number of rating smaller or larger than current one. Then we can take advantage of the `lg` and `sm` memo to count the number of valid tuple.\n```\n# My DP #\ndef numTeams(self, rating: List[int]) -> int:\n        l = len(rating)-1\n        lg,sm,res = [0]*l,[0]*l,0\n        for i in range(1,l):\n            v = rating[i]\n            for j in range(i):\n                if v<rating[j]:\n                    lg[i] += 1\n                    res += lg[j]\n                else:\n                    sm[i] += 1\n                    res += sm[j]\n        v = rating[-1]\n        return res + sum(lg[j] if v<rating[j] else sm[j] for j in range(l))\n```\nWe can easliy found that `lg` and `sm` is redundent. To improve, just remove `sm` and replace the `sm[j]` parts with `(j - lg[j])`. <u>*(DP-v2)*</u>\n\n**Change the Entry Point**\n\nFor a tuple` (i, j, k)`,  the DP above trys to iterate first on `k`, look up each `j` before it, then add up either `sm[j]` or `lg[j]` based on the relationship between `rating[k]` and `rating[j]`. If we change the entry point and first iterate on `j`,  there is another vaild O(N^2) solution, where we can check valid `i` and `k` for each `j` within O(N). \n\nThis idea is written in <u>[post #2](https://leetcode.com/problems/count-number-of-teams/discuss/565479/python-greater97.98-simple-logic-and-very-detailed-explanation)</u>.  Although runtime in this title is outdated and it is slower than the DP above, It is easy to implement and instructive for the O(NlogN) solution.\n\n**Binary Index Tree(BIT)**\n\nIn the section above, we spent O(N) to count valid `i` and `k` for each `j`. What if we can narrow it down to O(logN)? <u> [post #3](https://leetcode.com/problems/count-number-of-teams/discuss/554907/Java-Detailed-Explanation-TreeSet-greater-BIT-(Fenwick-Tree)-O(NlogN)) </u> came up with a clever idea to utlize <u>[BIT](https://en.wikipedia.org/wiki/Fenwick_tree)</u> to calculate valid `i` and `k`. \n\nBIT is a space-efficient structure, which can update element in array and calculate prefix sum in O(logN).  In this question, we can take advantage of the uniqueness of the `rating` values and use it as indexs. The BIT here can be used as a counter which can show the amount of smaller or larger numbers in O(logN).\n\nMy simplified version of BIT is followings. Only limitted function is needed for this question.\n```\ndef lastbit(i): return i & -i\ndef parent(i): return i & (i - 1)   # parent(i) = i - lastbit(i)\ndef nextpow(i): return i + lastbit(i) \n\nclass BIT:\n    def __init__(self,li):\n        self.li = li\n\n    def adjust(self,i,dv):\n        l = len(self.li)\n        while i<l:\n            self.li[i] += dv\n            i = nextpow(i)\n\n    def prefixsum(self,i):\n        su = 0\n        while i > 0:\n            su += self.li[i]\n            i = parent(i)\n        return su\n```\n\nFollowing the post I mentioned, I rewite and accelerate the solution with some math tricks.\n```\n# MY BIT #\nclass Solution:\n    def numTeams(self, rating: List[int]) -> int:\n        M,l = max(rating)+1,len(rating)-1\n        lt,rt = BIT([0]*M),BIT([0]*M)\n        for r in rating: rt.adjust(r,1)\n            \n        res = 0\n        for i,r in enumerate(rating):\n            rt.adjust(r,-1)\n            p1,p2 = lt.prefixsum(r-1),rt.prefixsum(r-1)\n            res += p1*(l-i-p2) + (i-p1)*p2\n            lt.adjust(r,1)\n            \n        return res\n```\nWith futher math inside, the loop part can be revised as this:\n```\n# BIT - v2 #\nfor i,r in enumerate(rating):\n\tp1,p2 = lt.prefixsum(r-1),rt.prefixsum(r-1)\n\tres += p1*(l-p2) + (i-p1)*(p2-p1*2)\n\tlt.adjust(r,1)\n```\n\n**Stain, and Dual Problem**\n\nLet `N=len(rating)` and `M=max(rating)`, the solution above is actually O(NlogM) in time and O(M) in space. The constraint here gives `N<=1000 and M<=100_000`, which makes it a small problem. But if `M` is much larger than  `N`, the waste of time and space will be significant. \n\nTo solve this problem and accelerate it to real O(NlogN), we can look at the dual question.  The original question is to find `rating[i]<rating[j]<rating[k]`(or reverse) while `i<j<k`. the later condition is guaranteed by the order of `rating` array, so we only need to check the former condition.\n\nNow we can obtain an index array `index` by sorting `rating`, where `rating[index[i1]]<rating[index[i2]]` if `i1<i2`. In another word,  `rating[index[i1]]<rating[index[i2]]<rating[index[i3]]` is guaranteed by order of array `index`.  The origional question is equavalent to a duel question to check whether `index[i]<index[i2]<index[i3]`(or reverse) in`index` when `i1<i2<i3`.\n\n**BIT Duel Question**\n\nFor the duel problem, the constiant will become `1<= index[i] <=N` (1- indexed). Hence, the time and space complexity are exact  O(NlogN) and O(N).  The corresponding reversion is here:\n```\n# BIT (duel) #\ndef numTeams(self, rating: List[int]) -> int:\n\tl = len(rating) + 1\n\tindex = sorted(range(1,l), key = lambda i: rating[i-1])\n\tlt,rt = BIT([0]*l),BIT([0]*l)\n\tfor r in index: rt.adjust(r,1)\n\n\tres = 0\n\tl -= 2\n\tfor i,r in enumerate(index):\n\t\tp1,p2 = lt.prefixsum(r-1),rt.prefixsum(r-1)\n\t\tres += p1*(l-p2) + (i-p1)*(p2-p1*2)\n\t\tlt.adjust(r,1)\n\n\treturn res\n```\nAnother advantage of switching to duel problem is that `rt` can be eliminated. Since the values of `index` array are distinct and are exact `1 to N`. The number of index smaller or larger than specific index is really obvious. Hence the final version I have is here:\n```\n# BIT (duel) - v2 #\ndef numTeams(self, rating: List[int]) -> int:\n\tl = len(rating) + 1\n\tindex = sorted(range(1,l), key = lambda i: rating[i-1])\n\tlt = BIT([0]*l)\n\n\tres = 0\n\tl -= 2\n\tfor i,r in enumerate(index):\n\t\tp1,p2 = lt.prefixsum(r-1),r-1\n\t\tres += p1*(l-p2) + (i-p1)*(p2-p1*2)\n\t\tlt.adjust(r,1)\n\n\treturn res\n```\n\n**Check Solutions above 99%**\n\nAfter obtained my final solution, I find that there are still 2% to overcome. So I check the top solutions and find the reason. In brief, O(NlogN) is the best complexity theoritcally, but the constant factor matters here as the N is not large enough.\n\nThe top solution use a clever version of DP with `bisect.insort`. In theory, each insort cost O(N) and in all O(N^2). But it is a little faster since N is small and `insort` is a fully optimized python native operation.\n\n**Scale**\n\nThis reason above is common and not interesting at all. The real interesting part is " `from sortedcontainers import SortedList` " used by one of these solutions, which is useful for scaling. \n\nAfter check the <u> [official website](http://www.grantjenks.com/docs/sortedcontainers/#testimonials) </u> of sortedcontainers, I find that `SortedList`  could be a competetive solution for large data handleable by a single server. `SortedList` is an hierarchical list implemented by pure python. It is designed to solve the bad performance of normal `insort` with elements over several thousands. With great design of structure, advantage of locality and optimization on low level, it overperforms other theoritical O(NlogN) structures like AVL-tree, RB-tree, and Skip-list a lot on scale of several billion or trillion, which is almost enough for common use case.\n\nIf the data scale needs to be distributed to store, the choice may be different. DP O(N^2) solution can be easily implemented by `window`, `index`, and `count` in SQL, and further run on Spark over nearly any amount of data.  On the contrary, O(NlogN) or `SortedList` solution require frequent adjustments over elements in order, which may not very suit for distributed situation.\n
['Dynamic Programming', 'Binary Indexed Tree']