2615. Sum of Distances / TypeScript

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.

 

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

 

 

function distance(nums: number[]): number[] {
    const indexMap: Map<number, number[]> = new Map();
    const result: number[] = new Array(nums.length).fill(0);

    // 같은 값의 인덱스를 저장
    for (let i = 0; i < nums.length; i++) {
        if (!indexMap.has(nums[i])) {
            indexMap.set(nums[i], []);
        }
        indexMap.get(nums[i])!.push(i);
    }

    // 각 인덱스에 대해 같은 값의 인덱스들과의 거리 계산
    indexMap.forEach(indices => {
        const n = indices.length;
        if (n < 2) return;

        // 전체 거리 계산
        let totalSum = 0;
        for (let i = 1; i < n; i++) {
            totalSum += indices[i] - indices[0];
        }

        result[indices[0]] = totalSum;

        // sliding window 방식으로 거리 계산 최적화
        for (let i = 1; i < n; i++) {
            const diff = indices[i] - indices[i - 1];
            totalSum += diff * (2 * i - n);
            result[indices[i]] = totalSum;
        }
    });

    return result;
}

 

• 인덱스 저장: indexMap을 사용하여 각 숫자에 대한 인덱스 리스트를 저장.
• 거리 계산: indexMap에서 각 숫자에 대해 인덱스 리스트를 가져오고, 각 인덱스에 대해 거리를 계산

 

예시 nums = [1, 3, 1, 1, 2]

 

indexMap.get(nums[i])!.push(i);

• 배열 nums에서 현재 값 nums[i]의 인덱스 i를 indexMap에 추가하는 역할을 함

indexMap = {
    1: [0, 2, 3],
    3: [1],
    2: [4]
}

 

1. 첫 번째 루프: totalSum 초기화

for (let i = 1; i < n; i++) {
    totalSum += indices[i] - indices[0];
}

예시: 숫자 1의 경우

• indices = [0, 2, 3]일 때,
• totalSum = |0 - 2| + |0 - 3| = 2 + 3 = 5
• 즉, result[0] = 5

 

2. 두 번째 루프: 슬라이딩 윈도우 방식으로 최적화

for (let i = 1; i < n; i++) {
    const diff = indices[i] - indices[i - 1];
    totalSum += diff * (2 * i - n);
    result[indices[i]] = totalSum;
}

 

슬라이딩 윈도우 방식 설명

슬라이딩 윈도우 방식은 현재 위치와 이전 위치의 차이(diff = indices[i] - indices[i - 1])를 이용해 전체 거리를 업데이트

• 작동 방식:
  • diff = indices[i] - indices[i - 1]은 현재 인덱스와 이전 인덱스 간의 차이를 계산
  • 이 diff 값을 이용해 totalSum을 업데이트합니다. 여기서 (2 * i - n)는 현재 인덱스가 배열의 중간에 있을 때 거리 합을 더하거나 빼주는 역할을 함.

예시: 숫자 1의 경우

• indices = [0, 2, 3]일 때,
• 첫 번째 인덱스에서 이미 totalSum = 5.
• 이제 두 번째 인덱스에 대해:

const diff = 2 - 0 = 2;
totalSum += 2 * (2 * 1 - 3); // totalSum = 5 - 2 = 3
result[2] = 3;

 

• 세 번째 인덱스에 대해:

const diff = 3 - 2 = 1;
totalSum += 1 * (2 * 2 - 3); // totalSum = 3 + 1 = 4
result[3] = 4;

 

 

- 숫자 3 (인덱스 [1])

이 숫자에 대해서는 다른 같은 값을 가진 인덱스가 없으므로 arr[1] = 0

- 숫자 2 (인덱스 [4])

이 숫자에 대해서도 다른 같은 값을 가진 인덱스가 없으므로 arr[4] = 0

 

따라서 최종

arr = [5, 0, 3, 4, 0]