Valid Triangle Number LeetCode Solution

Difficulty Level Medium
Frequently asked in Amazon Apple Bloomberg ByteDance Expedia LinkedIn Robinhood UberViews 1492

Problem Statement:

Valid Triangle Number LeetCode Solution says – 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.

Valid Triangle Number LeetCode Solution

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

Explanation:

The approach is similar to any binary search problem where you want to find value in an array without traversing(in our case third valid side calls it ‘c’).
So there are 2 ways to do this

  1. Hashmap get required value in O(1)
  2. Binary search O(log n)

Case 1 does not work for us as we don’t want an exact sum but elements less than a certain threshold(a+b).
So to conclude for every side we need to find b,c such that it forms a valid triangle that’s where 2 pointer comes into the picture.

Code-

Valid Triangle Number C++ Solution:

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int n=size(nums),count=0;
        sort(nums.begin(), nums.end());
        
        //basically we will be finding valid pair for ith value
        for(int i=2;i<n;i++){
            int left=0,right=i-1;
            while(left < right){
                if(nums[left]+nums[right] > nums[i]){
                    count += right-left;
                    right--; // imp to note check explanation
                }
                else{
                    left++;
                }
            }
        }
        return count;
    }};

Valid Triangle Number Java Solution:

class Solution 
{
    public int triangleNumber(int[] nums) 
    {
        Arrays.sort(nums);
        int ans=0;
        
        for(int i=0;i<nums.length;i++)
        {
            for(int j=i+1;j<nums.length;j++)
            {
                int pos=binarySearch(nums,j+1,nums.length-1,nums[i]+nums[j]-1);
                if(pos!=-1)
                ans+=pos-j;
            }
        }
        
        return ans;
    }
    
    public int binarySearch(int nums[],int start,int end,int target)
    {
        int ans=-1;
        
        while(start<=end)
        {
            int mid=start+(end-start)/2;
            
            if(nums[mid]<=target)
            {
                ans=mid;
                start=mid+1;
            }
            
            else
            {
                end=mid-1;
            }
        }
        
        return ans;
    }
}

Complexity Analysis of Valid Triangle Number Leetcode Solution:

Time complexity- O(n): Due to binary search
Space complexity- O(1)

Translate Ā»