[Leetcode]- weekly contest 341 (Sum of Distances)

Brain Fucked

 

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.

 

https://leetcode.com/problems/sum-of-distances/description/

 

Constraints:

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^9

 

Brute force: Math.abs( node[i] - node[j] ) (O(N^2))

 

Hint 1

ex) 동일 value의 배열이 다음과 같을 때, [1,4,1,1,6,3,2,1,1]; 

동일 값을 가진 노드의 인덱스를 배열 멤버로 갖는 맵은 다음과 같으며

 

{
 1: [0,2,3,7,8]
}

 

 

 

 

 

Hint 2

예를 들어 3번 노드에 대해, distance를 구해 보면 다음과 같다.

| 3 - 0 | + | 3 - 2 | + | 7 - 3 | + | 8 - 3|

3번 노드를 기준으로 좌측과 우측에 대해 계산법이 달라진다.

 

 

 

 

 

 

 

Hint 3

좌측의 경우, 일축하자면,  3*2 - ( 좌측 구간합)

우측의 경우, 일축하자면, (우측 구간합) - (3 * 2)

로 표현이 가능하다.

Prefix = node[i]*i - leftSum + rightSum - node[j]*j

 

 

 

 

 

 

Solution

var distance = function(nums) {
  let n = nums.length, map = {};
  for (let i = 0; i < n; i++) {
    if (!map[nums[i]]) map[nums[i]] = [];
    map[nums[i]].push(i);
  }
  let ans = Array(n).fill(0);
  for(const key of Object.keys(map)){
    const length = map[key].length;
    const current = map[key]
    let leftSum = 0, rightSum = 0;
    if(current.length === 1){
      continue;
    }
    for(let i = 0; i < length ; i ++){
      leftSum += current[i];
      ans[current[i]] = current[i] * (i+1) - leftSum;
    }

    for(let i = length - 1 ; i >= 0 ; i --){
      rightSum += current[i]
      ans[current[i]] += rightSum - current[i] * (length - i)
    }
    console.log(ans)
  }
  return ans;
};