Skip to content

← leetcode

Valid Triangle Number

· Medium

LeetCode problem 611

To form a valid triangle, we need to have three numbers x, y and z such that x <= y <= z. In the triplet, there will always exist a z value; in other words, a value that is greater than or equal to every other value.

My algorithm decides to use index i to iterate through all possible z values, which is denoted by nums[i], and to keep two pointers:

  • l pointed at the smallest possible number in nums
  • r pointed at the largest possible number that is less than nums[i] in nums
    • complicated way of just saying r = i-1

Then, when we find a valid arrangment of l and r such that nums[i] < nums[l] + nums[r], that implies that for nums[r], the sum of it and any value between l and r-1 inclusive (e.g. num[l], nums[l+1], nums[l+2], ..., nums[r-1]) must be greater than nums[i]. Therefore, there exist r-l additional possible triangle formations and we can decrement r (to prevent it from being chosen again). Otherwise, we increment l.

We keep on repeating this until l >= r, as it implies we have found all possible triangle triplets with nums[i] as the largest value.

code

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int ans = 0;
        sort(nums.begin(), nums.end());
        for (int i = 2; i < nums.size(); ++i) {
            int l = 0, r = i-1;
            while (l < r) {
                if (nums[i] < nums[l] + nums[r]) {
                    ans += r-l;
                    --r;
                } else {
                    ++l;
                }
            }
        }
        return ans;
    }
};

complexity

  • Time: O(n^2) where n denotes the number of elements inside of nums
  • Space: O(1)

time taken

  • 14 minutes and 28 seconds