Jobs

Interviews

Discussions

Valid Triangle Number

Medium

Amazon

2 views

Topics:

ArraysTwo Pointers

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.

For example:

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

Another example:

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

Constraints:

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

Write an efficient algorithm to solve this problem. Consider edge cases such as empty arrays or arrays with fewer than 3 elements. Explain the time and space complexity of your solution.

Valid Triangle Number

Medium

Amazon

2 views

Topics:

ArraysTwo Pointers

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.

For example:

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

Another example:

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

Constraints:

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

Write an efficient algorithm to solve this problem. Consider edge cases such as empty arrays or arrays with fewer than 3 elements. Explain the time and space complexity of your solution.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers in the input array?
Can the input array contain zero or negative numbers?
Are duplicate values allowed in the input array, and if so, should I consider them as distinct sides?
If no valid triangle can be formed, what should I return (e.g., 0, -1, null)?
What is the expected size of the input array; should I be concerned about integer overflow when calculating sums?

Brute Force Solution

Approach

To solve the problem using brute force, we'll check every possible combination of three numbers to see if they could form the sides of a valid triangle. This means testing all the different sets of three numbers we can pick from the given numbers. We verify the triangle inequality theorem for each of these combinations.

Here's how the algorithm would work step-by-step:

Consider all possible groups of three numbers from the given list of numbers.
For each group of three numbers, check if the sum of any two numbers is greater than the third number.
If, for a given group of three, all three of these 'sum greater than' conditions are met, then those three numbers can form a valid triangle. Count it.
After checking all possible groups of three numbers, return the total count of valid triangles that were found.

Code Implementation

def valid_triangle_number(numbers):
    number_of_valid_triangles = 0

    # Iterate through all possible combinations of three numbers
    for first_index in range(len(numbers)):
        for second_index in range(first_index + 1, len(numbers)):
            for third_index in range(second_index + 1, len(numbers)):
                first_side = numbers[first_index]
                second_side = numbers[second_index]
                third_side = numbers[third_index]

                # Check if the triangle inequality theorem holds
                if first_side + second_side > third_side and \
                   first_side + third_side > second_side and \
                   second_side + third_side > first_side:

                    # Increment the count if it's a valid triangle
                    number_of_valid_triangles += 1

    return number_of_valid_triangles

Big(O) Analysis

Time Complexity

O(n^3) – The provided brute force approach involves iterating through all possible combinations of three numbers from the input list of size n. This is equivalent to selecting 3 elements from n, which can be represented as n choose 3 (n C 3). The number of such combinations is proportional to n * (n-1) * (n-2). Simplifying, the dominant term becomes n^3. Therefore, the time complexity is O(n^3) because we are checking all possible triplets.

Space Complexity

O(1) – The brute force algorithm described in the plain English explanation iterates through the input list without creating any auxiliary data structures. It only uses a fixed number of variables to track the indices of the three numbers being considered and a counter for valid triangles. Therefore, the amount of extra memory used does not depend on the input size N, where N is the number of elements in the input list. This leads to a constant space complexity.

Optimal Solution

Approach

The key to efficiently finding valid triangle numbers is to sort the numbers first, then strategically consider triplets. We avoid unnecessary checks by leveraging the sorted order and a two-pointer technique.

Here's how the algorithm would work step-by-step:

First, arrange the numbers in increasing order from smallest to largest.
Then, start from the largest number and move backwards. Consider this the potential longest side of your triangle.
For each potential longest side, use two pointers, one starting at the beginning of the numbers and the other just before the longest side. These pointers will represent the two shorter sides of the potential triangle.
Move the pointers inwards. If the sum of the two shorter sides is greater than the longest side, it's a valid triangle. Count it, and move the right pointer inwards to see if you can find another valid triangle with a shorter second side.
If the sum of the two shorter sides is not greater than the longest side, it means the shorter sides aren't long enough. Move the left pointer outwards to find a longer first side.
Repeat these steps until the left and right pointers meet for the current longest side.
Move to the next largest number and repeat the entire process until you've considered all possible longest sides. The final count will give you the total number of valid triangles.

Code Implementation

def validTriangleNumber(nums):
    nums.sort()
    count = 0
    list_length = len(nums)

    for i in range(list_length - 1, 1, -1):
        # Start from the end to consider the longest side.
        longest_side_index = i

        left_side_index = 0
        right_side_index = longest_side_index - 1

        while left_side_index < right_side_index:
            # Pointers move until they meet.
            if nums[left_side_index] + nums[right_side_index] > nums[longest_side_index]:
                # Valid triangle found; increment count.
                count += right_side_index - left_side_index

                # Decrement right to find more valid triangles.
                right_side_index -= 1

            else:
                # Increment left to find a larger sum.
                left_side_index += 1

    return count

Big(O) Analysis

Time Complexity

O(n²) – The algorithm first sorts the input array of size n, which takes O(n log n) time. After sorting, the algorithm iterates through the array from the end, choosing each element as a potential longest side (O(n)). For each longest side, a two-pointer approach is used to find pairs of shorter sides that satisfy the triangle inequality. The two-pointer approach iterates at most n times for each longest side. Therefore, the nested loops contribute O(n * n) = O(n²) operations. Since O(n²) dominates O(n log n), the overall time complexity is O(n²).

Space Complexity

O(1) – The algorithm sorts the input array in place. It then uses a fixed number of integer variables like the index of the potential longest side and the left and right pointers for the two shorter sides. No auxiliary data structures whose size depends on the input size N (the number of elements in the input array) are created. Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately as no triangles can be formed.
Array with fewer than 3 elements	Return 0 immediately as a triangle needs 3 sides.
Array containing negative numbers	Filter out negative numbers since triangle sides cannot be negative.
Array containing zero values	Filter out zero values as a side length of zero is invalid for a triangle.
Array with all identical values (e.g., [5, 5, 5])	The algorithm should correctly identify the number of valid triangles that can be formed with those values.
Array with very large values potentially leading to integer overflow when summing	Use a data type with a larger range (e.g., long) to prevent integer overflow during the sum calculation.
Array already sorted in ascending order	The algorithm may not need to sort, or sorting might have optimal performance.
Array with duplicate values that could form multiple valid triangles using same side length values	The algorithm needs to count each unique combination of sides that satisfies triangle property.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers in the input array?
Can the input array contain zero or negative numbers?
Are duplicate values allowed in the input array, and if so, should I consider them as distinct sides?
If no valid triangle can be formed, what should I return (e.g., 0, -1, null)?
What is the expected size of the input array; should I be concerned about integer overflow when calculating sums?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Consider all possible groups of three numbers from the given list of numbers.
For each group of three numbers, check if the sum of any two numbers is greater than the third number.
If, for a given group of three, all three of these 'sum greater than' conditions are met, then those three numbers can form a valid triangle. Count it.
After checking all possible groups of three numbers, return the total count of valid triangles that were found.

Code Implementation

def valid_triangle_number(numbers):
    number_of_valid_triangles = 0

    # Iterate through all possible combinations of three numbers
    for first_index in range(len(numbers)):
        for second_index in range(first_index + 1, len(numbers)):
            for third_index in range(second_index + 1, len(numbers)):
                first_side = numbers[first_index]
                second_side = numbers[second_index]
                third_side = numbers[third_index]

                # Check if the triangle inequality theorem holds
                if first_side + second_side > third_side and \
                   first_side + third_side > second_side and \
                   second_side + third_side > first_side:

                    # Increment the count if it's a valid triangle
                    number_of_valid_triangles += 1

    return number_of_valid_triangles

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, arrange the numbers in increasing order from smallest to largest.
Then, start from the largest number and move backwards. Consider this the potential longest side of your triangle.
For each potential longest side, use two pointers, one starting at the beginning of the numbers and the other just before the longest side. These pointers will represent the two shorter sides of the potential triangle.
Move the pointers inwards. If the sum of the two shorter sides is greater than the longest side, it's a valid triangle. Count it, and move the right pointer inwards to see if you can find another valid triangle with a shorter second side.
If the sum of the two shorter sides is not greater than the longest side, it means the shorter sides aren't long enough. Move the left pointer outwards to find a longer first side.
Repeat these steps until the left and right pointers meet for the current longest side.
Move to the next largest number and repeat the entire process until you've considered all possible longest sides. The final count will give you the total number of valid triangles.

Code Implementation

def validTriangleNumber(nums):
    nums.sort()
    count = 0
    list_length = len(nums)

    for i in range(list_length - 1, 1, -1):
        # Start from the end to consider the longest side.
        longest_side_index = i

        left_side_index = 0
        right_side_index = longest_side_index - 1

        while left_side_index < right_side_index:
            # Pointers move until they meet.
            if nums[left_side_index] + nums[right_side_index] > nums[longest_side_index]:
                # Valid triangle found; increment count.
                count += right_side_index - left_side_index

                # Decrement right to find more valid triangles.
                right_side_index -= 1

            else:
                # Increment left to find a larger sum.
                left_side_index += 1

    return count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately as no triangles can be formed.
Array with fewer than 3 elements	Return 0 immediately as a triangle needs 3 sides.
Array containing negative numbers	Filter out negative numbers since triangle sides cannot be negative.
Array containing zero values	Filter out zero values as a side length of zero is invalid for a triangle.
Array with all identical values (e.g., [5, 5, 5])	The algorithm should correctly identify the number of valid triangles that can be formed with those values.
Array with very large values potentially leading to integer overflow when summing	Use a data type with a larger range (e.g., long) to prevent integer overflow during the sum calculation.
Array already sorted in ascending order	The algorithm may not need to sort, or sorting might have optimal performance.
Array with duplicate values that could form multiple valid triangles using same side length values	The algorithm needs to count each unique combination of sides that satisfies triangle property.