algoadvance

Leetcode 611. Valid Triangle Number

Problem Statement

Given an integer array nums, return the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.

A triplet (i, j, k) can form a triangle if:

• nums[i] + nums[j] > nums[k]
• nums[i] + nums[k] > nums[j]
• nums[j] + nums[k] > nums[i]

Clarifying Questions

1. What is the range of values in the input array?
   • The values can be any positive integers.
2. What is the range of the length of the input array?
   • Typically, problems do not constrict this, but it can be reasonable to assume it fits within usual problem constraints (e.g., the length of nums might be up to around 10^3 to 10^4).
3. Can the array contain duplicate values?
   • Yes, the array might contain duplicate values.
4. Are the array elements always positive?
   • Yes, since they represent potential triangle sides, they will be positive integers.

Strategy

1. Sort the Array:
   • Sorting the array helps in easily checking the triangle inequality.
2. Two-pointer Technique:
   • Iterate through the array with three nested loops where the outermost loop fixes the largest side of the triangle. The two inner pointers attempt to find valid combinations for the other two sides.
3. Check Validity:
   • For a fixed k (largest side), use two pointers (i starting from 0 and j starting from k-1) to find if nums[i] + nums[j] > nums[k]. If such a combination is found, all elements between i and j-1 with j will also form a valid triangle due to sorting.

Code

#include <vector>
#include <algorithm>

class Solution {
public:
    int triangleNumber(std::vector<int>& nums) {
        std::sort(nums.begin(), nums.end());
        
        int count = 0;
        
        for (int k = 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;
    }
};

Time Complexity

• Sorting the array: (O(n \log n))
• Two-pointer iteration: (O(n^2)) in the worst case since for each fixed k, the pointers i and j are iterated over the remaining array.

Therefore, the total time complexity of this approach is (O(n^2)), which is efficient for typical constraints on input size (n).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?