We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Valid Triangle Number

Number: 611

Difficulty: Medium

Paid? No

Companies: Bloomberg, LinkedIn, Amazon, Google, Meta, Expedia

Problem Description

Given an integer array nums, the task is to count the number of triplets (i, j, k) that can form a valid triangle when taken as side lengths. A valid triangle must satisfy the triangle inequality property: the sum of any two sides must be greater than the third side.

Key Insights

  • Sorting the array simplifies meeting the triangle inequality condition.
  • Once sorted, if nums[left] + nums[right] > nums[k] for some triplet, then all elements between left and right with the current right will also satisfy the condition.
  • Using a two-pointer approach inside a loop iterating the largest side allows us to efficiently count valid pairs.
  • The innermost loop operates in O(n) time leading to a quadratic overall time complexity.

Space and Time Complexity

Time Complexity: O(n^2) due to the two nested loops iterating through the array. Space Complexity: O(1) or O(log n) if considering the sorting space overhead.

Solution

The solution begins by sorting the array. For each potential largest side (considered in reverse order), use two pointers (one starting at the beginning and another just before the largest side index) to find pairs of sides whose sum is greater than the largest side. When a valid pair is found, all numbers between the two pointers with the current right pointer also form valid triangles because the array is sorted. Increment the count accordingly and adjust the pointers until all possibilities are exhausted. This greedy two-pointer approach reduces the need for a three-nested loop, ensuring an efficient solution.

Code Solutions

# Python solution for Valid Triangle Number

def triangleNumber(nums):
    # First, sort the array to facilitate the two-pointer approach
    nums.sort()
    count = 0
    n = len(nums)
    
    # Iterate from the end of the array towards the beginning, selecting the largest side at position k
    for k in range(n - 1, 1, -1):
        left = 0          # Start pointer for the smallest side
        right = k - 1     # End pointer for the middle side
        
        # While the left pointer is less than the right pointer
        while left < right:
            # Check if the sum of the two smaller sides is greater than the largest side
            if nums[left] + nums[right] > nums[k]:
                # All indices from left to right-1 form a valid triangle with nums[right] and nums[k]
                count += right - left
                # Move the right pointer one step left to find a new pair
                right -= 1
            else:
                # Move the left pointer one step right to try and increase the sum
                left += 1
    return count

# Example usage:
# input_nums = [2,2,3,4]
# print(triangleNumber(input_nums))  # Expected output: 3
← Back to All Questions