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

Question

Example: A = [4, 1, 3, 2, 3, 3]. Then we'd get B = [16, 1, 12, 3, 12, 12].

Approach 1: For each i, just search through A and sum up the numbers that are less than or equal to A[i]. Roughly speaking, this requires transversing through A n times, so it'll take O(n^2) time.

Approach 2: Sort A to get A', and then just find the cumsum of A'. This requires transversing through A' only once. So the overall running time is just the sort, O(n log n).

However, this doesn't work when there are ties. For the example above, we get A' = [1, 2, 3, 3, 3, 6], so cumsum(A') = [1, 3, 6, 9, 12, 16], which is not the same as B (sorted).

Is there a way to fix this so that it still runs in O(n log n)?

Answer 1

One way to do that with modern languages is to 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] for x in A] #O(n)

When building the dictionnary, the last value encountered replace the existing one, so at least it fits the good one. That 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] 

Answer 2

I have easy approach to doing this in o(nlogn).

• sort the array with respect to their value in increasing order.In sorting index of element should go with element.for sorting in java you can use inbuilt function

  java.util.Arrays.sort(input, new java.util.Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                return Double.compare(a[1], b[1]);
            }
        });

• create a temp array which will contain answer.
• calculate sum of all element in sorted array.
• traverse sorted array from back to front.
• maintain count for contiguous similar number.
• when get different value from next value update sum with sum-count*nextvalue.
• store the sum at index of current value;

Here is my java code

class Solution
{
 public static void main (String[] args) throws java.lang.Exception
 {
  int[][] input={{0,4}, {1,1}, {2,3}, {3,2}, {4,3}, {5,3
  
          //sort one column with respect to other column in 2d array
    java.util.Arrays.sort(input, new java.util.Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                return Double.compare(a[1], b[1]);
            }
           });
        
           int[] temp=new int[6];   //Answer array
           int sum=0;
           
           for(int i=0;i<6;i++){
               sum=sum+input[i][1];
           }
           
           int count=1;
           temp[input[5][0]]=sum;
           
           for(int i=4;i>=0;i--){
               if(input[i][1]==input[i+1][1]){
                   count++;
                   temp[input[i][0]]=sum;
               }
               else{
                   sum=sum-(count*input[i+1][1]);
                   temp[input[i][0]]=sum;
                   count=1;
               }
           }
           
           for(int i=0;i<6;i++)
              System.out.print(temp[i]+" ");
 }
}

Answer 3

Okay, if you allow for O(n log n) Then here is a very simple approach to achieve it:

1. Copy A to A' and sort A', O(n lg n)
2. Calculate Prefix Sum of A', store them in S, O(n)
3. Loop through A, for each element A_i, binary search the largest index j in A' such that A'[j] >= A_i, Ans[i] = S[j]

Ans is the array you want

Below is a sample C++ code illustrate the idea

#include<bits/stdc++.h>
using namespace std;

int A[6] = {4, 1, 3, 2, 3, 3}, B[6], SUM[6] = {0}, ANS[6];

int main(){
 for(int i=0; i<6; i++) B[i] = A[i];
 sort(B, B+6);
 for(int i=0; i<6; i++) SUM[i] = (i? SUM[i-1]:0) + B[i];
 
 for(int i=0; i<6;i++){
  int j = upper_bound(B,B+6, A[i]) - B;
  ANS[i] = SUM[j-1];
  printf("%d ", ANS[i]);
 }
 puts("");

 return 0;
}

Answer 4

The better approach could have been to sort the A to A' = [1, 3, 6, 9, 12, 16], then find the total sum of the integers and instead of cumsum, iterate over the array like below:

B[A.length-1] = sum;
for(int i=A.length-2; i=0; i++){
    if(A[i]!=A[i+1]){
        B[i] = sum - B[i+1];
    }
    else{
        B[i] = B[i+1];
    }
}

Answer 5

In the sorted approach, before storing the result, find all the elements with same value (which are now all consecutive, so this is the same traversal as you would have already been doing) and handle them all together: calculate the sum (same for all), then record the (same) result for each of them.