Valid Triangle Number

MEDIUM

Description

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.

Example 1:

Input: nums = [2,2,3,4]
Output: 3
Explanation: Valid combinations are: 
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3

Example 2:

Input: nums = [4,2,3,4]
Output: 4

Constraints:

1 <= nums.length <= 1000
0 <= nums[i] <= 1000

Approaches

Checkout 3 different approaches to solve Valid Triangle Number. Click on different approaches to view the approach and algorithm in detail.

Brute Force

The most straightforward approach is to check every possible triplet of numbers from the array and verify if they can form a valid triangle. This involves iterating through all combinations of three elements and applying the triangle inequality theorem.

Algorithm

Initialize a counter count to 0.
Use three nested loops to select three distinct indices i, j, and k from the array, such that i < j < k.
Let the side lengths be a = nums[i], b = nums[j], and c = nums[k].
For each triplet, check if it satisfies all three conditions of the triangle inequality theorem: a + b > c, a + c > b, and b + c > a.
If all conditions are met, increment the count.
After checking all possible triplets, return count.

This method uses three nested loops to generate all unique triplets (nums[i], nums[j], nums[k]) from the input array. For each triplet, we must verify that it can form a triangle. According to the triangle inequality theorem, the sum of the lengths of any two sides of a triangle must be greater than the length of the third side. Therefore, for a triplet (a, b, c) to be valid, it must satisfy a + b > c, a + c > b, and b + c > a. We maintain a counter, which is incremented for every triplet that satisfies these three conditions. While simple, this approach is very slow because it checks a number of triplets proportional to N cubed.

class Solution {
    public int triangleNumber(int[] nums) {
        int count = 0;
        int n = nums.length;
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (nums[i] + nums[j] > nums[k] && 
                        nums[i] + nums[k] > nums[j] && 
                        nums[j] + nums[k] > nums[i]) {
                        count++;
                    }
                }
            }
        }
        return count;
    }
}

Complexity Analysis

Time Complexity: O(N^3), where N is the number of elements in `nums`. The three nested loops result in a cubic number of checks.Space Complexity: O(1) extra space, as we only use a few variables to store indices and the count.

Pros and Cons

Pros:

Simple to understand and implement.
Does not require any modification to the input array.

Cons:

Extremely inefficient due to its cubic time complexity.
Likely to cause a 'Time Limit Exceeded' (TLE) error on platforms like LeetCode for the given constraints (N up to 1000).

Code Solutions

Checking out 3 solutions in different languages for Valid Triangle Number. Click on different languages to view the code.

class Solution {
public
  int triangleNumber(int[] nums) {
    Arrays.sort(nums);
    int n = nums.length;
    int res = 0;
    for (int i = n - 1; i >= 2; --i) {
      int l = 0, r = i - 1;
      while (l < r) {
        if (nums[l] + nums[r] > nums[i]) {
          res += r - l;
          --r;
        } else {
          ++l;
        }
      }
    }
    return res;
  }
}

Video Solution

Watch the video walkthrough for Valid Triangle Number

Algorithms:

Binary SearchSorting

Patterns:

Two PointersGreedy

Data Structures:

Array

Companies:

Expedia |LinkedIn |