Need help regarding this question. This is the problem
I’m using O(n) solution for this still I’m not able to pass the advanced test cases. Could you please point out how it’s taking long execution time for some test cases and more importantly how can this be resolved.
n,k=map(int,input().split())
li=list(map(int,input().split()))
count=0
li.sort()
i=0
j=1
while(i<n and j<n):
if(abs(li[i]-li[j])>=k):
count+=(n-j)
i+=1
j=i+1
else:
j+=1
print(count)
First of all this is not O(n). Sorting takes O(nlogn) and your loop’s worst case is O(n^2). Secondly , suppose that for some li[i], you do not find any li[j], then is there any need to check further? Also, use fast i/o.
I agree sort() function’s worst case is nlogn but how the loop is O(n^2) ? Also j is the index which always represents an element one or more index greater than the current index(i). If there is any possibility that i is the last element then j will be greater than n so the loop terminates automatically.
Ok I understood how loop’s worst case is n^2
I’m saying that suppose you didn’t find any elment for li[i]. Is there any need to check for li[i+1], li[i+2], … ?
Since the list is in ascending order so if the list is like 1,1,3 and k=1 so for 1 and 1 we didn’t get count as 1(still 0) but when we progress i, 1 and 3 we’ll get the count increased. Since the list is in ascending order it means if i’m not meeting the conditions at the starting then I’ll meet condition on forward iterations
Suppose the input is
5 6
2 3 11 13 15 16
When you will iterate for 11, none of the elements 13, 15 and 16 will satisfy the condition. So, no element pairs up with 11 (except for pairs 2-11 and 3-11 which were found in previous iterations). Now since you didn’t find any pairable element for 11, would it make sense to iterate 13, 15 and 16 ?
Makes sense now, but this method is still having large complexity.