Intervals Between Identical Elements

Medium
1855.

Intervals Between Identical Elements

Intervals Between Identical Elements is a medium coding problem on arrays, hash table and prefix sum, asked in Amazon and Google interviews.

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.length
  • 1 <= n <= 4 * 10^4
  • 1 <= arr[i] <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @return {number[]}
 */
var getDistances = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.length
  • 1 <= n <= 4 * 10^4
  • 1 <= arr[i] <= 10^5

Hints for Intervals Between Identical Elements

  1. Hint 1

    Only indices with the same value interact, so handle each value's list of positions separately.

  2. Hint 2

    For a sorted list of positions, the distance from position p to everything on its left is count_left * p - sum_left; to its right, sum_right - count_right * p.

  3. 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

  1. Left to right: keep cnt[v] and sum[v] of the positions seen so far with value v. At index i with value v, add cnt[v] * i - sum[v] to answer[i], then include i.
  2. Right to left with fresh totals: add sum[v] - cnt[v] * i to answer[i], then include i.
  3. 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 (n up to 10^5) the sums need 64-bit integers; here n <= 4 * 10^4 keeps every sum below 8 * 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 answer

Java

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