972. Imbalance Total
For any non-empty subarray, sort its elements and count the neighbouring pairs in the sorted order whose difference is strictly greater than 1; that count is the imbalance of the subarray. Equal neighbours (difference 0) and consecutive integers (difference 1) never count. For example the subarray [5, 1, 2] sorts to 1, 2, 5 and has imbalance 1.
Given nums, return the sum of the imbalance over every contiguous subarray (single-element subarrays contribute 0). The input is guaranteed to be such that the answer fits in a signed 32-bit integer.
Example 1
- Input:
- nums = [2,5,3]
- Output:
- 3
- Explanation:
The subarrays [2,5], [5,3] and [2,5,3] each have one gap bigger than 1 when sorted (3 to 5 or 2 to 5), single elements have none, total 3.
Example 2
- Input:
- nums = [1,2,3]
- Output:
- 0
- Explanation:
Every subarray sorts into consecutive integers, so no imbalance anywhere.
Example 3
- Input:
- nums = [1,3,1,3]
- Output:
- 6
- Explanation:
Every subarray containing both a 1 and a 3 has exactly one gap of 2, and there are 6 such subarrays.
Constraints
- 1 ≤ nums.length ≤ 105
- 1 ≤ nums[i] ≤ 109
- The answer fits in a signed 32-bit integer.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 600 msC++ 150 msJava 300 msJavaScript 300 msTypeScript 300 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)