Package g2701_2800.s2763_sum_of_imbalance_numbers_of_all_subarrays

Class Solution

java.lang.Object
g2701_2800.s2763_sum_of_imbalance_numbers_of_all_subarrays.Solution
public class Solution extends Object
2763 - Sum of Imbalance Numbers of All Subarrays.<p>Hard</p> <p>The <strong>imbalance number</strong> of a <strong>0-indexed</strong> integer array <code>arr</code> of length <code>n</code> is defined as the number of indices in <code>sarr = sorted(arr)</code> such that:</p> <ul> <li><code>0 <= i < n - 1</code>, and</li> <li><code>sarr[i+1] - sarr[i] > 1</code></li> </ul> <p>Here, <code>sorted(arr)</code> is the function that returns the sorted version of <code>arr</code>.</p> <p>Given a <strong>0-indexed</strong> integer array <code>nums</code>, return <em>the <strong>sum of imbalance numbers</strong> of all its <strong>subarrays</strong></em>.</p> <p>A <strong>subarray</strong> is a contiguous <strong>non-empty</strong> sequence of elements within an array.</p> <p><strong>Example 1:</strong></p> <p><strong>Input:</strong> nums = [2,3,1,4]</p> <p><strong>Output:</strong> 3</p> <p><strong>Explanation:</strong> There are 3 subarrays with non-zero imbalance numbers:</p> <ul> <li>Subarray [3, 1] with an imbalance number of 1.</li> <li>Subarray [3, 1, 4] with an imbalance number of 1.</li> <li>Subarray [1, 4] with an imbalance number of 1.</li> </ul> <p>The imbalance number of all other subarrays is 0. Hence, the sum of imbalance numbers of all the subarrays of nums is 3.</p> <p><strong>Example 2:</strong></p> <p><strong>Input:</strong> nums = [1,3,3,3,5]</p> <p><strong>Output:</strong> 8</p> <p><strong>Explanation:</strong> There are 7 subarrays with non-zero imbalance numbers:</p> <ul> <li>Subarray [1, 3] with an imbalance number of 1.</li> <li>Subarray [1, 3, 3] with an imbalance number of 1.</li> <li>Subarray [1, 3, 3, 3] with an imbalance number of 1.</li> <li>Subarray [1, 3, 3, 3, 5] with an imbalance number of 2.</li> <li>Subarray [3, 3, 3, 5] with an imbalance number of 1.</li> <li>Subarray [3, 3, 5] with an imbalance number of 1.</li> <li>Subarray [3, 5] with an imbalance number of 1.</li> </ul> <p>The imbalance number of all other subarrays is 0. Hence, the sum of imbalance numbers of all the subarrays of nums is 8.</p> <p><strong>Constraints:</strong></p> <ul> <li><code>1 <= nums.length <= 1000</code></li> <li><code>1 <= nums[i] <= nums.length</code></li> </ul>

  • Constructor Details

    • Solution

      public Solution()

  • Method Details

    • sumImbalanceNumbers

      public int sumImbalanceNumbers(int[] nums)