Triangle Numbers

nums = [11,4,9,6,15,18]

10

4, 15, 18
6, 15, 18
9, 15, 18
11, 15, 18
9, 11, 18
6, 11, 15
9, 11, 15
4, 9, 11
6, 9, 11
4, 6, 9

public class Solution {
    public Integer triangleNumber(int[] nums) {
        // Your code goes here
    }
}

Solution

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

Explanation

For three sides to form a valid triangle, all three of these conditions must be true:

• (a + b > c)
• (a + c > b)
• (b + c > a)

where (a), (b), and (c) are the three side lengths. This means the sum of every possible pair of sides must exceed the remaining side. For example, sides [1, 2, 1000] do NOT form a valid triangle because while (2 + 1000 > 1), the condition (1 + 2 > 1000) fails. By sorting the array, we can leverage the two-pointer technique to count all valid triplets in O(n²) time and O(1) space.

The key to this question is realizing that if we sort three numbers from smallest to largest (say a ≤ b ≤ c), we only need to check if a + b > c. If this condition holds, the other two conditions (a + c > b and b + c > a) are automatically satisfied because c ≥ b and b ≥ a. For example, with 4, 8, 9, if 4 + 8 > 9 is true, then we have a valid triplet.

But not only that, every number between 4 and 8 also forms a valid triplet when paired with 8 and 9. Since the array is sorted and 4 + 8 > 9, replacing 4 with any larger value (5, 6, 7, or 8) will still satisfy the condition — so all of these are valid triplets too.

This means that if we sort the input array, and then iterate from the end of the array to the beginning, we can use the two-pointer technique to efficiently count all valid triplets.

The pointers i, left, and right represent the current triplet we are considering. If nums[left] + nums[right] > nums[i], then every index from left to right - 1 also forms a valid triplet with right and i — because the array is sorted, so each of those values is at least as large as nums[left]. That gives us right - left valid triplets in one step. We then decrement right to look for valid triplets with a smaller middle value.

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

When nums[left] + nums[right] < nums[i], we know that all triplets between left and right are also invalid, so we increment left to look for a larger smallest value.

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

Each time left and right cross, we decrement i and reset left and right to their positions at opposite ends of the array. This happens until i is less than 2, at which point we have counted all valid triplets.

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