algoadvance

Leetcode 611. Valid Triangle Number

Problem Statement

You are given an integer array nums representing the lengths of sides of triangles. You need to return the number of triplets chosen from the array that can make triangles if we take them as side lengths. A triangle is valid if the sum of any two sides is greater than the third side.

Example:

Explanation: The valid triplets are:

  1. (2, 3, 4)
  2. (2, 3, 4)
  3. (2, 2, 3)

Clarifying Questions

  1. Are all elements in the input array positive integers? Yes, the elements represent the lengths of the sides of triangles, so they will always be positive integers.

  2. How large can the input array be? The size of the array is up to 1000 elements.

  3. Do the elements of the array need to be distinct? No, elements in the array do not need to be distinct.

  4. What should be the output if there are no valid triangles? The output should be 0 in such a case.

Strategy

  1. Sorting:
    • First, sort the array. Sorting helps to simplify the logic for checking the triangle inequality condition.
  2. Two-Pointer Technique:
    • Use a two-pointer approach to count the valid triangles. For each element in the sorted array, treat it as the largest side of the triangle and find pairs that satisfy the triangle inequality condition.
  3. Triple Nested Loop:
    • Fix the largest side and use a nested loop to find pairs among the remaining sides such that they form a valid triangle with the largest side.

Algorithm:

  1. Sort the array.
  2. Iterate over the array from the end to the start, treating the current element (k-th) as the largest side of the triangle.
  3. For each k, use two pointers (i and j) to find all valid pairs (i, j) such that nums[i] + nums[j] > nums[k], where i < j < k.

Code:

public class ValidTriangleNumber {
    public int triangleNumber(int[] nums) {
        if (nums == null || nums.length < 3) {
            return 0;
        }
        
        // Sort the array
        Arrays.sort(nums);
        int count = 0;
        
        // Iterate over the array to consider each element as the largest side
        for (int k = nums.length - 1; k >= 2; k--) {
            int i = 0;
            int j = k - 1;
            
            // Use two pointers to find valid triangle sides
            while (i < j) {
                if (nums[i] + nums[j] > nums[k]) {
                    // If nums[i] + nums[j] > nums[k], all elements from nums[i] to nums[j-1] are also valid with nums[j] and nums[k]
                    count += j - i;
                    j--;
                } else {
                    // Move the left pointer to right if the condition is not satisfied
                    i++;
                }
            }
        }
        
        return count;
    }
}

Time Complexity:

Overall, the time complexity is O(n^2).

This solution should be efficient given the constraints, as it ensures that we correctly count all valid triangles in an optimal manner.

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