Easiest Code Ever - Python - Top 97% Speed - O( n log n ) Combinatorial
Easiest Code Ever - Python - Top 97% Speed - O( n log n ) Combinatorial\n\nThe code below simply loops through the array taking an element "x" as the pivot. Usi
**Easiest Code Ever - Python - Top 97% Speed - O( n log n ) Combinatorial**\n\nThe code below simply loops through the array taking an element "x" as the pivot. Using this pivot, we count separately the number of values:\n1. **Lower** than "x" to the **left** (lo_L)\n2. **Higher** than "x" to the **left** (hi_L)\n1. **Lower** than "x" to the **right**  (lo_R)\n2. **Higher** than "x" to the **right** (hi_R)\n\nThese values are then combined to update our result variable:\n* result +=  lo_L * hi_R + hi_L * lo_R\n\nThe idea makes a lot of sense after a moment (a detailed explanation of the formula can be found below).\n\nNow, the 4 tracked variables can be obtained in two ways:\n1. The best way is to use SortedLists containing all the values to the Left and Right of our pivot. Using binary search, we can find the index of our pivot in these lists, and quickly deduce the number of elements higher or lower. This allows us to have a O( n log n ) solution.\n2. Otherwise, we can use two nested loops to build our counting variables primitively. This gives us a O(n^2) solution.\n\nBoth code versions are presented below. I hope the explanation was helpful. Cheers,\n\n```\n# Version A:  [Top Speed] O(n log n) solution using SortedLists to calculate our 4 counting variables in Log(n) time.\nfrom sortedcontainers import SortedList\nclass Solution:\n    def count_low_high(self,sl,x):\n        lo =           sl.bisect_left(x)\n        hi = len(sl) - lo\n        return lo, hi\n    \n    def numTeams(self, A):\n        result = 0\n        left   = SortedList()\n        right  = SortedList(A)\n        for x in A:\n            right.remove(x)\n            lo_L, hi_L  =  self.count_low_high(left ,x)\n            lo_R, hi_R  =  self.count_low_high(right,x)\n            result     +=  lo_L*hi_R + hi_L*lo_R\n            left .add(x)\n        return result\n```\n\n```\n# Version B:  O(n^2) solution with (primitive) nested loops for building our 4 counting variables.\nclass Solution:\n    def numTeams(self, A):\n        L = len(A)\n        result = 0\n        for j in range(1,L-1):\n            x, lo_L, lo_R, hi_L, hi_R = A[j], 0, 0, 0, 0\n            for i in range(j):\n                if A[i]<x:\n                    lo_L += 1\n                else:\n                    hi_L += 1\n            for k in range(j+1,L):\n                if A[k]<x:\n                    lo_R += 1\n                else:\n                    hi_R += 1\n            result += lo_L*hi_R + hi_L*lo_R\n        return result\n```\n\n\n**PS.** Detailed explanation of the formula ``` lower_left * higher_right + higher_left * lower_right``` :\n\nThe 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:\n1) 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```.\n2) 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```.\n\nAs 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.
['Python', 'Python3']