Intervals Between Identical Elements
MedPrompt
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| = 5Example 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.
Approaches
4 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Initialize a result array
intervalsof sizenwith zeros. - Iterate through the input array
arrwith an outer loop fromi = 0ton-1. - Inside the outer loop, start an inner loop from
j = 0ton-1. - In the inner loop, check if
arr[i]is equal toarr[j]. - If they are equal, calculate the absolute difference of their indices,
|i - j|, and add it to a running sum forintervals[i]. - After the inner loop completes,
intervals[i]will hold the total sum of intervals for the element at indexi. - After the outer loop finishes, return the
intervalsarray.
Walkthrough
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.
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; }}Complexity
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).
Trade-offs
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.
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.
Algorithm
- Create a
HashMapwhere keys are the numbers inarrand values are lists of indices where those numbers appear. - Iterate through the input array
arronce to populate theHashMap. For each elementarr[i], add the indexito the list associated with the valuearr[i]. - Initialize a result array
intervalsof sizen. - Iterate through each list of indices in the
HashMap's values. - For each list, perform a brute-force calculation: for each index
iin the list, iterate through all other indicesjin the same list and sum up the absolute differences|i - j|. - Store the calculated sum in
intervals[i]. - Return the
intervalsarray.
Walkthrough
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.
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; }}Complexity
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).
Trade-offs
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.
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.
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
idxof sizek, which is naturally sorted:- Create a prefix sum array
prefixof sizek+1.prefix[i]will store the sum of the firstiindices. - Calculate the total sum of all indices in the list,
totalSum. - Iterate through the list of indices from
i = 0tok-1. For the current indexcurrIdx = 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.
- The number of elements to the left is
- Create a prefix sum array
- Return the
intervalsarray.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Initialize a result array
intervalsof sizenwith zeros. - First Pass (Left-to-Right):
- Initialize two maps:
countto store the frequency of each number, andsumOfIndicesto store the sum of indices for each number. - Iterate from
i = 0ton-1. - For the current element
val = arr[i], get its previous countcand sum of indicessfrom the maps. - The sum of distances to identical elements on the left is
c * i - s. Add this tointervals[i]. - Update the maps for
val: increment its count and addito its sum of indices.
- Initialize two maps:
- Second Pass (Right-to-Left):
- Clear or re-initialize the
countandsumOfIndicesmaps. - Iterate from
i = n-1down to0. - For
val = arr[i], get its countcand sum of indicessfrom 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 tointervals[i]. - Update the maps for
val.
- Clear or re-initialize the
- Return the
intervalsarray.
Walkthrough
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.
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; }}Complexity
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).
Trade-offs
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.
Solutions
Solution
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; }}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; }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.