Intervals Between Identical Elements - Practice Coding Problems

Intervals Between Identical Elements - Problem

You are given a 0-indexed array of n integers arr.

The interval between two elements in arr is defined as the absolute difference between their indices. More formally, the interval between arr[i] and arr[j] is |i - j|.

Return an array intervals of length n where intervals[i] is the sum of intervals between arr[i] and each element in arr with the same value as arr[i].

Note: |x| is the absolute value of x.

Input & Output

Example 1 — Basic Array

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

› Output: [4,2,7,2,4,4,5]

💡 Note: For arr[0]=2: same values at indices 0,4 → distances |0-0|+|0-4| = 0+4 = 4. For arr[1]=1: same values at indices 1,3 → distances |1-1|+|1-3| = 0+2 = 2. For arr[2]=3: same values at indices 2,5,6 → distances |2-2|+|2-5|+|2-6| = 0+3+4 = 7.

Example 2 — All Same Values

$ Input: arr = [10,10,10]

› Output: [3,2,3]

💡 Note: For arr[0]=10: distances to indices 0,1,2 → |0-0|+|0-1|+|0-2| = 0+1+2 = 3. For arr[1]=10: distances to indices 0,1,2 → |1-0|+|1-1|+|1-2| = 1+0+1 = 2. For arr[2]=10: distances to indices 0,1,2 → |2-0|+|2-1|+|2-2| = 2+1+0 = 3.

Example 3 — All Different Values

$ Input: arr = [1,2,3,4]

› Output: [0,0,0,0]

💡 Note: Each element is unique, so each only matches with itself at distance 0. All intervals are 0.

Constraints

n == arr.length
1 ≤ n ≤ 10⁵
1 ≤ arr[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array with potentially duplicate values at different indices

Find Matches

For each element, find all positions with same value

Calculate Distances

Sum up absolute differences between current index and all matching indices

Key Takeaway

🎯 Key Insight: Use prefix sums to calculate all distances mathematically instead of nested loops for O(n) solution

Asked in

F Facebook 12 a Amazon 8 G Google 6

The key insight is using prefix sums to calculate distances mathematically instead of nested loops. For each group of identical elements, we can compute the sum of distances from any position to all other positions in the group using the formula: left_distance + right_distance, where each side is calculated using prefix sums. Best approach is prefix sum optimization with Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n²)	O(1)	For each element, scan entire array to find matching values and sum distances
Prefix Sum Optimization	O(n)	O(n)	Use mathematical properties and prefix sums to calculate all distances efficiently
Hash Map Grouping	O(n²)	O(n)	Group indices by value, then calculate distances within each group

Brute Force — Algorithm Steps

For each element at index i
Scan entire array for elements with same value
Calculate absolute difference |i - j| for each match
Sum all distances for this element

Visualization

Tap to expand

Step-by-Step Walkthrough

Select Element

Pick element at index i

Compare All

Check every other element for same value

Sum Distances

Add up |i-j| for all matches

Code -

solution.c — C

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

long long* solution(int* arr, int n) {
    long long* intervals = (long long*)calloc(n, sizeof(long long));
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (arr[i] == arr[j]) {
                intervals[i] += abs(i - j);
            }
        }
    }
    
    return intervals;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Parse array
    int arr[1000];
    int n = 0;
    char* token = strtok(line + 1, ",]"); // Skip opening bracket
    while (token != NULL) {
        arr[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    long long* result = solution(arr, n);
    
    printf("[");
    for (int i = 0; i < n; i++) {
        printf("%lld", result[i]);
        if (i < n - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Nested loops: outer loop n times, inner loop n times for each outer iteration

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables for indices and sum, no extra data structures

✓ Linear Space

28.4K Views

Medium Frequency

~25 min Avg. Time

892 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