Find total cost of deleting maximum numbers one by one from an array

Question

I have been given a sequence of n distinct integers a0, a1,...a(n−1). In each iteration I pick the maximum number and delete it; the cost of deleting the maximum number is the number of numbers to the left of it. Repeat this n number of times. I have to find the total cost of n iterations.

For example, if A[] = {6, 2, 8, 4, 9, 3}
The total cost is: 4 + 2 + 0 + 1 + 1 + 0 = 8

I know there are O(n logn) algorithms to solve this problem, common ones being the merge sort approach and the BST approach.

But I am confused on how to implement the BST approach. Any help on how to start would be kindly appreciated.

lots of data structures can solve this, first thing that comes to mind is using 2 segment trees — Photon, Apr 23 '20 at 10:02
@Photon actually the answer is way simpler: OP is just asking for the number of inversion in an array with descending sorting. That's already been answered plenty of times. And yes, there is an `O(n lg n)` algo for that problem — , Apr 23 '20 at 10:15
@Paul, Can you kindly give an intuitive explanation for your answers, so that it easy to visualise — Deepak Tatyaji Ahire, Apr 23 '20 at 10:41

score 0 · Answer 1 · answered Apr 23 '20 at 11:53

0

TLDR:
You're looking for the number of inversions in the array for descending sorting. This is doable in O(n lg n).

The number of inversions in an array A is defined as the number of all pairs of indices i, j, such that i < j and A[i] > A[j]. So basically the number of pairs of values in A such that the first would appear after the second, if A was sorted. This can be calculated by going through all values in A and counting preceding values that should come afterwards:

count_inversions(A):
    count = 0
    for i=0 to length of A - 1:
        for j=0 to i - 1:
            if A[i] > A[j]:
                count++
    return count

For your problem the naive solution would be quite similar:

total_delete_cost(A):
    count = 0
    for i=0 to length of A - 1:
        for j=0 to i - 1:
            if A[i] < A[j]:
                count++
    return count

The only thing that changed is the line if A[i] > A[j]. Or looking at it another way: each value x in A will add m to the total cost, where m is the number of values that are larger than x and have a higher index. This is precisely the number of inversions for a reverse ordering from A.

From here on the remainder of the question is answered here, except for the minor adaption to switch from ascending to descending ordering, so I won't post the code to solve the remainder of the problem.

answered Apr 23 '20 at 11:53

Don't you think that the algorithm you're suggesting is an O(n^2) algorithm ? I think that the only way to solve this problem in O(n logn) is by using Balanced Binary Search trees, as in the [link](https://stackoverflow.com/questions/337664/counting-inversions-in-an-array) you shared. – Shrey Tripathi Apr 23 '20 at 19:47
@ShreyTripathi the algorithm I presented was just a naive brute-force solution. It wasn't meant to solve the problem in `O(n lg n)`, but just to point out the correlation between your problem and the number of inversions problem. – Apr 23 '20 at 19:52
I understood the method, i.e., using Binary Search Trees, but I am not able to implement it. Since I am new to Binary Search Trees, some help on how to do it would be good. I could not find how to do so on the internet. – Shrey Tripathi Apr 24 '20 at 06:43
@ShreyTripathi you should probably switch to the mergesort approach. It's way more common (most answers to the linked question use mergesort) and simpler. To be honest, I wonder why you chose a BST in the first place? – Apr 24 '20 at 07:27
Yeah, and I have implemented the mergesort approach. But since I was studying BSTs I was wondering of a BST approach to solve the problem. – Shrey Tripathi Apr 24 '20 at 16:29

ruakh · Accepted Answer · 2020-04-28T02:22:53.110

But I am confused on how to implement the BST approach.

If you write a balanced-binary-search-tree implementation (such as a red-black tree implementation), and have it keep track of the size of each node's subtree (which you can do without affecting the asymptotic complexity guarantees), then you can give it an "index of" or "count less than" method that computes, in O(log n) time, how many elements are less than a given value.

Creating that implementation is the hard part (though at least you don't need to support deletion); once you have it, the algorithm is pretty straightforward:

initialize a tree, initially empty
initialize an integer result, initially zero
for each element elem:
- ask the tree how many elements are less than elem; add that number to result
- add elem to the tree
return result

Find total cost of deleting maximum numbers one by one from an array

2 Answers2