Code Implementation

class Solution:
    def triangleNumber(self, nums):
        nums.sort()
        n = len(nums)
        count = 0
        for k in range(n - 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
      

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

class Solution {
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length, count = 0;
        for (int k = n - 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;
    }
}
      

var triangleNumber = function(nums) {
    nums.sort((a, b) => a - b);
    let n = nums.length, count = 0;
    for (let k = n - 1; k >= 2; --k) {
        let i = 0, j = k - 1;
        while (i < j) {
            if (nums[i] + nums[j] > nums[k]) {
                count += j - i;
                --j;
            } else {
                ++i;
            }
        }
    }
    return count;
};
      

Problem Description

Given an array of non-negative integers nums, where each element represents the length of a side of a triangle, determine how many triplets of indices (i, j, k) (with i < j < k) can form a valid triangle. A triplet forms a valid triangle if the sum of any two side lengths is greater than the third side length. Each element in nums can be used only once per triplet, and the same triplet should not be counted multiple times.

Key constraints:

• Each triplet must use three distinct elements from nums.
• Triangle inequality must be satisfied: nums[i] + nums[j] > nums[k], nums[i] + nums[k] > nums[j], and nums[j] + nums[k] > nums[i].
• Input size: 1 <= nums.length <= 1000, 0 <= nums[i] <= 1000

Thought Process

To solve this problem, we start by recognizing that for any three numbers to form a triangle, the sum of any two must be greater than the third. The brute-force approach would be to check all possible triplets in the array, but this would be inefficient for large arrays (as there are O(n³) triplets).

To optimize, we notice that if we sort the array, the largest side in any triplet will always be at the highest index. This lets us focus on the condition nums[i] + nums[j] > nums[k] (since the other two conditions are guaranteed by the sorting order). Using two pointers, we can efficiently find all valid pairs for each possible largest side.

The key insight is that, by sorting, we can fix the largest side and search for pairs in the remaining array using a two-pointer approach, reducing the time complexity dramatically.

Solution Approach

We use the following steps to efficiently count the number of valid triangles:

1. Sort the array. Sorting ensures that for any triplet (i, j, k) with i < j < k, nums[k] is the largest side.
2. Iterate from the end. For each index k from n-1 down to 2, treat nums[k] as the largest side.
3. Use two pointers. Set i = 0 and j = k-1. While i < j:
   • If nums[i] + nums[j] > nums[k], then all pairs between i and j are valid for this k, so increment the count by j - i and move j leftward.
   • Otherwise, increment i rightward to try a larger value.
4. Continue for all possible largest sides. This checks all valid triplets efficiently.

This approach leverages sorting and two pointers to reduce the number of checks from O(n³) to O(n²).

Example Walkthrough

Let's walk through the algorithm with a sample input: nums = [2, 2, 3, 4]

• After sorting: [2, 2, 3, 4]
• Set k = 3 (nums[3] = 4), i = 0, j = 2:
  • Check nums[0] + nums[2] = 2 + 3 = 5 > 4 → valid. All pairs between i and j are valid (since nums[1] + nums[2] = 2 + 3 = 5 > 4 as well). So we add j - i = 2 to our count and move j to 1.
  • Now, i = 0, j = 1:
    • nums[0] + nums[1] = 2 + 2 = 4 (not greater than 4), so increment i to 1.
  • Loop ends for k = 3.
• Set k = 2 (nums[2] = 3), i = 0, j = 1:
  • nums[0] + nums[1] = 2 + 2 = 4 > 3 → valid. Add j - i = 1 to count.
• Final count: 2 + 1 = 3 valid triangles: (2,3,4), (2,3,4) (with different indices), and (2,2,3).

Time and Space Complexity

• Brute-force approach: O(n³) time, O(1) extra space. Checks every triplet individually.
• Optimized approach (sorting + two pointers):
  • Sorting takes O(n log n) time.
  • The two-pointer search for each k takes O(n) time, and we do this for each k, so total time is O(n²).
  • Extra space is O(1) (ignoring the space used by sorting, which can be O(n) depending on the language).

This optimization makes the solution feasible for input sizes up to 1000.

Summary

By sorting the array and using the two-pointer technique, we efficiently count all valid triangle triplets in O(n²) time. The key insight is that sorting allows us to always treat the largest side last, and for each such side, quickly determine how many pairs of smaller sides can combine with it to form a triangle. This approach is both elegant and practical, making it suitable for large input sizes.