Algorithm: Given an array A of numbers, create an array B where B[i] = sum(A[j]: A[j] <= A[i]) -

example: = [4, 1, 3, 2, 3, 3]. we'd b = [16, 1, 12, 3, 12, 12].

approach 1: each i, search through , sum numbers less or equal a[i]. speaking, requires transversing through n times, it'll take o(n^2) time.

approach 2: sort a', , find cumsum of a'. requires transversing through a' once. overall running time sort, o(n log n).

however, doesn't work when there ties. example above, a' = [1, 2, 3, 3, 3, 6], cumsum(a') = [1, 3, 6, 9, 12, 16], not same b (sorted).

is there way fix still runs in o(n log n)?

one way modern languages use dictionnary :

a=random_integers(1,10,10) sa=sorted(a) #o(n log n) csa=cumsum(sa)  #o(n) i=dict(zip(sa,csa)) #o(n) b=[i[x] x in a] #o(n) 

when building dictionnary, last value encountered replace existing one, @ least fits one. gives :

[7 5 4 1 4 2 6 7 8 2] [1 2 2 4 4 5 6 7 7 8] [1 3 5 9 13 18 24 31 38 46] {1:1, 2:5, 4:13, 5:18, 6:24, 7:38, 8:46} [38 18 13 1 13 5 24 38 46 5]