Update Imbalance Number when Extending Subarray | Explanation
Ituition\nN is 1000, so we can use O(n^2) to find all combination of subarrays, but for every subarray, we are limited to use O(1) or O(log n) to update and que
# Ituition\nN is 1000, so we can use O(n^2) to find all combination of subarrays, but for every subarray, we are limited to use O(1) or O(log n) to update and query the imbalance number.\n# Method\nWe start with a fixed left bound `i` of the subarray.\nEverytime we include `nums[j]` into the sorted data structure, where j from `i` to `len(nums)-1`.\nWe count the imbalance number like this:\nWe find the position `c` in the sorted list `sl` where we want to insert `nums[j]` into, that is, we have `sl[c] >= nums[j] >= sl[c-1]` if `c` and `c-1` are valid indexes in `sl`.\nThen, we should break the "imbalance relation" between `(sl[c], sl[c-1])` and build the "imbalance relation" between `(sl[c], nums[j])` and `(nums[j], sl[c-1])`.\nThat is, we can update the imbalance number by `-1` if `sl[c] - sl[c-1] > 1`, and `+1` if `sl[c] - nums[j] > 1` and `+1` if `nums[j] - sl[c-1] > 1`.\n\n\n# Complexity\nTime Complexity: O(n^2\\*log(n))\nSpace Complexity: O(n)\n# Code\n```\nfrom sortedcontainers import SortedList\nclass Solution:\n    def sumImbalanceNumbers(self, nums: List[int]) -> int:\n        ans = 0\n        for i in range(len(nums)):\n            \n            sl = SortedList()\n            imb = 0\n            \n            for j in range(i, len(nums)):\n                c = sl.bisect_left(nums[j])\n                if len(sl) == 0:\n                    sl.add(nums[j])\n                    continue\n                elif c == 0:\n                    if sl[c] - nums[j] > 1:\n                        imb += 1\n                elif c == len(sl):\n                    if nums[j] - sl[-1] > 1:\n                        imb += 1\n                else:\n                    if sl[c] - sl[c-1] > 1:\n                        imb -= 1\n                    if sl[c] - nums[j] > 1:\n                        imb += 1\n                    if nums[j] - sl[c-1] > 1:\n                        imb += 1\n                ans += imb\n                sl.add(nums[j])\n        return ans\n                \n```
['Python3']