2121. Intervals Between Identical Elements, medium, prefix sums.

NOTE
prefix sums is structured in index form rather then value form. you might have seen prefix sum like

  for (int i = 1; i < n; i++) 
    prefix[i] = prefix[i - 1] + arr[i];

whereas this will be

  for (int i = 1; i < n; i++) 
    prefix[arr[i]] = prefix[arr[i - 1]] + something.

notice we are storing values at the value of that array

Approach

• we first maintained the count of indexes of the same elements through a map.
• now we have our data in organized form, only counting all the differences is remaining.
• we wish to count the absolute differences in optimize way O(n). (can be extended in O(n^2)).
• lets say for the element 1 is repeating @index 0, 2, 4, 5, 6.
• and by some means we have distance of 4 from 0, 2.
• we would like to extend this for 5.
  • so, we will have to extend for 0 -- 4 -> 5.
  • so, we will have to extend for 2 -- 4 -> 5.
  • so, we will have to extend for 4 -- 4 -> 5.
  • or, we will have to extend for all the elements smaller then 4. means 3 times.
  • and, we will have to extend them by 5 - 4.

in generalise form

      prefix[current_element] = prefix[previous_element] + 
                                (elements_to_the_left)   * 
                                (current_element - previous_element)

We will then prepare a prefix array and suffix array to maintain this value from both sides.

implementation of the same

```cpp vector getDistances(vector& arr) { map<int, vector> mp; int n = arr.size(); for (int i = 0; i < n; i++) mp[arr[i]].push_back(i); vector prefix(n, 0), suffix(n, 0); for (const auto& [key, value]: mp) { for (int i = 1; i < value.size(); i++) { int diff = value[i] - value[i - 1]; int elements_to_left = i; prefix[value[i]] = prefix[value[i - 1]] + elements_to_left * diff; } for (int i = value.size() - 2; i >= 0; i--) { int diff = value[i + 1] - value[i]; int elements_to_right = (value.size() - i - 1); suffix[value[i]] = suffix[value[i + 1]] + elements_to_right * diff; } } vector ans; for (int i = 0; i < n; i++) ans.push_back(prefix[i] + suffix[i]); return ans; } ``` </details>