Watch 9 video solutions for Intervals Between Identical Elements, a medium level problem involving Array, Hash Table, Prefix Sum. This walkthrough by Coding Decoded has 1,755 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |