<p>You are given a <strong>0-indexed</strong> integer array <code>nums</code>. There exists an array <code>arr</code> of length <code>nums.length</code>, where <code>arr[i]</code> is the sum of <code>|i - j|</code> over all <code>j</code> such that <code>nums[j] == nums[i]</code> and <code>j != i</code>. If there is no such <code>j</code>, set <code>arr[i]</code> to be <code>0</code>.</p>

<p>Return <em>the array </em><code>arr</code><em>.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,3,1,1,2]
<strong>Output:</strong> [5,0,3,4,0]
<strong>Explanation:</strong> 
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. 

</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [0,5,3]
<strong>Output:</strong> [0,0,0]
<strong>Explanation:</strong> Since each element in nums is distinct, arr[i] = 0 for all i.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
</ul>

<p>&nbsp;</p>
<p><strong>Note:</strong> This question is the same as <a href="https://leetcode.com/problems/intervals-between-identical-elements/description/" target="_blank"> 2121: Intervals Between Identical Elements.</a></p>

class Solution:
    def distance(self, nums: List[int]) -> List[int]:
        """
        - no negative nums
        - |x - y| = 0; x, y are indices and x != y
            - (x - y) = 0 and -(x - y) = 0
            - abs difference
        - consider indices seen so far or from whole array?

        # option 1
        - start with each num and check for the diff value
        - create a sum var that tracks cummulative sum
        [1, 3, 2, 1, 1]
         i 
                    j
        for i in range(len(num))
            cum_sum = 0
            for j in range(len(num))
                if i != j and num[i] == num[j]
                    cum_sum += abs(j - i)
            arr[i] = cum_sum

        time: O(n^2); n=len(nums)
        space: O(n)

        # option 2: time-optimized
        ways of scanning array in linear time:
            - shrink/expand pointers
            - L to R and then R to L scans (use: items from both sides are used in calculation)
            - store cummulative vals (vals seen so far) in hashmap (use: items on either side are not included in calculation)
        consider an example of num=1 at i=4:
            - left side calculation: 
                1. 4-0 + 4-3 = 5
                2. 4 * (count of num=1 so far) - sum_from_left = 4*2-3=5
            - right side calculation:
                1. 6-4 + 5-4 = 3
                2.a (as incdices on right will be greater) 
                2.b sum_from_right - 4 * (count of num=1 from right) = 11-4*2 = 3
         0  1  2. 3. 4. 5. 6
        [1, 3, 2, 1, 1, 1, 4]
                     ^
        time: O(n), space: O(n)
        """
        arr = [0] * len(nums)
        count_from_left = defaultdict(int)
        sum_from_left = defaultdict(int)
        count_from_right = defaultdict(int)
        sum_from_right = defaultdict(int)

        # iterate from L to R
        for i, num in enumerate(nums):
            # get the left sum
            arr[i] += (count_from_left[num] * i - sum_from_left[num])

            # update the counters
            sum_from_left[num] += i
            count_from_left[num] += 1

        # iterate from R to L
        for i in range(len(nums) - 1, -1, -1):
            num = nums[i]
            arr[i] += (sum_from_right[num] - count_from_right[num] * i)

            # update the counters
            sum_from_right[num] += i
            count_from_right[num] += 1

        return arr
        
635