Watch 9 video solutions for Sum of Imbalance Numbers of All Subarrays, a hard level problem involving Array, Hash Table, Ordered Set. This walkthrough by codingMohan has 1,227 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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, andsarr[i+1] - sarr[i] > 1Here, 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 <= 10001 <= nums[i] <= nums.lengthProblem Overview: Given an integer array, every subarray has an imbalance number defined as the count of gaps greater than 1 between adjacent elements after sorting that subarray. The task is to compute the total imbalance across all possible subarrays.
Approach 1: Brute Force with Ordered Set (O(n2 log n) time, O(n) space)
Enumerate every subarray by fixing a start index and expanding the end index. Maintain the elements of the current subarray inside an ordered structure such as a balanced tree or sorted container. Each insertion finds the predecessor and successor of the new value and checks whether a new gap is introduced or removed. The imbalance count is updated incrementally instead of recomputing the whole sorted array each time. Ordered lookups and insertions cost O(log n), giving an overall complexity of O(n^2 log n). This approach directly models the definition and is useful for understanding how gaps appear between consecutive values.
Key operations include ordered insertion, predecessor lookup, and successor lookup. Data structures commonly used are TreeSet, SortedList, or similar ordered containers from Ordered Set implementations.
Approach 2: Dynamic Imbalance Adjustment (O(n2) time, O(n) space)
The optimized approach avoids maintaining a fully ordered structure. For each starting index, expand the subarray to the right and track which values have appeared using a boolean array or hash structure. When inserting a new number x, check whether x-1 and x+1 already exist in the current subarray. If neither exists, a new gap is created so the imbalance increases by one. If both neighbors exist, two previous gaps merge into one so the imbalance decreases by one. Otherwise the imbalance remains unchanged.
This constant-time adjustment eliminates the log n overhead from ordered structures. The algorithm iterates over all starting indices and dynamically updates the imbalance while expanding the subarray, resulting in O(n^2) total work and O(n) auxiliary space. The method relies heavily on fast membership checks using Hash Table or boolean arrays and sequential scanning of the Array.
Recommended for interviews: Start by explaining the brute force enumeration with an ordered set to demonstrate understanding of the imbalance definition and how sorted neighbors determine gaps. Then move to the dynamic adjustment technique, which interviewers typically expect. It reduces the per‑insertion cost to constant time and shows strong reasoning about how local neighbor relationships affect the imbalance metric.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Ordered Set | O(n^2 log n) | O(n) | Good for understanding the imbalance definition and when using built‑in ordered containers |
| Dynamic Imbalance Adjustment | O(n^2) | O(n) | Preferred optimized solution for interviews and competitive programming |