Sum of Imbalance Numbers of All Subarrays

Sum of Imbalance Numbers of All Subarrays - Problem

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, and
sarr[i+1] - sarr[i] > 1

Here, 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.

Input & Output

Example 1 — Basic Case

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

› Output: 1

💡 Note: Subarrays: [2]→0, [2,3]→0, [2,3,1]→0, [3]→0, [3,1]→1, [1]→0. Only [3,1] sorted as [1,3] has gap 3-1=2>1, so total is 1.

Example 2 — No Imbalances

$ Input: nums = [1,3,3,3,5]

› Output: 8

💡 Note: Multiple subarrays have gaps. For example [1,3] has gap 2, [3,5] has gap 2, [1,3,5] has 2 gaps, etc.

Example 3 — Single Element

$ Input: nums = [1]

› Output: 0

💡 Note: Only one subarray [1] with no gaps possible in single element arrays.

Constraints

1 ≤ nums.length ≤ 1000
1 ≤ nums[i] ≤ nums.length

Visualization

Tap to expand

Understanding the Visualization

Input

Array [2,3,1] with all possible subarrays

Process

Sort each subarray and count gaps > 1

Output

Sum of all imbalance numbers

Key Takeaway

🎯 Key Insight: Count gaps > 1 in sorted subarrays and sum across all subarrays

Asked in

G Google 15 M Microsoft 12

The key insight is to understand that imbalance measures gaps in sorted unique elements. The brute force approach generates all subarrays and sorts each one. The optimized approach uses incremental set building to avoid redundant work. Best time complexity is O(n³ log n), space O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n³ log n)	O(n)	Generate all subarrays, sort each one, count gaps
Optimized with Set Tracking	O(n³ log n)	O(n)	Track unique elements incrementally to avoid full sorting

Brute Force — Algorithm Steps

Generate all possible subarrays
Sort each subarray
Count gaps in sorted subarray
Sum all imbalance numbers

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Subarrays

Create all possible contiguous subarrays

Sort Each

Sort each subarray to find gaps

Count Gaps

Count differences > 1 between consecutive elements

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int solution(int* nums, int numsSize) {
    int totalImbalance = 0;
    
    // Generate all subarrays
    for (int i = 0; i < numsSize; i++) {
        for (int j = i; j < numsSize; j++) {
            // Extract subarray
            int subarraySize = j - i + 1;
            int* subarray = (int*)malloc(subarraySize * sizeof(int));
            for (int k = 0; k < subarraySize; k++) {
                subarray[k] = nums[i + k];
            }
            
            // Sort the subarray
            qsort(subarray, subarraySize, sizeof(int), compare);
            
            // Count imbalances (gaps > 1)
            int imbalance = 0;
            for (int k = 0; k < subarraySize - 1; k++) {
                if (subarray[k + 1] - subarray[k] > 1) {
                    imbalance++;
                }
            }
            
            totalImbalance += imbalance;
            free(subarray);
        }
    }
    
    return totalImbalance;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Parse JSON array
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]"); // Skip opening bracket
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, numsSize);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³ log n)

O(n²) subarrays, each taking O(n log n) to sort

⚠ Quadratic Growth

Space Complexity

O(n)

Extra space for sorting each subarray

⚡ Linearithmic Space

8.9K Views

Medium Frequency

~25 min Avg. Time

234 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler