CareerCup

1. Sort the array in non descending order.
2. For each i in [0, N), calculate the ans as sum of all the waters before that + (water used if all the subsequent buckets are made equal to ith one). Second thing can be calculated using something like suffix sum
3. Minimise the result you are getting above to get the answer.

1.) sort the array(waters array) in descending order.
2.)Assuming every bucket as candidate find the minimum amount of water need to be removed.Result will be minimum amount of water among that.
3.)Every bucket which is in left of current bucket have more water than current bucket and every bucket which is in right of current bucket have less water than current bucket.
4.)For every bucket we remove all the bucket on its right and some amount of water from all the bucket on its left(they have more water).
5.)Amount of water removed can be calculated using (total_water - waters[i]*(i+1)).
5.) res = min(res, total_water - waters[i]*(i+1)).
6.)Time complexity - O(n) and Space Complexity - O(1)

int minLitreRemoved(vector<int>&waters){
    //sort the array
    sort(waters.begin(),waters.end(),greater<int>());//sort in descending order
    int res = INT_MAX;
    int total_water = 0;//stores sum of litres of water from all bucket
    for(auto bucket : waters){
        total_water += bucket;
    }
    for(int i=0;i<waters.size();i++){
        res = min(res, total_water - waters[i]*(i+1));//i+1 bucket will have atleast water[i] height.(sorted in descending order)
    }
    return res;
}

1.) sort the array(waters array) in descending order.
2.)Assuming every bucket as candidate find the minimum amount of water need to be removed.Result will be minimum amount of water among that.
3.)Every bucket which is in left of current bucket have more water than current bucket and every bucket which is in right of current bucket have less water than current bucket.
4.)For every bucket we remove all the bucket on its right and some amount of water from all the bucket on its left(they have more water).
5.)Amount of water removed can be calculated using (total_water - waters[i]*(i+1)).
5.) res = min(res, total_water - waters[i]*(i+1)).
6.)Time complexity - O(n) and Space Complexity - O(1)

int minLitreRemoved(vector<int>&waters){
    //sort the array
    sort(waters.begin(),waters.end(),greater<int>());//sort in descending order
    int res = INT_MAX;
    int total_water = 0;//stores sum of litres of water from all bucket
    for(auto bucket : waters){
        total_water += bucket;
    }
    for(int i=0;i<waters.size();i++){
        res = min(res, total_water - waters[i]*(i+1));//i+1 bucket will have atleast water[i] height.(sorted in descending order)
    }
    return res;
}

1.) sort the array(waters array) in descending order.
2.)Assuming every bucket as candidate find the minimum amount of water need to be removed.Result will be minimum amount of water among that.
3.)Every bucket which is in left of current bucket have more water than current bucket and every bucket which is in right of current bucket have less water than current bucket.
4.)For every bucket we remove all the bucket on its right and some amount of water from all the bucket on its left(they have more water).
5.)Amount of water removed can be calculated using (total_water - waters[i]*(i+1)).
5.) res = min(res, total_water - waters[i]*(i+1)).
6.)Time complexity - O(n) and Space Complexity - O(1)

int minLitreRemoved(vector<int>&waters){
    //sort the array
    sort(waters.begin(),waters.end(),greater<int>());//sort in descending order
    int res = INT_MAX;
    int total_water = 0;//stores sum of litres of water from all bucket
    for(auto bucket : waters){
        total_water += bucket;
    }
    for(int i=0;i<waters.size();i++){
        res = min(res, total_water - waters[i]*(i+1));//i+1 bucket will have atleast water[i] height.(sorted in descending order)
    }
    return res;
}

1.) sort the array(waters array) in descending order.
2.)Assuming every bucket as candidate find the minimum amount of water need to be removed.Result will be minimum amount of water among that.
3.)Every bucket which is in left of current bucket have more water than current bucket and every bucket which is in right of current bucket have less water than current bucket.
4.)For every bucket we remove all the bucket on its right and some amount of water from all the bucket on its left(they have more water).
5.)Amount of water removed can be calculated using (total_water - waters[i]*(i+1)).
5.) res = min(res, total_water - waters[i]*(i+1)).
6.)Time complexity - O(n) and Space Complexity - O(1)

int minLitreRemoved(vector<int>&waters){
    //sort the array
    sort(waters.begin(),waters.end(),greater<int>());//sort in descending order
    int res = INT_MAX;
    int total_water = 0;//stores sum of litres of water from all bucket
    for(auto bucket : waters){
        total_water += bucket;
    }
    for(int i=0;i<waters.size();i++){
        res = min(res, total_water - waters[i]*(i+1));//i+1 bucket will have atleast water[i] height.(sorted in descending order)
    }
    return res;
}

Above solutions won't work in case of duplicate elements.
And complexity of above solutions is not O(n) because sorting the array will definitely take more than that

A.sort()
n = len(A)
pref = [0]*n
suff = [0]*n
pref[0] = A[0]
suff[-1] = A[-1]

for i in range(1,n):
pref[i] = A[i] + pref[i-1]
suff[n-1-i] = A[n-i-1] + suff[n-i]

res = 10**9 + 7
for i in range(n):
if i == 0:
res = min(res,suff[i+1] - A[i]*(n-i-1))
elif i == n-1:
res = min(res,pref[i-1])
else:
res = min(res,pref[i-1] + suff[i+1] - A[i]*(n-i-1))
return res

A.sort()
n = len(A)
pref = [0]*n
suff = [0]*n
pref[0] = A[0]
suff[-1] = A[-1]

for i in range(1,n):
    pref[i] = A[i] + pref[i-1]
    suff[n-1-i] = A[n-i-1] + suff[n-i]

res = 10**9 + 7
for i in range(n):
    if i == 0:
        res = min(res,suff[i+1] - A[i]*(n-i-1))
    elif i == n-1:
        res = min(res,pref[i-1])
    else:
        res = min(res,pref[i-1] + suff[i+1] - A[i]*(n-i-1))
return res