CODEWITHSUNDEEP
arraysalgorithmdata-structures
sgoel
sgoel

Reputation: 29

Sum of multiplication of distance and maximum value for each pair in an Integer Array

Given an unsorted Integer array with their values. Need to calculate sum of Multiplication of Distance between each pair and The value that is maximum between them.

To be more clear. Lets say array A[] with n elements

Calculate:- 

for all i & j (i<j)
sum (distance(i,j)*(max(A[i],A[j])))

O(n^2) is easy. I want better than that. I've tried hard but don't know what data structure to use. I would request to give only a hint to solve this problem ( I will try from there )

Upvotes: 1

Views: 164

Answers (1)

kraskevich
kraskevich

Reputation: 18556

I'll assume that all numbers are distinct for simplicity.

Let's iterate from left to right. Let's look at a[i] and add all segments that have their right end in it to the answer. Consider all j < i. There are two possible cases:

  1. a[j] < a[i]. We need to add a[i] * (i - j + 1) to the answer.
  2. a[j] > a[i]. We need to add a[j] * (i - j + 1).

Let's rewrite these two sums: the first one is sum j < i and a[j] < a[i] of a[i] * (i - j + 1) = (a[i] * (i + 1) * number of such j) - (a[i] * (sum j < i and a[j] < a[i] of j)). Note that the a[i] * (i + 1) and a[i] are independent of j, so it's just a constant. We just need to count the number of such j that j < i and a[j] < a[i] and their sum efficiently. In fact, it's a sum on a prefix. A balanced binary search tree could handle that, but we don't need it. We can compress the coordinates and use a binary index tree instead. Now we can compute this sum in O(N log N).

You can do a similar thing with the second sum to obtain an O(N log N) solution.

Upvotes: 1

Related Questions