Intervals Between Identical Elements — Problem & Solution
Intervals Between Identical Elements solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Intervals Between Identical Elements is a medium coding problem on arrays, hash table and prefix sum, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Prefix Sum
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array arr of n integers. The interval between two positions i and j is |i - j|.
For every index i, compute the sum of the intervals between i and every other index j holding the same value (arr[j] == arr[i]). Return the array intervals of those sums.
The constraints are tightened from the original (n is at most 4 * 10^4) so every sum fits in a 32-bit integer.
Example 1
Input: arr = [2,1,3,1,2,3,3]
Output: [4,2,7,2,4,4,5]
Explanation: Index 2 (value 3) pairs with indices 5 and 6: |2 - 5| + |2 - 6| = 7. Index 0 (value 2) pairs with index 4: 4.
Example 2
Input: arr = [10,5,10,10]
Output: [5,0,3,4]
Explanation: The 5 at index 1 is alone, so its sum is 0.
Example 3
Input: arr = [7]
Output: [0]
Constraints
n == arr.length1 <= n <= 4 * 10^41 <= arr[i] <= 10^5
Hints for Intervals Between Identical Elements
Hint 1
Only indices with the same value interact, so handle each value's list of positions separately.
Hint 2
For a sorted list of positions, the distance from position
pto everything on its left iscount_left * p - sum_left; to its right,sum_right - count_right * p.Hint 3
Sweep once left to right keeping, per value, how many positions you have seen and their sum; then once right to left. Add both contributions.
How to solve Intervals Between Identical Elements
Split |i - j| by side: for the earlier positions of the same value it is i - j, for the later ones j - i. Summing i - j over the earlier ones is count * i - sum — two running totals per value are enough, so two sweeps answer every index.
Approach
- Left to right: keep
cnt[v]andsum[v]of the positions seen so far with valuev. At indexiwith valuev, addcnt[v] * i - sum[v]toanswer[i], then includei. - Right to left with fresh totals: add
sum[v] - cnt[v] * itoanswer[i], then includei. - Return
answer.
Why it works
For a fixed i, every same-valued index j < i contributes i - j, and the sum of those is cnt * i - sum over exactly the indices counted when the left sweep reaches i. The right sweep symmetrically sums j - i over j > i. Indices with other values never enter the totals for v.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- The quadratic "compare with every equal element" approach times out on long runs of one value.
- In the original problem (
nup to10^5) the sums need 64-bit integers; heren <= 4 * 10^4keeps every sum below8 * 10^8.
Reference solution
Python
from typing import List
def getDistances(arr: List[int]) -> List[int]:
n = len(arr)
answer = [0] * n
cnt, tot = {}, {}
for i, v in enumerate(arr):
c, s = cnt.get(v, 0), tot.get(v, 0)
answer[i] += c * i - s
cnt[v], tot[v] = c + 1, s + i
cnt, tot = {}, {}
for i in range(n - 1, -1, -1):
v = arr[i]
c, s = cnt.get(v, 0), tot.get(v, 0)
answer[i] += s - c * i
cnt[v], tot[v] = c + 1, s + i
return answerJava
public static int[] getDistances(int[] arr) {
int n = arr.length;
int[] answer = new int[n];
Map<Integer, int[]> seen = new HashMap<>();
for (int i = 0; i < n; i++) {
int[] cs = seen.computeIfAbsent(arr[i], key -> new int[2]);
answer[i] += cs[0] * i - cs[1];
cs[0]++;
cs[1] += i;
}
seen.clear();
for (int i = n - 1; i >= 0; i--) {
int[] cs = seen.computeIfAbsent(arr[i], key -> new int[2]);
answer[i] += cs[1] - cs[0] * i;
cs[0]++;
cs[1] += i;
}
return answer;
}C++
vector<int> getDistances(vector<int>& arr) {
int n = arr.size();
vector<int> answer(n, 0);
unordered_map<int, pair<int, int>> seen;
for (int i = 0; i < n; i++) {
auto& cs = seen[arr[i]];
answer[i] += cs.first * i - cs.second;
cs.first++;
cs.second += i;
}
seen.clear();
for (int i = n - 1; i >= 0; i--) {
auto& cs = seen[arr[i]];
answer[i] += cs.second - cs.first * i;
cs.first++;
cs.second += i;
}
return answer;
}JavaScript
var getDistances = function(arr) {
var n = arr.length;
var answer = new Array(n);
var cnt = new Map(), tot = new Map();
for (var i = 0; i < n; i++) {
var v = arr[i], c = cnt.get(v) || 0, s = tot.get(v) || 0;
answer[i] = c * i - s;
cnt.set(v, c + 1);
tot.set(v, s + i);
}
cnt = new Map();
tot = new Map();
for (var j = n - 1; j >= 0; j--) {
var w = arr[j], c2 = cnt.get(w) || 0, s2 = tot.get(w) || 0;
answer[j] += s2 - c2 * j;
cnt.set(w, c2 + 1);
tot.set(w, s2 + j);
}
return answer;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets