# Intervals Between Identical Elements
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/intervals-between-identical-elements)
Canonical: https://scaleengineer.com/dsa/problems/intervals-between-identical-elements
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array, Hash Table
**Companies:** [TuSimple](https://scaleengineer.com/companies/tusimple)
---
## 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`.

**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.length`
* `1 <= n <= 105`
* `1 <= arr[i] <= 105`

**Note:** This question is the same as [ 2615: Sum of Distances.](https://leetcode.com/problems/sum-of-distances/description/)

# Approaches
## Brute Force
The brute-force approach is the most straightforward way to solve the problem. For each element in the array, we iterate through the entire array again to find all other elements with the same value. For each identical element found, we calculate the interval (the absolute difference of indices) and add it to a running total for the current element.
**Time:** O(N^2), where N is the number of elements in the array. The nested loops lead to a quadratic number of comparisons. · **Space:** O(N) or O(1). O(N) to store the output array `intervals`. If the output array is not considered, the space complexity is O(1).
**Pros:** Simple to understand and implement.; Requires minimal auxiliary space (besides the output array).
**Cons:** Extremely inefficient for large inputs due to its quadratic time complexity.; Will result in a 'Time Limit Exceeded' (TLE) error on most competitive programming platforms for the given constraints.
### Explanation
This method involves a nested loop structure. The outer loop selects an element `arr[i]`, and the inner loop iterates through all elements `arr[j]` to find matches. When a match is found (`arr[i] == arr[j]`), the distance `|i - j|` is computed and accumulated. This process is repeated for every element in the array.

```java
class Solution {
    public long[] getDistances(int[] arr) {
        int n = arr.length;
        long[] intervals = new long[n];
        for (int i = 0; i < n; i++) {
            long currentSum = 0;
            for (int j = 0; j < n; j++) {
                if (arr[i] == arr[j]) {
                    currentSum += Math.abs(i - j);
                }
            }
            intervals[i] = currentSum;
        }
        return intervals;
    }
}
```
### Algorithm
*   Initialize a result array `intervals` of size `n` with zeros.
*   Iterate through the input array `arr` with an outer loop from `i = 0` to `n-1`.
*   Inside the outer loop, start an inner loop from `j = 0` to `n-1`.
*   In the inner loop, check if `arr[i]` is equal to `arr[j]`.
*   If they are equal, calculate the absolute difference of their indices, `|i - j|`, and add it to a running sum for `intervals[i]`.
*   After the inner loop completes, `intervals[i]` will hold the total sum of intervals for the element at index `i`.
*   After the outer loop finishes, return the `intervals` array.

## Grouping Indices by Value
This approach improves upon the pure brute-force method by first grouping the indices of identical elements. Instead of scanning the entire array for each element, we only need to compare an element with others in its own value group. This can be significantly faster if the array contains many unique values with few occurrences each.
**Time:** O(N + Σ(k_v^2)), where N is for building the map and k_v is the number of occurrences of value v. In the worst case, where all elements are the same, k_v = N, leading to O(N^2) complexity. · **Space:** O(N), as the `HashMap` might need to store all N indices in the worst case (e.g., all elements are unique or all are the same).
**Pros:** More efficient than the pure brute-force approach on average, especially for arrays with high cardinality (many unique values).; Logically separates the problem by value, which can simplify reasoning.
**Cons:** The worst-case time complexity is still O(N^2), which occurs if all elements in the array are identical.; Can consume significant memory to store the lists of indices in the HashMap.
### Explanation
We use a `HashMap<Integer, List<Integer>>` to store the locations of each number. After populating this map, we iterate through each group of indices. For each index `i` within a group, we calculate the sum of distances to every other index `j` in that same group. While this avoids unnecessary comparisons with elements of different values, the complexity within a large group remains quadratic.

```java
import java.util.*;

class Solution {
    public long[] getDistances(int[] arr) {
        int n = arr.length;
        long[] intervals = new long[n];
        Map<Integer, List<Integer>> map = new HashMap<>();

        for (int i = 0; i < n; i++) {
            map.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);
        }

        for (List<Integer> indices : map.values()) {
            if (indices.size() <= 1) {
                continue;
            }
            for (int i : indices) {
                long currentSum = 0;
                for (int j : indices) {
                    currentSum += Math.abs(i - j);
                }
                intervals[i] = currentSum;
            }
        }
        return intervals;
    }
}
```
### Algorithm
*   Create a `HashMap` where keys are the numbers in `arr` and values are lists of indices where those numbers appear.
*   Iterate through the input array `arr` once to populate the `HashMap`. For each element `arr[i]`, add the index `i` to the list associated with the value `arr[i]`.
*   Initialize a result array `intervals` of size `n`.
*   Iterate through each list of indices in the `HashMap`'s values.
*   For each list, perform a brute-force calculation: for each index `i` in the list, iterate through all other indices `j` in the same list and sum up the absolute differences `|i - j|`.
*   Store the calculated sum in `intervals[i]`.
*   Return the `intervals` array.

## Grouping with Prefix Sums
This efficient approach builds upon the grouping strategy. Once we have the list of indices for a particular value, we can observe that the sum of intervals for an index `i` can be calculated quickly if we know the sum of indices to its left and to its right. By pre-calculating prefix sums for each list of indices, we can find these sums in O(1) time, leading to a linear time solution.
**Time:** O(N). Building the map takes O(N). Processing all groups involves iterating through each index once to build prefix sums and once more to calculate distances, resulting in a total time proportional to N. · **Space:** O(N). The HashMap can store up to N indices, and the prefix sum arrays can also take up to O(N) space in total.
**Pros:** Highly efficient with a linear time complexity, O(N).; Passes the given constraints easily.
**Cons:** Requires additional space for the HashMap and prefix sum arrays.; The logic is more complex compared to brute-force methods.
### Explanation
For a sorted list of indices `idx_0, idx_1, ..., idx_{k-1}`, the total interval for `idx_i` is `Σ|idx_i - idx_j|`. This can be split into `Σ(idx_i - idx_j)` for `j < i` and `Σ(idx_j - idx_i)` for `j > i`. These sums can be rewritten as `(i * idx_i - Σ_{j<i} idx_j)` and `(Σ_{j>i} idx_j - (k-1-i) * idx_i)`. By computing a prefix sum array on the list of indices, we can find `Σ_{j<i} idx_j` and `Σ_{j>i} idx_j` instantly, allowing us to calculate the interval for each index in O(1) time after an O(k) preprocessing step for the group.

```java
import java.util.*;

class Solution {
    public long[] getDistances(int[] arr) {
        int n = arr.length;
        long[] intervals = new long[n];
        Map<Integer, List<Integer>> map = new HashMap<>();

        for (int i = 0; i < n; i++) {
            map.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);
        }

        for (List<Integer> indices : map.values()) {
            int k = indices.size();
            if (k <= 1) continue;

            long[] prefixSum = new long[k + 1];
            for (int i = 0; i < k; i++) {
                prefixSum[i + 1] = prefixSum[i] + indices.get(i);
            }
            long totalSum = prefixSum[k];

            for (int i = 0; i < k; i++) {
                long currentIndex = indices.get(i);
                long leftCount = i;
                long rightCount = k - 1 - i;

                long leftSumOfIndices = prefixSum[i];
                long rightSumOfIndices = totalSum - prefixSum[i + 1];

                long leftDist = leftCount * currentIndex - leftSumOfIndices;
                long rightDist = rightSumOfIndices - rightCount * currentIndex;

                intervals[(int)currentIndex] = leftDist + rightDist;
            }
        }
        return intervals;
    }
}
```
### Algorithm
*   First, group indices by their corresponding values using a `HashMap<Integer, List<Integer>>`.
*   Iterate through each group (list of indices) in the map.
*   For each list of indices `idx` of size `k`, which is naturally sorted:
    *   Create a prefix sum array `prefix` of size `k+1`. `prefix[i]` will store the sum of the first `i` indices.
    *   Calculate the total sum of all indices in the list, `totalSum`.
    *   Iterate through the list of indices from `i = 0` to `k-1`. For the current index `currIdx = idx.get(i)`:
        *   The number of elements to the left is `leftCount = i`.
        *   The sum of indices to the left is `leftSum = prefix[i]`.
        *   The sum of distances to the left is `leftDist = leftCount * currIdx - leftSum`.
        *   The number of elements to the right is `rightCount = k - 1 - i`.
        *   The sum of indices to the right is `rightSum = totalSum - prefix[i+1]`.
        *   The sum of distances to the right is `rightDist = rightSum - rightCount * currIdx`.
        *   The total interval is `intervals[currIdx] = leftDist + rightDist`.
*   Return the `intervals` array.

## Two-Pass Calculation
This is a very elegant and efficient O(N) solution that avoids explicitly grouping indices. It calculates the total interval sum by breaking it down into two components: the sum of distances to identical elements on the left and the sum of distances to identical elements on the right. Each component is calculated in a separate pass over the array.
**Time:** O(N), as it consists of two linear passes through the array, with O(1) average time operations for the hashmap. · **Space:** O(U), where U is the number of unique elements in `arr`. This is for the hashmaps. In the worst case, U can be N, making the space complexity O(N).
**Pros:** Optimal linear time complexity O(N).; Conceptually clean and avoids creating intermediate lists of indices.; Generally efficient in practice due to sequential memory access.
**Cons:** Requires two separate passes over the array.; Uses hashmaps which can have a higher constant factor overhead compared to arrays.
### Explanation
The key insight is that for an index `i`, the total sum `Σ|i - j|` can be split. In a left-to-right pass, we can calculate `Σ(i - j)` for all `j < i` where `arr[j] == arr[i]`. This equals `(count_left * i) - (sum_of_left_indices)`. We can maintain the count and sum of indices for each value seen so far in a hash map. Similarly, a right-to-left pass can calculate `Σ(j - i)` for all `j > i`. The final answer for `intervals[i]` is the sum of the results from these two passes.

```java
import java.util.*;

class Solution {
    public long[] getDistances(int[] arr) {
        int n = arr.length;
        long[] intervals = new long[n];
        
        // Left to Right Pass
        Map<Integer, Integer> count = new HashMap<>();
        Map<Integer, Long> sum = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int val = arr[i];
            int c = count.getOrDefault(val, 0);
            long s = sum.getOrDefault(val, 0L);
            
            intervals[i] += (long)c * i - s;
            
            count.put(val, c + 1);
            sum.put(val, s + i);
        }
        
        // Right to Left Pass
        count.clear();
        sum.clear();
        for (int i = n - 1; i >= 0; i--) {
            int val = arr[i];
            int c = count.getOrDefault(val, 0);
            long s = sum.getOrDefault(val, 0L);
            
            intervals[i] += s - (long)c * i;
            
            count.put(val, c + 1);
            sum.put(val, s + i);
        }
        
        return intervals;
    }
}
```
### Algorithm
*   Initialize a result array `intervals` of size `n` with zeros.
*   **First Pass (Left-to-Right):**
    *   Initialize two maps: `count` to store the frequency of each number, and `sumOfIndices` to store the sum of indices for each number.
    *   Iterate from `i = 0` to `n-1`.
    *   For the current element `val = arr[i]`, get its previous count `c` and sum of indices `s` from the maps.
    *   The sum of distances to identical elements on the left is `c * i - s`. Add this to `intervals[i]`.
    *   Update the maps for `val`: increment its count and add `i` to its sum of indices.
*   **Second Pass (Right-to-Left):**
    *   Clear or re-initialize the `count` and `sumOfIndices` maps.
    *   Iterate from `i = n-1` down to `0`.
    *   For `val = arr[i]`, get its count `c` and sum of indices `s` from the right side (elements already processed in this pass).
    *   The sum of distances to identical elements on the right is `s - c * i`. Add this to `intervals[i]`.
    *   Update the maps for `val`.
*   Return the `intervals` array.

# Solutions
### Java

```java
class Solution {
public
  long[] getDistances(int[] arr) {
    Map<Integer, List<Integer>> d = new HashMap<>();
    int n = arr.length;
    for (int i = 0; i < n; ++i) {
      d.computeIfAbsent(arr[i], k->new ArrayList<>()).add(i);
    }
    long[] ans = new long[n];
    for (List<Integer> v : d.values()) {
      int m = v.size();
      long val = 0;
      for (int e : v) {
        val += e;
      }
      val -= (m * v.get(0));
      for (int i = 0; i < v.size(); ++i) {
        int delta = i >= 1 ? v.get(i) - v.get(i - 1) : 0;
        val += i * delta - (m - i) * delta;
        ans[v.get(i)] = val;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<long long> getDistances(vector<int> &arr) {
    unordered_map<int, vector<int>> d;
    int n = arr.size();
    for (int i = 0; i < n; ++i)
      d[arr[i]].push_back(i);
    vector<long long> ans(n);
    for (auto &item : d) {
      auto &v = item.second;
      int m = v.size();
      long long val = 0;
      for (int e : v)
        val += e;
      val -= m * v[0];
      for (int i = 0; i < v.size(); ++i) {
        int delta = i >= 1 ? v[i] - v[i - 1] : 0;
        val += i * delta - (m - i) * delta;
        ans[v[i]] = val;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def getDistances(self, arr: List[int]) -> List[int]: d = defaultdict(list) n = len(arr) for i, v in enumerate(arr): d[v]. append(i) ans = [0] * n for v in d . values(): m = len(v) val = sum(v) - v[0] * m for i, p in enumerate(v): delta = v[i] - v[i - 1] if i >= 1 else 0 val += i * delta - (m - i) * delta ans[p] = val return ans

```