I have a sorted list , lets say 1, 6 , 10 ,15 ,16 , 18, 30, 50.

How do I find first three items which are in the less than interval of n, say 3.

For example in the above list, 15, 16 and 18 is the answer. Is it possible to get to this in better than O(n) ?

  • 2
    Do I need sleep or does this make no sense? "in the less than interval of n"? Aug 23, 2016 at 2:53
  • Worst case is O(n). Average case is probably O(n/2), which is also O(n) if you don't know anything about the data set. If you want better, I think you'd have to look at the bigger picture and try to solve a more encompassing problem, which would then include how those numbers (the sorted lists) are generated, and maybe even why you want those specific result. Sometimes you can do very interesting things if you solve a specific enough, larger/real-world problem instead of a harder general problem.
    – Erik Eidt
    Aug 23, 2016 at 5:24

1 Answer 1


Can you not just subtract a[2]-a[0] and see if less then N. If so, there's your answer. If not, try a[3]-a[1] and see if less then N. Iterate until you find it or run out. Potentially requires N-2 comparisons.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.