LeetCode 2763 - Sum of Imbalance Numbers of All Subarrays

For any array, its imbalance number is determined after sorting the elements. Suppose we have a subarray and sort it into sarr. We examine every adjacent pair in the sorted order.

leetcodehardarrayhash-tableenumeration

LeetCode Problem 2763

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Enumeration

Solution

LeetCode 2763 - Sum of Imbalance Numbers of All Subarrays

Problem Understanding

For any array, its imbalance number is determined after sorting the elements.

Suppose we have a subarray and sort it into sarr. We examine every adjacent pair in the sorted order. Whenever the difference between consecutive values is greater than 1, that pair contributes one imbalance.

For example:

arr = [3,1,4]
sorted(arr) = [1,3,4]

3 - 1 = 2 > 1  -> contributes 1
4 - 3 = 1      -> contributes 0

imbalance = 1

The problem asks us to compute the imbalance number for every non-empty subarray of nums, then return the sum of all those imbalance values.

The constraints are:

1 <= n <= 1000
1 <= nums[i] <= n

The array length is at most 1000, which is too large for approaches that recompute sorting for every subarray. Since there are already O(n²) subarrays, anything close to O(n³) or O(n² log n) per subarray is far too slow.

An important observation is that values are bounded:

nums[i] <= n <= 1000

This allows us to maintain presence information efficiently while extending subarrays.

Important edge cases include:

  • Arrays of length 1, where every subarray has imbalance 0.
  • Arrays containing many duplicates, since duplicates do not create new gaps.
  • Arrays where values differ by more than one, creating multiple imbalance contributions.
  • Arrays that become balanced when a missing middle value is inserted later.

Approaches

Brute Force

The most direct solution is to enumerate every subarray.

For each subarray:

  1. Copy its elements.
  2. Sort them.
  3. Count adjacent sorted pairs whose difference exceeds 1.
  4. Add the count to the answer.

This is correct because it follows the problem definition exactly.

However, there are O(n²) subarrays. Sorting a subarray of length k costs O(k log k). Summing this across all subarrays leads to roughly O(n³ log n) time, which is far too slow for n = 1000.

Key Insight

Instead of recomputing the imbalance from scratch for every subarray, consider fixing a left endpoint i and extending the right endpoint j.

As we insert one new value into the current subarray, only the relationships involving that value can change the imbalance.

Suppose the current set of values already contains:

x-1
x
x+1

When inserting x, the imbalance changes according to nearby values:

  • If neither x-1 nor x+1 exists, a new gap appears, so imbalance increases by 1.
  • If both neighbors exist, inserting x bridges an existing gap, so imbalance decreases by 1.
  • If exactly one neighbor exists, imbalance does not change.
  • If x already exists, nothing changes because duplicates do not affect the sorted distinct structure.

This allows us to update the imbalance in O(1) time while extending a subarray.

Since we enumerate all O(n²) subarrays and each extension costs constant time, the total complexity becomes O(n²).

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n³ log n) O(n) Sort every subarray independently
Optimal O(n²) O(n) Incrementally maintain imbalance while extending subarrays

Algorithm Walkthrough

  1. Initialize the final answer to 0.
  2. Iterate over every possible left endpoint i.
  3. For each i, create a boolean presence array that records which values have appeared in the current subarray.
  4. Set the current imbalance value to 0.
  5. Mark nums[i] as present. A single-element subarray always has imbalance 0.
  6. Extend the right endpoint j from i + 1 to n - 1.
  7. Let the new value be x = nums[j].
  8. If x has not appeared before in the current subarray:
  • Check whether x - 1 is present.
  • Check whether x + 1 is present.
  • If neither neighbor exists, increase imbalance by 1.
  • If both neighbors exist, decrease imbalance by 1.
  • If exactly one neighbor exists, leave imbalance unchanged.
  • Mark x as present.
  1. Add the current imbalance value to the global answer.
  2. Continue extending the subarray until all right endpoints have been processed.
  3. Return the accumulated answer.

Why it works

The imbalance number depends only on gaps between consecutive distinct values in sorted order. When a new value x is inserted, the only affected gaps are those adjacent to x.

If neither neighbor exists, x introduces a new isolated value and creates one additional gap. If both neighbors exist, x fills a previously existing gap and removes one imbalance contribution. If exactly one neighbor exists, the number of gaps remains unchanged.

Since every extension updates the imbalance exactly according to the change in gap count, the maintained value always equals the true imbalance of the current subarray.

Python Solution

from typing import List

class Solution:
    def sumImbalanceNumbers(self, nums: List[int]) -> int:
        n = len(nums)
        answer = 0

        for left in range(n):
            seen = [False] * (n + 2)
            seen[nums[left]] = True

            imbalance = 0

            for right in range(left + 1, n):
                value = nums[right]

                if not seen[value]:
                    left_neighbor = seen[value - 1] if value > 1 else False
                    right_neighbor = seen[value + 1]

                    if not left_neighbor and not right_neighbor:
                        imbalance += 1
                    elif left_neighbor and right_neighbor:
                        imbalance -= 1

                    seen[value] = True

                answer += imbalance

        return answer

Implementation Explanation

The outer loop fixes the left boundary of the subarray.

For each left boundary, we maintain a seen array that tracks which values currently appear in the growing subarray. Because the problem guarantees:

nums[i] <= n

an array of size n + 2 is sufficient to safely access value + 1.

The variable imbalance stores the imbalance number of the current subarray.

Whenever a new element is added, we first check whether it already exists. Duplicates do not affect the imbalance, so no update is needed.

For a new distinct value, we inspect whether value - 1 and value + 1 already exist. Based on those two neighbors, we update the imbalance according to the gap-creation and gap-removal rules.

After processing the new element, the current imbalance corresponds exactly to the subarray ending at right, so we add it to the answer.

Go Solution

func sumImbalanceNumbers(nums []int) int {
	n := len(nums)
	answer := 0

	for left := 0; left < n; left++ {
		seen := make([]bool, n+2)
		seen[nums[left]] = true

		imbalance := 0

		for right := left + 1; right < n; right++ {
			value := nums[right]

			if !seen[value] {
				leftNeighbor := false
				if value > 1 {
					leftNeighbor = seen[value-1]
				}

				rightNeighbor := seen[value+1]

				if !leftNeighbor && !rightNeighbor {
					imbalance++
				} else if leftNeighbor && rightNeighbor {
					imbalance--
				}

				seen[value] = true
			}

			answer += imbalance
		}
	}

	return answer
}

Go-Specific Notes

The Go implementation follows exactly the same logic as the Python version.

A boolean slice of length n + 2 is used for presence tracking. Since nums[i] <= n, accessing value + 1 is always safe. The result easily fits inside Go's int type because the maximum possible answer is well below 32-bit limits for n = 1000.

Worked Examples

Example 1

nums = [2,3,1,4]

Left = 0

Initial:

seen = {2}
imbalance = 0
Right Value Neighbor Status Imbalance Change Current Imbalance Answer Added
1 3 2 exists 0 0 0
2 1 2 exists 0 0 0
3 4 3 exists 0 0 0

Contribution:

0

Left = 1

Initial:

seen = {3}
imbalance = 0
Right Value Neighbor Status Imbalance Change Current Imbalance Answer Added
2 1 neither neighbor exists +1 1 1
3 4 neighbor 3 exists 0 1 1

Contribution:

2

Left = 2

Initial:

seen = {1}
imbalance = 0
Right Value Neighbor Status Imbalance Change Current Imbalance Answer Added
3 4 neither neighbor exists +1 1 1

Contribution:

1

Total:

0 + 2 + 1 = 3

Answer:

3

Example 2

nums = [1,3,3,3,5]

Left = 0

Right Value Imbalance
1 3 1
2 3 1
3 3 1
4 5 2

Contribution:

1 + 1 + 1 + 2 = 5

Left = 1

Right Value Imbalance
2 3 0
3 3 0
4 5 1

Contribution:

1

Left = 2

Right Value Imbalance
3 3 0
4 5 1

Contribution:

1

Left = 3

Right Value Imbalance
4 5 1

Contribution:

1

Total:

5 + 1 + 1 + 1 = 8

Answer:

8

Complexity Analysis

Measure Complexity Explanation
Time O(n²) Every subarray extension is processed once
Space O(n) Presence array for distinct values

The outer loop chooses a starting position, and the inner loop extends the ending position. Together they perform approximately n(n-1)/2 iterations, giving O(n²) time. The only auxiliary structure is the seen array of size O(n).

Test Cases

from typing import List

s = Solution()

assert s.sumImbalanceNumbers([2, 3, 1, 4]) == 3      # example 1
assert s.sumImbalanceNumbers([1, 3, 3, 3, 5]) == 8   # example 2

assert s.sumImbalanceNumbers([1]) == 0               # single element
assert s.sumImbalanceNumbers([1, 2]) == 0            # consecutive values
assert s.sumImbalanceNumbers([1, 3]) == 1            # one gap

assert s.sumImbalanceNumbers([2, 2]) == 0            # duplicates only
assert s.sumImbalanceNumbers([2, 2, 2]) == 0         # all duplicates

assert s.sumImbalanceNumbers([1, 3, 2]) == 1         # gap later filled
assert s.sumImbalanceNumbers([3, 1, 2]) == 1         # imbalance reduced by insertion

assert s.sumImbalanceNumbers([1, 4]) == 1            # large gap
assert s.sumImbalanceNumbers([1, 4, 7]) == 4         # multiple gaps

assert s.sumImbalanceNumbers([1, 2, 3, 4]) == 0      # already consecutive
assert s.sumImbalanceNumbers([4, 3, 2, 1]) == 0      # reverse consecutive

Test Summary

Test Why
[2,3,1,4] Official example 1
[1,3,3,3,5] Official example 2
[1] Minimum array size
[1,2] No gaps exist
[1,3] Single imbalance contribution
[2,2] Duplicate handling
[2,2,2] All values identical
[1,3,2] Gap gets filled later
[3,1,2] Imbalance decreases after insertion
[1,4] Large gap between values
[1,4,7] Multiple imbalance contributions
[1,2,3,4] Perfectly consecutive sequence
[4,3,2,1] Consecutive values in reverse order

Edge Cases

Single Element Arrays

When n = 1, there is only one subarray, namely the element itself. A single value has no adjacent pairs in sorted order, so its imbalance is always zero. The implementation naturally handles this because the inner loop never executes.

Duplicate Values

Duplicates can easily introduce bugs if they are treated as new distinct values. For example:

[3,3,3]

has imbalance 0 for every subarray. The algorithm explicitly checks if not seen[value] before updating the imbalance. Therefore duplicate insertions never create or remove gaps.

Gap Bridging

Consider:

[1,3,2]

The subarray [1,3] has imbalance 1 because there is a gap between 1 and 3. When 2 is inserted, that gap disappears.

The algorithm detects that both neighbors of 2 already exist, namely 1 and 3, and decreases the imbalance by 1. This correctly models the removal of the gap.

Values at the Boundaries

When processing value 1, there is no valid 0 neighbor. The implementation explicitly checks:

left_neighbor = seen[value - 1] if value > 1 else False

which avoids invalid indexing while preserving the correct logic. Similarly, the seen array is allocated with length n + 2, making access to value + 1 always safe.