medium Valid Triangle Number

Problem Statement

Given an array of integers nums, return the number of triplets we can make using array elements that can create triangle if we take them as side lengths of a triangle.

A set of three numbers can constitute a triangle if and only if the sum of any two sides is greater than the third side. This condition must hold true for all three combinations of summed sides.

Examples

• Example 1:

  • Input: nums = [4, 2, 3, 1]
  • Expected Output: 1
  • Justification: The valid combinations that can form a triangle are (2, 3, 4). The other combinations either do not meet the triangle inequality theorem or are duplicates in a different order.

• Example 2:

  • Input: nums = [5, 1, 3, 4, 7]
  • Expected Output: 3
  • Justification: There are 3 combinations that meet the triangle condition, such as (3, 4, 5), (3, 5, 7), (4, 5, 7) that satisfy the triangle inequality.

• Example 3:

  • Input: nums = [10, 21, 22, 100, 101, 200, 300]
  • Expected Output: 6
  • Justification: There are 6 combinations that meet the triangle condition, such as (10, 21, 22), (10, 100, 101), (21, 100, 101), (22, 100, 101), (100, 101, 200), and (101, 200, 300) that satisfy the triangle inequality.

Solution

To solve this problem, the most efficient approach involves sorting the input array and then using a two-pointer technique to count the triplets that satisfy the triangle inequality condition. Sorting the array allows us to apply the triangle inequality theorem more efficiently since we only need to check if the sum of the two smallest sides is greater than the largest side in a triplet. Once sorted, we iterate through the array, fixing one side as the longest side and using two pointers to find the other two sides of potential triangles.

This approach works because, for any sorted triplet where a <= b <= c, if a + b > c, then we know we have a valid triangle. By starting with the largest possible 'c' and finding 'a' and 'b' that meet the condition, we ensure that all possible combinations are accounted for without unnecessary repetition or missing any valid triplets.

Step-by-Step Algorithm

1. Sort the Input Array:

   • Begin by sorting the array in non-decreasing order. This is crucial because it allows us to use the triangle inequality theorem effectively, knowing that if nums[i] + nums[j] > nums[k], then any j' > j will also satisfy nums[i] + nums[j'] > nums[k], reducing the number of comparisons needed.

2. Initialize Count:

   • Set a counter variable count to 0. This will hold the number of valid triangles found.

3. Iterate through the Array with Three Pointers:

   • Use three pointers i, j, and k to iterate through the array. The pointer i starts from 0 to nums.length - 3, j starts from i + 1 to nums.length - 2, and k = i + 2 is used to find the first element that violates the triangle condition.

4. Find Valid Triangles:

   • For each fixed i and j, move k to find the first index where nums[i] + nums[j] <= nums[k]. The idea is that for each pair of i and j, any k between j + 1 and k - 1 (inclusive) will form a valid triangle, because nums[i] + nums[j] will be greater than nums[k] for those values, satisfying the triangle inequality theorem.

5. Update Count:

   • For each pair of i and j, add k - j - 1 to count. This represents the number of valid triangles formed with i and j as two sides.

6. Return the Count:

   • After iterating through all possible combinations, return the value of count.

Algorithm Walkthrough

Let's consider the Input: nums = [10, 21, 22, 100, 101, 200, 300].

1. Sort the array: The input array is already sorted, so we proceed with it as [10, 21, 22, 100, 101, 200, 300].

2. Initialize variables: Start with count = 0. We will update this count as we find valid triangles.

3. Iterate through the array with three pointers (i, j, k):

   • The idea is to fix the smallest side nums[i] and find pairs nums[j] and nums[k] that satisfy the triangle inequality: nums[i] + nums[j] > nums[k].

4. For i = 0 (nums[i] = 10):

   • Set j = i + 1 (j = 1, nums[j] = 21) and start the search for k.

   • Since k is initially set to i + 2, we start with k = 2.

   • Finding valid triangles:

     • When j = 1 (nums[j] = 21) and k = 2 (nums[k] = 22), the triangle inequality holds (10 + 21 > 22), so we increment k to find the next valid k.
     • Unable to find more valid k for this j, we move to the next j.

   • No additional valid triangles found for this i and j.

   • Update count = count + k - j - 1 = 0 + 3 - 1 - 1 = 1.

   • Update j to 2:

   • No valid triangles are found for i = 1, and j = 2.

   • For j = 3:

   • nums[0] + nums[3] > nums[4]. So, increment k to 5.

   • Update count = count + k - j - 1 = 1 + 5 - 3 - 1 = 2.

5. For i = 1 (nums[i] = 21):

   • For j = 2 (nums[j] = 22): No valid k because 22 + 21 cannot be greater than any subsequent number in the sorted list.
   • For j = 3 (nums[j] = 100):
     • The triangle inequality holds for k = 4 (nums[k] = 101) since 21 + 100 > 101. Update k = 5.
     • Update count = count + k - j - 1 = 2 + 5 - 3 - 1 = 3.
     • Continue incrementing j and complete the next iterations.

6. For i = 2 (nums[i] = 22):

   • For j = 3 (nums[j] = 100):
     • Similarly, the triangle inequality holds for k = 4 (nums[k] = 101) since 22 + 100 > 101. Update k = 5.
     • Update count = count + k - j - 1 = 3 + 5 - 3 - 1 = 4.
     • Continue incrementing j and complete the next iterations.

7. For i = 3 (nums[i] = 100):

   • For j = 4 (nums[j] = 101):
     • k = 5 (nums[k] = 200) satisfies 100 + 101 > 200. Update k = 6.
     • Update count = count + k - j - 1 = 4 + 6 - 4 - 1 = 5.
     • Continue incrementing j and complete the next iterations.

8. For i = 4 (nums[i] = 101):

   • For j = 5 (nums[j] = 200):
     • k = 6 (nums[k] = 300) satisfies 101 + 200 > 300. Update k = 7.
     • Update count = count + 7 - j - 1 = 5 + 7 - 5 - 1 = 6.

9. Final Result:

   • Total valid triplates are 6.

Code

import java.util.Arrays;

public class Solution {

  // Method to count the number of valid triangles
  public int triangleNumber(int[] nums) {
    Arrays.sort(nums); // Sort the array
    int count = 0;
    for (int i = 0; i < nums.length - 2; i++) { // Iterate through the array
      int k = i + 2;
      for (int j = i + 1; j < nums.length - 1 && nums[i] != 0; j++) { // Iterate from i+1 to nums.length-1
        while (k < nums.length && nums[i] + nums[j] > nums[k]) { // Iterate from k to nums.length
          k++; // Increment k if condition is met
        }
        count += k - j - 1; // Increment count by the difference between k and j-1
      }
    }
    return count; // Return the count of valid triangles
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    // Example 1
    System.out.println(solution.triangleNumber(new int[] { 4, 2, 3, 1 }));
    // Example 2
    System.out.println(solution.triangleNumber(new int[] { 5, 1, 3, 4, 7 }));
    // Example 3
    System.out.println(
      solution.triangleNumber(new int[] { 10, 21, 22, 100, 101, 200, 300 })
    );
  }
}

Complexity Analysis

Time Complexity

• Sorting: The initial sort operation has a time complexity of , where (N) is the number of elements in the input array.
• Finding Triplets: After sorting, the algorithm iterates over each element, using two pointers to find valid triangles. The outer loop runs in time, and for each iteration of the outer loop, the inner loop can iterate up to (N) times in the worst case. However, due to the two-pointer technique, each element is visited only once by the inner loop and the (k) pointer, resulting in an overall time complexity for this part.

Combining these parts, the total time complexity of the algorithm is = , as the term dominates for large (N).

Space Complexity

• Sorting Space: The space complexity of sorting is .
• Auxiliary Space: Apart from the space used for sorting, the algorithm only uses a constant amount of extra space for variables, resulting in an overall auxiliary space complexity of .

Therefore, the total space complexity of the algorithm is , primarily due to the sorting operation.