Number of possible triangles from an integer array in O(NlogN)

411 Views Asked by At

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?

0

There are 0 best solutions below