2849. Sum of Imbalance Numbers of All Subarrays
My accepted Python solution to LeetCode problem 2849, Sum of Imbalance Numbers of All Subarrays, running in 249ms.
- Difficulty: Hard
- Python
- Runtime 249ms
- Memory 17.7MB
- Updated
Read the problem on LeetCode View on GitHub
The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.
Python
Accepted on LeetCode — runtime 249ms, memory 17.7MB, accepted 2026-01-01.
class Solution:
def sumImbalanceNumbers(self, nums: List[int]) -> int:
n = len(nums)
result = 0
for i in range(n):
seen = set()
imbalance = 0
for j in range(i, n):
num = nums[j]
# Calculate change in imbalance when adding nums[j]
if num in seen:
pass # No change
else:
# Check neighbors
has_prev = (num - 1) in seen
has_next = (num + 1) in seen
if has_prev and has_next:
# Merges two groups, reduces imbalance by 1
imbalance -= 1
elif not has_prev and not has_next:
# Creates new group
if seen: # Not the first element
imbalance += 1
# If has_prev XOR has_next, imbalance stays same
seen.add(num)
result += imbalance
return result