Description
You are given a 0-indexed integer array nums.
There exists an array arr of length nums.length, where arr[i] is the sum of |i - j| over all j such that nums[j] == nums[i] and j != i. If there is no such j, set arr[i] to be 0.
Return the array arr.
Example 1:
Input: nums = [1,3,1,1,2] Output: [5,0,3,4,0] Explanation: When i = 0, nums[0] == nums[2] and nums[0] == nums[3]. Therefore, arr[0] = |0 - 2| + |0 - 3| = 5. When i = 1, arr[1] = 0 because there is no other index with value 3. When i = 2, nums[2] == nums[0] and nums[2] == nums[3]. Therefore, arr[2] = |2 - 0| + |2 - 3| = 3. When i = 3, nums[3] == nums[0] and nums[3] == nums[2]. Therefore, arr[3] = |3 - 0| + |3 - 2| = 4. When i = 4, arr[4] = 0 because there is no other index with value 2.
Example 2:
Input: nums = [0,5,3] Output: [0,0,0] Explanation: Since each element in nums is distinct, arr[i] = 0 for all i.
Constraints:
1 <= nums.length <= 1050 <= nums[i] <= 109
Note: This question is the same as 2121: Intervals Between Identical Elements.
Solutions
This is an optimized version that uses a prefix sum technique to avoid redundant distance calculations. For each group of equal values, it computes a total sum of all indices, then uses the formula total - 2 * prefixTotal + index * (2 * i - len) to calculate each distance in O(1) time. The prefixTotal accumulates indices as we iterate through the group, allowing the algorithm to compute all results efficiently in linear time.
/**
* @param {number[]} nums
* @return {number[]}
*/
var distance = function(nums) {
const n = nums.length;
const map = new Map();
const dp = new Array(n).fill(0);
for (let i = 0; i < n; i++) {
if (!map.has(nums[i])) {
map.set(nums[i], []);
}
map.get(nums[i]).push(i);
}
const res = Array(n).fill(0);
for (const group of map.values()) {
let total = 0;
for (const idx of group) {
total += idx;
}
const len = group.length;
let prefixTotal = 0;
for (let i = 0; i < len; i++) {
const index = group[i];
res[index] = total - 2 * prefixTotal + index * (2 * i - len);
prefixTotal += index;
}
}
return res;
};