Why O(nlogn) solution getting TLE?



  1. Traverse the array taking each element “a” as the middle element.
  2. Maintain 2 ordered maps- “left” and “right”. “left” has all elements to the left of “a” and “right” has the right ones.
  3. Binary search “left” to get max element less than “a”. Similarly binary search “right” to get the max element greater than “a”. Return -inf if not possible.
  4. The two search result form a triplet with “a”. Compare this sum with maxSum;
  5. Return maxSum
    Time : O(nlogn)
    Space : O(n)