611. Valid Triangle Number¶

Difficulty: Medium

611. Valid Triangle Number

Medium

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

Solution¶

class Solution {
    public int triangleNumber(int[] nums) {
        int n = nums.length;
        int count = 0;
        Arrays.sort(nums);
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                int low = j + 1, high = n - 1, ansLeft = -1, ansRight = -1;
                while (low <= high) {
                    int mid = low + (high - low) / 2;
                    if (nums[i] + nums[mid] > nums[j]) {
                        ansLeft = mid;
                        high = mid - 1;
                    }
                    else 
                        low = mid + 1;
                }
                low = j + 1; high = n - 1;
                while (low <= high) {
                    int mid = low + (high - low) / 2;
                    if (nums[i] + nums[j] > nums[mid]) {
                        ansRight = mid;
                        low = mid + 1;
                    }
                    else high = mid - 1;
                }
                if (ansLeft == -1 || ansRight == -1) continue; 
                if (ansLeft <= ansRight) {
                    count += (ansRight - ansLeft + 1);
                }
            } 
        }
        return count;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here