Scale Engineer

Sum of Imbalance Numbers of All Subarrays

Hard
#2480Time: O(n³ log n). There are O(n²) subarrays. For each subarray of length up to n, we spend O(n log n) to sort it. This results in a cubic time complexity, which is too slow for n=1000.Space: O(n), for storing the temporary subarray.
Data structures
ArrayHash TableOrdered Set

Prompt

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.

A subarray is a contiguous non-empty sequence of elements within an array.

 

Example 1:

Input: nums = [2,3,1,4]
Output: 3
Explanation: There are 3 subarrays with non-zero imbalance numbers:
- Subarray [3, 1] with an imbalance number of 1.
- Subarray [3, 1, 4] with an imbalance number of 1.
- Subarray [1, 4] with an imbalance number of 1.
The imbalance number of all other subarrays is 0. Hence, the sum of imbalance numbers of all the subarrays of nums is 3.

Example 2:

Input: nums = [1,3,3,3,5]
Output: 8
Explanation: There are 7 subarrays with non-zero imbalance numbers:
- Subarray [1, 3] with an imbalance number of 1.
- Subarray [1, 3, 3] with an imbalance number of 1.
- Subarray [1, 3, 3, 3] with an imbalance number of 1.
- Subarray [1, 3, 3, 3, 5] with an imbalance number of 2. 
- Subarray [3, 3, 3, 5] with an imbalance number of 1. 
- Subarray [3, 3, 5] with an imbalance number of 1.
- Subarray [3, 5] with an imbalance number of 1.
The imbalance number of all other subarrays is 0. Hence, the sum of imbalance numbers of all the subarrays of nums is 8.

 

Constraints:

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= nums.length

Approaches

4 approaches with complexity analysis and trade-offs.

The most straightforward approach is to simulate the process directly. We can generate every single subarray of the input array nums. For each of these subarrays, we calculate its imbalance number as defined in the problem statement and add it to a running total. The imbalance number calculation involves sorting the subarray and then counting the gaps greater than 1 between adjacent elements.

Algorithm

  1. Initialize a variable totalImbalance to 0.
  2. Generate all possible subarrays of nums. This can be done using two nested loops, with the outer loop for the starting index i and the inner loop for the ending index j.
  3. For each subarray nums[i...j]: a. Create a temporary copy of the subarray. b. Sort the temporary copy. Let's call it sarr. c. Calculate the imbalance number for sarr. Iterate from the first element to the second-to-last element of sarr and increment a counter if sarr[k+1] - sarr[k] > 1. d. Add this imbalance number to totalImbalance.
  4. After iterating through all subarrays, return totalImbalance.

Walkthrough

This method iterates through all possible start and end points to define a subarray. For each subarray, a new list is created, sorted, and then scanned to find its imbalance number. The sum of these imbalance numbers over all subarrays gives the final answer.

For example, with nums = [2,3,1,4], we would first consider the subarray [2]. Sorted, it's [2]. Imbalance is 0. Then [2,3]. Sorted, it's [2,3]. Imbalance is 0. Then [2,3,1]. Sorted, it's [1,2,3]. Imbalance is 0. This process continues for all n*(n+1)/2 subarrays.

import java.util.ArrayList;import java.util.Collections;import java.util.List; class Solution {    public int sumImbalanceNumbers(int[] nums) {        int n = nums.length;        int totalImbalance = 0;         for (int i = 0; i < n; i++) {            for (int j = i; j < n; j++) {                // Create the subarray                List<Integer> sub = new ArrayList<>();                for (int k = i; k <= j; k++) {                    sub.add(nums[k]);                }                 // Calculate imbalance for the subarray                if (sub.size() <= 1) {                    continue;                }                 Collections.sort(sub);                 int currentImbalance = 0;                for (int k = 0; k < sub.size() - 1; k++) {                    if (sub.get(k + 1) - sub.get(k) > 1) {                        currentImbalance++;                    }                }                totalImbalance += currentImbalance;            }        }        return totalImbalance;    }}

Complexity

Time

O(n³ log n). There are O(n²) subarrays. For each subarray of length up to n, we spend O(n log n) to sort it. This results in a cubic time complexity, which is too slow for n=1000.

Space

O(n), for storing the temporary subarray.

Trade-offs

Pros

  • Simple to understand and implement.

  • Directly follows the problem definition.

Cons

  • Extremely inefficient and will time out for the given constraints.

  • Repeatedly sorts subarrays, which involves a lot of redundant computation.

Solutions

class Solution {public  int sumImbalanceNumbers(int[] nums) {    int n = nums.length;    int ans = 0;    for (int i = 0; i < n; ++i) {      TreeMap<Integer, Integer> tm = new TreeMap<>();      int cnt = 0;      for (int j = i; j < n; ++j) {        Integer k = tm.ceilingKey(nums[j]);        if (k != null && k - nums[j] > 1) {          ++cnt;        }        Integer h = tm.floorKey(nums[j]);        if (h != null && nums[j] - h > 1) {          ++cnt;        }        if (h != null && k != null && k - h > 1) {          --cnt;        }        tm.merge(nums[j], 1, Integer : : sum);        ans += cnt;      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem