Rust 12ms/Python 500ms. Quadratic with detailed explanation
Intuition\nLets assume that we already have some array and for it we already calculated imbalanced number for it. Lets assume that the array is [1, 5, 6, 8, 12]
# Intuition\nLets assume that we already have some array and for it we already calculated imbalanced number for it. Lets assume that the array is `[1, 5, 6, 8, 12]`. The number here is 3, but right now it is not important at all. What we will be focusing on is what happens when we add a new element to this sorted list.\n\nThe easiest case is when **the number is already in the list**. As you see that the imbalanced number is not changed. Now when the element is inserted somewhere in the array.\n\nThe important part is whetehr the element +1 or -1 already exist. If they do not exist (for example we add element 10 and we see that 9 and 11 do not exist) we see that out of 1 previous imbalanced number, we got 2 (`+1`)\n\nIf we add an element 7, and we see that 6 and 8 both exist we see that out of previous 1 imbalanced number, we got 0 (`-1`).\n\nIf we add number 4 (where one exist and another does not), the number does not change.\n\n# Complexity\n- Time complexity: $O(n^2)$\n- Space complexity: $O(n)$\n\n# Code\n```Rust []\nimpl Solution {\n  pub fn sum_imbalance_numbers(nums: Vec<i32>) -> i32 {\n    let (mut res, n) = (0, nums.len());\n    for i in 0 .. n - 1 {\n      let mut seen = vec![false; n + 2];\n      let mut curr = 0;\n      seen[nums[i] as usize] = true;\n\n      for j in i + 1 .. n {\n        let p = nums[j] as usize;\n        if !seen[p] {\n          seen[p] = true;\n          if seen[p - 1] && seen[p + 1] {\n            curr -= 1;\n          } else if !seen[p - 1] && !seen[p + 1] {\n            curr += 1;\n          }\n        }\n        res += curr;\n      }\n    }\n    return res;\n  }\n}\n```\n```python []\nclass Solution:\n  def sumImbalanceNumbers(self, nums: List[int]) -> int:\n    res = 0\n    for i in range(len(nums)):\n      seen, curr = [0] * (len(nums) + 2), 0\n      seen[nums[i]] = True\n      for j in range(i + 1, len(nums)):\n        if not seen[nums[j]]:\n          seen[nums[j]] = True\n          if seen[nums[j] - 1] and seen[nums[j] + 1]:\n            curr -= 1\n          elif not seen[nums[j] - 1] and not seen[nums[j] + 1]:\n            curr += 1\n\n        res += curr\n\n    return res\n```
['Python3', 'Rust']