3

Given an array that contains positive integers. The task is to calculate the number of triplets a, b, c such that they can be the sides of a triangle or

max(a, b, c) < a + b + c - max(a, b, c)

the O(N^3) solution is trivial using 3 loops, O(N^2) is simple enough to iterate over from the end of the sorted array and find a valid range satisfying the triangle inequality. But is it possible to find the count from a sorted array in linear time by iterating and fixing the middle length?

anand singh
  • 103
  • 7
  • Shouldn't this be true for all cases except when atleast two of a,b,c are zero ? – Avinash Thakur Jul 15 '21 at 17:07
  • @AvinashThakur, positive integers doesn't constitute zero – anand singh Jul 15 '21 at 17:15
  • `is it possible` .. y not ? how different is `find the count from a sorted array` than `find the count from a for loop/generator` ? – p._phidot_ Jul 15 '21 at 18:29
  • Your title and question ask two different questions. So which is it going to be? Linear or `O(n lg n)`? `O(n lg n)` is definitely doable, `O(n)` not so much, unless additional constraints are imposed on the input. –  Jul 15 '21 at 18:32
  • @Paul O(N log N) is for sorting is upper bound for time complexity – anand singh Jul 15 '21 at 19:37
  • 1
    @anandsingh not quite. `O(n lg n)` is the upper bound for *comparison*-sorting. There's also e.g. counting- and radix-sort, which both are faster, albeit only for specific scenarios. Either way, i take it that in your question with "linear time" you actually meant `O(n lg n)`? –  Jul 15 '21 at 20:54
  • @Paul how do you do O(n log n)? My intuition on first seeing this problem is that it's 3SUM-hard, but I haven't worked out the details of a reduction. – David Eisenstat Jul 16 '21 at 17:14
  • This is actually a duplicate of https://stackoverflow.com/q/39855682/1413244 but not voting to close because that question did not get a good answer and because the answerers all took the question to mean count the triangles *and list them* which is O(n^3) because it is possible for all triples to be a legal triangle so then just to list the n choose 3 triangles is O(n^3), even though the text of the question just asks for the count. – jwezorek Jul 23 '21 at 00:25

0 Answers0