Sum of Imbalance Numbers of All Subarrays — LeetCode 2763 Python Solution

The problem

The imbalance number of a 0-indexed integer array arr of length n is defined as the number of indices in sarr = sorted(arr) such that: 0 <= i < n - 1, and sarr[i+1] - sarr[i] > 1 Here, sorted(arr) is the function that returns the sorted version of arr. Given a 0-indexed integer array nums, return the sum of imbalance numbers of all its subarrays.

Example

Input

nums = [2,3,1,4]

Output

3

Explanation

There are 3 subarrays with non-zero imbalance numbers:

Python solution

class Solution:
    def sumImbalanceNumbers(self, nums: List[int]) -> int:
        n = len(nums)
        ans = 0
        for i in range(n):
            sl = SortedList()
            cnt = 0
            for j in range(i, n):
                k = sl.bisect_left(nums[j])
                h = k - 1
                if h >= 0 and nums[j] - sl[h] > 1:
                    cnt += 1
                if k < len(sl) and sl[k] - nums[j] > 1:
                    cnt += 1
                if h >= 0 and k < len(sl) and sl[k] - sl[h] > 1:
                    cnt -= 1
                sl.add(nums[j])
                ans += cnt
        return ans

Complexity

Pattern: Hash Map

Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 2763. Sum of Imbalance Numbers of All Subarrays is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Hash Table.

The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.

Related problems