Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2121.html

2121. Intervals Between Identical Elements (Medium)

You are given a 0-indexed array of n integers arr.

The interval between two elements in arr is defined as the absolute difference between their indices. More formally, the interval between arr[i] and arr[j] is |i - j|.

Return an array intervals of length n where intervals[i] is the sum of intervals between arr[i] and each element in arr with the same value as arr[i].

Note: |x| is the absolute value of x.

 

Example 1:

Input: arr = [2,1,3,1,2,3,3]
Output: [4,2,7,2,4,4,5]
Explanation:
- Index 0: Another 2 is found at index 4. |0 - 4| = 4
- Index 1: Another 1 is found at index 3. |1 - 3| = 2
- Index 2: Two more 3s are found at indices 5 and 6. |2 - 5| + |2 - 6| = 7
- Index 3: Another 1 is found at index 1. |3 - 1| = 2
- Index 4: Another 2 is found at index 0. |4 - 0| = 4
- Index 5: Two more 3s are found at indices 2 and 6. |5 - 2| + |5 - 6| = 4
- Index 6: Two more 3s are found at indices 2 and 5. |6 - 2| + |6 - 5| = 5

Example 2:

Input: arr = [10,5,10,10]
Output: [5,0,3,4]
Explanation:
- Index 0: Two more 10s are found at indices 2 and 3. |0 - 2| + |0 - 3| = 5
- Index 1: There is only one 5 in the array, so its sum of intervals to identical elements is 0.
- Index 2: Two more 10s are found at indices 0 and 3. |2 - 0| + |2 - 3| = 3
- Index 3: Two more 10s are found at indices 0 and 2. |3 - 0| + |3 - 2| = 4

 

Constraints:

  • n == arr.length
  • 1 <= n <= 105
  • 1 <= arr[i] <= 105

Companies:
TuSimple, Wayve

Related Topics:
Array, Hash Table, Prefix Sum

Similar Questions:

Solution 1.

Assume number k appears at indices 1, 3, 5, 7.

For index 1, ans[1] = |3-1|+|5-1|+|7-1| = (3+5+7) - 3*1.

For index 3, ans[3] = |3-1|+|5-3|+|7-3| = (5+7) - 2*3 + 1*3 - 1

…

We can find the following pattern:

Here only consider the indices of the same numbers. Let rightSum/leftSum be the sum of indices to the right/left of i, and rightCnt/leftCnt be the number of indices to the right/left of i.

ans[i] = rightSum - rightCnt * i + leftCnt * i - leftSum

// OJ: https://leetcode.com/problems/intervals-between-identical-elements/
// Time: O(N)
// Space: O(N)
class Solution {
public:
    vector<long long> getDistances(vector<int>& A) {
        unordered_map<int, long> leftSum, leftCnt, rightSum, rightCnt;
        int N = A.size();
        for (int i = 0; i < N; ++i) {
            rightSum[A[i]] += i;
            ++rightCnt[A[i]];
        }
        vector<long long> ans(N);
        for (int i = 0; i < N; ++i) {
            rightSum[A[i]] -= i;
            rightCnt[A[i]]--;
            ans[i] = rightSum[A[i]] - rightCnt[A[i]] * i + leftCnt[A[i]] * i - leftSum[A[i]];
            leftSum[A[i]] += i;
            leftCnt[A[i]]++;
        }
        return ans;
    }
};

We can update the formula to the following

ans[i] = (rightSum - leftSum) - (rightCnt - leftCnt) * i
       = diffSum - diffCnt * i

In this way, we only need to keep track of the diffs.

// OJ: https://leetcode.com/problems/intervals-between-identical-elements/
// Time: O(N)
// Space: O(N)
class Solution {
public:
    vector<long long> getDistances(vector<int>& A) {
        unordered_map<int, long> diffSum, diffCnt;
        int N = A.size();
        for (int i = 0; i < N; ++i) {
            diffSum[A[i]] += i;
            ++diffCnt[A[i]];
        }
        vector<long long> ans(N);
        for (int i = 0; i < N; ++i) {
            diffSum[A[i]] -= i;
            diffCnt[A[i]]--;
            ans[i] = diffSum[A[i]] - diffCnt[A[i]] * i;
            diffSum[A[i]] -= i;
            diffCnt[A[i]]--;
        }
        return ans;
    }
};

Minor simplification: We can include |i-i| = 0 in the formula.

For example:

For index 1, ans[1] = |1-1|+|3-1|+|5-1|+|7-1| = (1+3+5+7) - 4*1.

For index 3, ans[3] = |3-1|+|3-3|+|5-3|+|7-3| = (3+5+7) - 3*3 + 1*3 - 1

…

Now we can define rightSum and rightCnt be the sum/count of indices >= i.

// OJ: https://leetcode.com/problems/intervals-between-identical-elements/
// Time: O(N)
// Space: O(N)
class Solution {
public:
    vector<long long> getDistances(vector<int>& A) {
        long long diffSum[100001] = {}, diffCnt[100001] = {}, N = A.size();
        for (int i = 0; i < N; ++i) {
            diffSum[A[i]] += i;
            diffCnt[A[i]]++;
        }
        vector<long long> ans(N);
        for (int i = 0; i < N; ++i) {
            ans[i] = diffSum[A[i]] - diffCnt[A[i]] * i;
            diffSum[A[i]] -= 2 * i;
            diffCnt[A[i]] -= 2;
        }
        return ans;
    }
};

Solution 2.

Similar to 1685. Sum of Absolute Differences in a Sorted Array (Medium)

// OJ: https://leetcode.com/problems/intervals-between-identical-elements/
// Time: O(N)
// Space: O(N)
class Solution {
public:
    vector<long long> getDistances(vector<int>& A) {
        unordered_map<int, vector<int>> m;
        int N = A.size();
        vector<long long> ans(N);
        for (int i = 0; i < N; ++i) m[A[i]].push_back(i);
        for (auto &[n, v] : m) {
            long total = accumulate(begin(v), end(v), 0L), right = total;
            for (long i = 0; i < v.size(); ++i) {
                ans[v[i]] = right - (v.size() - i) * v[i] + i * v[i] - (total - right);
                right -= v[i];
            }
        }
        return ans;
    }
};

All Problems

All Solutions