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.
This approach involves iterating through all possible subarrays of the given array, sorting each subarray, and calculating the imbalance number.
For each subarray, sort it, and then count the pairs of elements such that the difference between them is greater than 1. Sum these counts for all subarrays to get the total imbalance number.
The C solution iterates over all subarrays, sorts them using qsort, and counts pairs where the difference is greater than 1. It uses dynamic memory allocation for each subarray.
Time Complexity: O(N^3 log N) because we have O(N^2) subarrays and sorting each one takes O(N log N).
Space Complexity: O(N) due to auxiliary space used for sorting each subarray.
The optimized approach avoids recalculating imbalance for overlapping parts of subarrays. We adjust the imbalance by adding or removing elements dynamically from a running subarray.
To achieve this, rely on maintaining counts of each element, assisting in quickly determining when the imbalance conditions are met as the subarray boundaries shift.
This C implementation uses a frequency counter for the fast adjustment of the imbalance. As each new element is added to the subarray, it checks neighboring values and updates the count of the imbalance accordingly.
Time Complexity: O(N^2) as each subarray is only processed in linear time.
Space Complexity: O(M) where M is the max value in nums to maintain frequency counts.
We can first enumerate the left endpoint i of the subarray. For each i, we enumerate the right endpoint j of the subarray from small to large, and maintain all the elements in the current subarray with an ordered list. We also use a variable cnt to maintain the unbalanced number of the current subarray.
For each number nums[j], we find the first element nums[k] in the ordered list that is greater than or equal to nums[j], and the last element nums[h] that is less than nums[j]:
nums[k] exists, and the difference between nums[k] and nums[j] is more than 1, the unbalanced number increases by 1;nums[h] exists, and the difference between nums[j] and nums[h] is more than 1, the unbalanced number increases by 1;nums[k] and nums[h] exist, then inserting the element nums[j] between nums[h] and nums[k] will reduce the unbalanced number by 1.Then, we add the unbalanced number of the current subarray to the answer, and continue the iteration until we finish iterating over all subarrays.
The time complexity is O(n^2 times log n) and the space complexity is O(n), where n is the length of the array nums.
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(N^3 log N) because we have O(N^2) subarrays and sorting each one takes O(N log N). Space Complexity: O(N) due to auxiliary space used for sorting each subarray. |
| Optimized Approach with Dynamic Adjustment | Time Complexity: O(N^2) as each subarray is only processed in linear time. Space Complexity: O(M) where M is the max value in nums to maintain frequency counts. |
| Enumeration + Ordered Set | — |
| 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 |
2 Approaches | 2763. Sum of Imbalance Numbers of All Subarrays | Leetcode Weekly Contest 352 • codingMohan • 1,227 views views
Watch 8 more video solutions →Practice Sum of Imbalance Numbers of All Subarrays with our built-in code editor and test cases.
Practice on FleetCode