Valid Triangle Number

Problem Statement

Given an array nums of non-negative integers, count the number of triplets that can form a valid triangle (any two sides sum to more than the third).

Example

Input:  nums = [2,2,3,4]
Output: 3
Explanation: (2,3,4), (2,3,4), (2,2,3).

Two Pointer Approach

Sort first. Fix the largest side at index k, then use two pointers i and j below it. If nums[i] + nums[j] > nums[k], then every index between i and j also works, so add j - i and move j down; otherwise move i up.

Complexity

• Time: O(n^2)
• Space: O(1) extra

Solution Code

Python

def triangleNumber(nums):
    nums.sort()
    count = 0
    for k in range(len(nums) - 1, 1, -1):
        i, j = 0, k - 1
        while i < j:
            if nums[i] + nums[j] > nums[k]:
                count += j - i
                j -= 1
            else:
                i += 1
    return count

Java

int triangleNumber(int[] nums) {
    Arrays.sort(nums);
    int count = 0;
    for (int k = nums.length - 1; k >= 2; k--) {
        int i = 0, j = k - 1;
        while (i < j) {
            if (nums[i] + nums[j] > nums[k]) { count += j - i; j--; }
            else i++;
        }
    }
    return count;
}

C++

int triangleNumber(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    int count = 0;
    for (int k = (int)nums.size() - 1; k >= 2; k--) {
        int i = 0, j = k - 1;
        while (i < j) {
            if (nums[i] + nums[j] > nums[k]) { count += j - i; j--; }
            else i++;
        }
    }
    return count;
}

Key Takeaways

• With a sorted array, only the two smaller sides need checking.
• Counting j - i at once avoids an inner loop.
• A great example of turning an O(n^3) count into O(n^2).