CODEWITHSUNDEEP
algorithm
mouse88
mouse88

Reputation: 1

Given an unsorted integer array A, return an array B, where B[i] is the number of A[j] such that A[i] > A[j] while i < j

Example: A = [5, 3, 8, 7, 2, 1, 4]. Then we'd get B = [4, 2, 4, 3, 1, 0, 0].

Is there a way to do this in O(n log n)?

Upvotes: 0

Views: 38

Answers (2)

Murat Akburak
Murat Akburak

Reputation: 51

You can use a segment tree structure( Each node will store the sum of its children ).All nodes of segment tree is 0 initially. Start from right to left and check the sum of [ai+1,N]. This will be B[i] and then when i passed update the ai. leaf as 1.

Upvotes: 0

mcdowella
mcdowella

Reputation: 19601

a) Work from right to left, inserting the values in an annotated balanced tree as you go. If you keep annotations in the tree that tell you the number of items below each node then you can work out the number of items to the right of each item less than it as you insert. This is a balanced tree, so each insert costs you at most log n, for a total cost of n log n.

b) Divide and conquer, splitting the array into half at each point, and returning the values in sorted order and the B array calculated for each half. When you merge, you need to do a sort, and for the left half of the array you need to add on the number of values in the right half of the array less than itself. You can do this as part of the merge, and it still takes linear time, so the cost is the usual n log n of a merge sort.

Upvotes: 1

Related Questions