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.
Example 1:
Input: arr = [2,1,3,1,2,3,3] Output: [4,2,7,2,4,4,5] Explanation: - Index 0: Another 2 is found at index 4. |0 - 4| = 4 - Index 1: Another 1 is found at index 3. |1 - 3| = 2 - Index 2: Two more 3s are found at indices 5 and 6. |2 - 5| + |2 - 6| = 7 - Index 3: Another 1 is found at index 1. |3 - 1| = 2 - Index 4: Another 2 is found at index 0. |4 - 0| = 4 - Index 5: Two more 3s are found at indices 2 and 6. |5 - 2| + |5 - 6| = 4 - Index 6: Two more 3s are found at indices 2 and 5. |6 - 2| + |6 - 5| = 5
Example 2:
Input: arr = [10,5,10,10] Output: [5,0,3,4] Explanation: - Index 0: Two more 10s are found at indices 2 and 3. |0 - 2| + |0 - 3| = 5 - Index 1: There is only one 5 in the array, so its sum of intervals to identical elements is 0. - Index 2: Two more 10s are found at indices 0 and 3. |2 - 0| + |2 - 3| = 3 - Index 3: Two more 10s are found at indices 0 and 2. |3 - 0| + |3 - 2| = 4
Constraints:
n == arr.length1 <= n <= 1051 <= arr[i] <= 105
Note: This question is the same as 2615: Sum of Distances.
Problem Overview: Given an integer array arr, compute an output array where result[i] equals the sum of distances between index i and every other index j where arr[i] == arr[j]. Distance is the absolute difference |i - j|. The challenge is avoiding repeated work when the same value appears many times.
Approach 1: Naive Pair Comparison (O(n²) time, O(1) extra space)
Check every pair of indices using two nested loops. For each index i, iterate through the entire array and add |i - j| whenever arr[i] == arr[j]. This brute‑force method directly follows the definition of the problem and requires no additional data structures beyond the output array. However, it performs n × n comparisons, which becomes slow when the array grows large. This version is useful for verifying correctness or understanding the distance calculation before optimizing.
Approach 2: HashMap + Prefix Sum Optimization (O(n) time, O(n) space)
The key observation: identical values can be processed together instead of recomputing distances repeatedly. First, group indices by value using a hash table. For each unique number, you get a sorted list of positions where it appears. Distances from a position depend on how many identical elements are on the left and right.
Traverse the index list while maintaining running prefix sums. Suppose the current index in the group is pos[k]. The contribution from elements on the left equals k * pos[k] - prefixSumLeft. The contribution from elements on the right equals prefixSumRight - (m - k - 1) * pos[k], where m is the number of occurrences. These formulas compute total distances using arithmetic rather than iterating over neighbors.
Using this technique turns repeated distance calculations into simple constant‑time updates. Each index participates in exactly one group traversal, producing linear complexity. The method combines array traversal, hash map grouping, and prefix sum accumulation to eliminate redundant work.
Recommended for interviews: Interviewers typically expect the HashMap + prefix sum approach. The brute force version shows you understand the definition of the distance calculation, but it does not scale. The optimized solution demonstrates the ability to group data, reuse prefix sums, and reduce quadratic work to linear time.
This approach involves iterating through the array and for each element, calculating the sum of intervals by iterating again to find all identical elements. This yields an O(n^2) time complexity, which is inefficient for larger inputs.
In this C program, we initialize an intervals array and iterate over each element. For each element, we run another loop to check for identical elements and calculate the intervals sum, adding it to the intervals array. Finally, we print and free the intervals array.
Time Complexity: O(n^2), where n is the length of the array.
Space Complexity: O(n) for the intervals array.
To enhance efficiency, use a HashMap to map each unique value in the array to its indices. Then, for each unique value, calculate interval sums in a linear pass.
This C implementation utilizes an integer-array based hash mapping to track indices of each element value efficiently. Then, iteratively calculates interval sums using these indexed locations.
Time Complexity: O(n), assuming amortized operations on reallocations are balanced.
Space Complexity: O(n) for storing indices in dynamic arrays.
| Approach | Complexity |
|---|---|
| Naive Approach | Time Complexity: O(n^2), where n is the length of the array. |
| Efficient Approach Using HashMap | Time Complexity: O(n), assuming amortized operations on reallocations are balanced. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Pair Comparison | O(n²) | O(1) | Useful for understanding the distance definition or verifying small inputs |
| HashMap + Prefix Sum | O(n) | O(n) | Best general solution when the array can contain many repeated values |
Intervals Between Identical Elements | Leetcode 2121 | Contest 273 | Tricky Linear 🔥🔥🔥🔥 • Coding Decoded • 1,755 views views
Watch 8 more video solutions →Practice Intervals Between Identical Elements with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor