Problem
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
Solution (Java)
// HashMap Beats 100%
class Solution {
public long[] distance(int[] arr) {
Map<Long,long[]> map = new HashMap<>();
// [0] -> sum of indices at left of i
// [1] -> sum of indices at right of i
// [2] -> left freq
// [3] -> right freq
int i=0;
for(int e:arr)
{
long x = e;
if(map.get(x)==null){
map.put(x,new long[4]);
}
map.get(x)[1]+=i++; // total sum of indices with value x
map.get(x)[3]++; // no. of occurences of x in arr
}
long[] res = new long[arr.length];
i=0;
for(int e:arr)
{
long x = e;
long[] temp = map.get(x);
temp[1]-=i; // sum of indices at right
temp[3]--; // right freq
res[i]=Math.abs(temp[0]-i*temp[2])+Math.abs(temp[1]-i*temp[3]);
temp[0]+=i++; // sum of indices at left
temp[2]++; // left freq
}
return res;
}
}
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).