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

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

✓ Brute Force

⏱️ Time: O(n³ log n) Space: O(n)

For each possible subarray, sort it and count the number of gaps where consecutive elements differ by more than 1. This straightforward approach examines every subarray independently.

Optimized with Set Tracking

⏱️ Time: O(n³ log n) Space: O(n)

Instead of sorting each subarray from scratch, we incrementally build each subarray and use a set to track unique elements. For each subarray, we convert the set to a sorted list and count gaps.

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

Sum of Imbalance Numbers of All Subarrays - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler