LeetCode 611: Valid Triangle Number

link

A triplet is a 3-element subset like $\{ \texttt{nums}[i], \texttt{nums}[j], \texttt{nums}[k] : i \ne j \ne k \}$ . Therefore, different ordering of the three elements does not make a different triplet. In other words, all six permutations of the three elements are counted as the same triplet.

A triplet is trianglular if the three numbers in it respect the geometric triangular property: sum of any two must be bigger than the remaining.

Brute Force

Check all distinct triplets. Count-wise: ${{n}\choose{3}} = \frac{{{n}\choose{1}} \cdot {{n-1}\choose{1}} \cdot {{n-3}\choose{1}}}{3!}$ .

Time: $\mathcal{O}(n^3)$ , space: $\mathcal{O}(1)$ .

class Solution:
    def is_triangular(self, triplet) -> bool:
        triplet.sort()
        return triplet[0]+triplet[1] > triplet[2]

    def triangleNumber(self, nums: List[int]) -> int:
        count, n = 0, len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    count += (1 if self.is_triangular([nums[i], nums[j], nums[k]]) else 0)
        return count

Sorted nums

Once we have the smallest two elements $a$ and $b$ of a triplet, we need to count $c$ ‘s such that $a+b > c$ . With a sorted nums, we can thus replace the innermost loop with a binary-search.

Time: $\mathcal{O}(n^2 \cdot \lg{n})$ . Space is that of sorting.

class Solution:
    def find_rightmost_index(self, x, nums, begin) -> int:
        lo, hi = begin, len(nums)-1
        pos = begin-1
        while lo <= hi:
            mid = (lo+hi) // 2
            if nums[mid] < x:
                pos = mid
                lo = mid+1
            else:
                hi = mid-1
        return pos

    def triangleNumber(self, nums: List[int]) -> int:
        nums.sort()
        count, n = 0, len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                two_sum = nums[i] + nums[j]
                pos = self.find_rightmost_index( two_sum, nums, (begin := j+1) )
                count += (pos-begin+1)
        return count

Reverse sorted nums

With nums sorted in reverse, the outer loop will enumerate the largest ( $c$ ) of the three elements in the triplet. The other two elements $a$ and $b$ must satisfy: $a+b > c$ . We can count all valid pairs for $(a, b)$ in a linear scan.

Time is $\mathcal{O}(n^2)$ . Space is that for sorting.

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        nums.sort(reverse=True)
        count, n = 0, len(nums)
        for i in range(n):
            biggest = nums[i]
            # nums[k] is smallest
            j, k = i+1, n-1
            while j < k:
                two_sum = nums[j] + nums[k]
                # Violates triangle property
                if two_sum <= biggest:
                    k -= 1
                else:
                    count += (k-j)
                    j += 1

        return count

unreasonably effective