Sum of Imbalance Numbers of All Subarrays
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 - 1sarr[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.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1
Input
nums = [2,3,1,4]Output
3The only subarrays with non-zero imbalance numbers are [3, 1], [3, 1, 4], and [1, 4], each contributing 1, so the total is 3.
Example 2
Input
nums = [1,3,3,3,5]Output
8The seven listed subarrays with non-zero imbalance numbers contribute a total of 8, while all other subarrays contribute 0.
Constraints
- 1 <= nums.length <= 1000
- 1 <= nums[i] <= nums.length