Problem statement

https://leetcode.com/problems/valid-triangle-number/

Solution

Let n be number of our numbers. Then bruteforce solution is O(n^3). Another approach is to sort numbers and for each pair a_i and a_j, where i<j we need to find the biggest index k, such that a_k < a_i + a_j. It can be done with binary search with overall complexity O(n^2 * log n).

There is even better solution, using two pointers approach. Let us choose first index i. Then we need to find number of pairs (left, right) where left < right < i and a_{left} + a_{right} > a_i. Let us start with left = 1 and right = i-1. Then we can use Two Pointers approach to find number of desired pairs inO(n) for fixed i. Note, that it is very similar to all 2Sum or 3Sum problems.

Complexity

Time complexity is O(n^2), space complexity is O(1).

Code

class Solution:
    def triangleNumber(self, nums):
        nums, count, n = sorted(nums), 0, len(nums)
        for i in range(2, n):
            left, right = 0, i-1
            while left < right:
                if nums[left] + nums[right] > nums[i]:
                    count += (right - left)
                    right -= 1
                else:
                    left += 1
        return count