#2763

Hard

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Sum of Imbalance Numbers of All Subarrays

Learn how to compute the total imbalance across all subarrays by updating gap counts as each subarray expands.

Problem Statement

You are given an integer array nums. For any subarray, sort its values and count how many adjacent pairs in that sorted order differ by more than 1. That count is the subarray's imbalance number.

Return the sum of those imbalance numbers over every contiguous subarray of nums. In the sample nums = [2,3,1,4], the answer is 3 because only subarrays such as [3,1], [3,1,4], and [1,4] create a missing-value gap after sorting.

Examples

Example 1

Input: nums = [2,3,1,4]

Output: 3

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

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

Solution Approach

Start every subarray from the left

Fix a left endpoint i, mark nums[i] as seen, and extend the right endpoint j one step at a time. This nested scan matches the constraint size well enough, but only if each extension updates the imbalance directly instead of rebuilding sorted order.

Update the imbalance from local neighbors only

When a new value x enters the current subarray, check whether x-1 and x+1 have already appeared. If neither neighbor exists, x creates one new separated block, so the imbalance increases by 1. If both neighbors exist, x merges two blocks and removes one previous gap, so the imbalance decreases by 1. If exactly one neighbor exists, the number of gaps does not change. Duplicate values also do not change the imbalance because they add no new sorted gap.

Accumulate the running imbalance

Keep a running imbalance for the current left endpoint and add it to the final answer after every right-end extension. For nums = [2,3,1,4], this explains why adding 1 after [2,3] creates a gap around the missing 2-to-3 continuity in sorted order, and why later adding 4 only affects whether that new value connects to an existing neighbor. The result is an O(n^2) scan with O(n) extra memory for the seen structure.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

With a fresh scan from each left endpoint and O(1) expected hash lookups for x-1 and x+1, the total time is O(n^2). The extra space is O(n) for the seen array or hash set used while expanding one left-started subarray.

What Interviewers Usually Probe

They want you to avoid sorting every subarray and instead update the imbalance as the window grows.
They expect you to notice that only x-1 and x+1 affect whether a newly added value creates or closes a gap.
They may ask why duplicates do not change the imbalance, which tests whether you understand sorted adjacency in this exact problem.

Common Pitfalls or Variants

Common pitfalls

Incrementing the imbalance for every unseen value is wrong because inserting x between two existing neighbors should decrease the gap count.
Forgetting duplicate handling breaks cases like [1,3,3,3,5], where repeated 3 values should not keep adding imbalance.
Recomputing sorted subarrays each time usually leads to an unnecessary O(n^3 log n) style solution that misses the intended local-update pattern.

Follow-up variants

Replace the hash set with a boolean array because nums[i] is bounded by nums.length, which often simplifies the implementation.
Derive a contribution-based formula that counts how often each value starts a new gap, then subtract overcounted neighbor connections.
Use an ordered set or balanced structure for a more general version where values are not tightly bounded, though it is heavier than needed here.

FAQ

What is the main idea for Sum of Imbalance Numbers of All Subarrays?

Fix a left index, extend the right index, and maintain the current imbalance with neighbor checks around the new value. The whole trick is that only x-1 and x+1 can change the sorted-gap count when x is added.

Why does checking only x-1 and x+1 work?

Imbalance counts adjacent gaps in sorted order. When x is inserted, only the numbers immediately next to x in value can create a new separated block or merge two existing blocks, so distant values never change that local effect.

Why do duplicates not increase the imbalance?

A duplicate does not introduce a new value position in sorted order, so it cannot create a new adjacent difference greater than 1. In this problem, duplicates should leave the running imbalance unchanged.

Is an ordered set required for this problem?

Not for the given constraints. Since nums[i] is between 1 and nums.length, a hash set or boolean seen array is enough to support the neighbor checks that drive the O(n^2) solution.

What is the usual wrong approach for this exact pattern?

The common miss is to sort every subarray and count gaps from scratch. That ignores the incremental structure of the problem and turns a local-update task into a much slower repeated-sorting solution.

terminal

Solution

Solution 1: Enumeration + Ordered Set

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.

class Solution:
    def sumImbalanceNumbers(self, nums: List[int]) -> int:
        n = len(nums)
        ans = 0
        for i in range(n):
            sl = SortedList()
            cnt = 0
            for j in range(i, n):
                k = sl.bisect_left(nums[j])
                h = k - 1
                if h >= 0 and nums[j] - sl[h] > 1:
                    cnt += 1
                if k < len(sl) and sl[k] - nums[j] > 1:
                    cnt += 1
                if h >= 0 and k < len(sl) and sl[k] - sl[h] > 1:
                    cnt -= 1
                sl.add(nums[j])
                ans += cnt
        return ans

Continue Practicing

#2713 maximum strictly increasing cells in a matrix #3092 most frequent ids #2363 merge similar items