“This can be done in O(log N) time using set and storing prefix sum and the element in the set.”
what does this mean??
My prediction(most probably wrong approach as it may give TLE)
1)Sort the array
2)Binary search
3)Then find the point below which all elements A[v] + x <0
4)traverse the array from that point till this is not violated( A[v] + x <0 )
If I am right what i understood then i think in worst case answer order should O(n)?? as there may be case in which all elements in array satisfy(A[v] + x <0)
If i am wrong please explain the detail meaning of
“This can be done in O(log N) time using set and storing prefix sum and the element in the set.”
Hi Sunil!
I think you have slightly misinterpreted the statement. After point number 1,2,3… we will not be required to find a sum till the given index(as you’ve mentionaed in step 4).In fact ,the problem requires some preprocesing wherein we are going to store the prefix sum of the sorted array(as you mentioned)/set(as they mentioned).Both can be used alternatively so thats not an issue.
Note:(prefixsum[i]=arr[0]+arr[i]+…arr[i]).
So the log(N) complexity mentioned in the editorial is the complexity for step 3(binary search).And once we have found the index at this step,we already have our prefix sum calculated beforehand and hence no need for any traversal.
Hope this makes sense.
Correct me you if you find any mistake.
