Intervals Between Identical Elements — LeetCode 2121 Python Solution

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

Example

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

Python solution

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

Complexity

Pattern: Prefix Sum

Precompute running totals once so any range query becomes a single subtraction. LeetCode 2121. Intervals Between Identical Elements is filed here because LeetCode tags it Prefix Sum, which is the vocabulary this hub collects.

The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.

Related problems