Leetcode 2615: Sum of Distances

Input: The input consists of a 0-indexed integer array `nums` of length `n`. Each element of `nums` is an integer in the range [0, 10^9].

Example: nums = [1, 3, 1, 1, 2]

Constraints:

• 1 <= nums.length <= 10^5

• 0 <= nums[i] <= 10^9

Output: Return an array `arr` where for each `i`, `arr[i]` is the sum of absolute differences |i - j| for all `j` such that `nums[j] == nums[i]` and `j != i`. If no such `j` exists, set `arr[i] = 0`.

Example: Output: [5, 0, 3, 4, 0]

Constraints:

• The array `arr` must have the same length as the input array `nums`.

Goal: The goal is to calculate the sum of absolute differences for each element of the array, considering the other elements with the same value and their indices.

Steps:

• Step 1: Initialize two maps to keep track of the cumulative sum of indices and the count of occurrences for each number.

• Step 2: Iterate through the array from left to right, and for each index, calculate the sum of absolute differences based on previously encountered indices of the same value.

• Step 3: Iterate through the array from right to left to update the result array with the contributions from indices after the current one.

• Step 4: Return the final result array.

Goal: Ensure that the solution can handle arrays with sizes up to 100,000 elements efficiently, and properly compute the sum of absolute differences for large numbers in the range [0, 10^9].

Steps:

• The algorithm should handle up to 10^5 elements in `nums` efficiently.

• The values in `nums` can be as large as 10^9, so the solution should work within these constraints.

Assumptions:

• All elements in the array are non-negative integers.

• If there are multiple occurrences of a number, the distances should be calculated between all pairs of indices with the same value.

• Input: nums = [1, 3, 1, 1, 2]

• Explanation: For index 0 (value 1), there are two other occurrences of 1 at indices 2 and 3. The absolute differences are |0 - 2| + |0 - 3| = 5, so arr[0] = 5. For index 1 (value 3), there are no other occurrences of 3, so arr[1] = 0. The same logic applies for the other indices.

• Input: nums = [0, 5, 3]

• Explanation: Each value in `nums` is distinct, so the sum of absolute differences for all indices is 0. Hence, the result is [0, 0, 0].

Approach: The approach involves efficiently calculating the sum of absolute differences for each element by using two passes over the input array. In the first pass, we compute contributions from previous occurrences, and in the second pass, we compute contributions from subsequent occurrences.

Observations:

• Using a brute force solution with nested loops would be too slow, especially for large arrays.

• By keeping track of the sum of indices and count of occurrences for each number in a map, we can efficiently compute the result in two passes over the array.

Steps:

• Step 1: Initialize two maps, one for cumulative sums of indices and another for counts of occurrences.

• Step 2: Iterate through the array from left to right. For each index `i`, calculate the sum of absolute differences using the cumulative sum and count of occurrences for `nums[i]`.

• Step 3: Clear the maps and iterate from right to left to handle the contributions from subsequent indices.

• Step 4: Return the result array containing the computed values.

Empty Inputs:

• If the input array is empty, return an empty array.

Large Inputs:

• The solution should handle arrays of size up to 10^5 efficiently.

Special Values:

• If all elements are distinct, the result should be an array of zeros.

Constraints:

• The solution should work even for very large integers (up to 10^9).

vector<long long> distance(vector<int>& nums) {
    /*
    
    [1,3,1,1,2]
     0,1,2,3,4
    
     0
       0  
     2   2
     5   3 4
             0
    */
    
    unordered_map<int, double> mp, cnt;
    int n = nums.size();
    vector<long long> arr(n, 0);
    for(int i = 0; i < n; i++) {
        arr[i] = cnt[nums[i]] * i - mp[nums[i]];
        mp[nums[i]] += i;
        cnt[nums[i]] += 1;
    }
    mp.clear(), cnt.clear();        
    for(int i = n - 1; i >= 0; i--) {
        arr[i] += mp[nums[i]] - cnt[nums[i]] * i;
        mp[nums[i]] += i;
        cnt[nums[i]] += 1;
    }
    return arr;
}

1 : Code Start

vector<long long> distance(vector<int>& nums) {

Function definition for calculating distances.

2 : Data Structure Initialization

    unordered_map<int, double> mp, cnt;

Declare unordered maps `mp` and `cnt` for tracking the sum of indices and counts.

3 : Size Calculation

    int n = nums.size();

Store the size of the `nums` array.

4 : Array Initialization

    vector<long long> arr(n, 0);

Initialize an array `arr` of size `n` to store the result.

5 : Loop Start

    for(int i = 0; i < n; i++) {

Loop through the array `nums` to calculate partial distances.

6 : Update Distance

        arr[i] = cnt[nums[i]] * i - mp[nums[i]];

Calculate and store the partial result in `arr[i]`.

7 : Update Sum Map

        mp[nums[i]] += i;

Update the sum of indices for the current value in `nums`.

8 : Update Count Map

        cnt[nums[i]] += 1;

Increment the count for the current value in `nums`.

9 : Clear Maps

    mp.clear(), cnt.clear();

Clear the maps `mp` and `cnt` before the reverse pass.

10 : Reverse Loop Start

    for(int i = n - 1; i >= 0; i--) {

Loop through the array `nums` in reverse to complete the calculation.

11 : Update Reverse Distance

        arr[i] += mp[nums[i]] - cnt[nums[i]] * i;

Update the distance for each element in the reverse pass.

12 : Update Reverse Sum Map

        mp[nums[i]] += i;

Update the sum of indices for the current value in the reverse pass.

13 : Update Reverse Count Map

        cnt[nums[i]] += 1;

Increment the count for the current value in the reverse pass.

14 : Return Result

    return arr;

Return the final calculated array `arr`.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is O(n) because the algorithm makes two passes through the array, each requiring O(n) time, where `n` is the length of the array.

Best Case: O(n)

Worst Case: O(n)

Description: The space complexity is O(n) because the algorithm uses hash maps to store the cumulative sum and counts of occurrences for each unique value in the array.

Leetcode 2615: Sum of Distances

Explore →