611. Valid Triangle Number

MediumGreedyArrayTwo PointersBinary SearchSorting
Leetcode Link

Problem Description

The problem presents us with an integer array nums and asks us to find the count of all possible triplets in this array that can form a valid triangle. A set of three numbers forms the sides of a triangle if and only if the sum of any two sides is greater than the third side. This is known as the triangle inequality theorem.

Intuition

To solve this problem, we can start by sorting the array. Sorting helps us to apply the triangle inequality more effectively by having an ordered list to work with. In this way, when we pick two numbers, the smaller two sides of a potential triangle, we already know that any number following them in the array will be greater or equal than these two.

Once we have the sorted array, the intuition behind the solution is as follows:

  • The outer loop picks the first side a of the potential triangle.
  • The second, inner loop picks the second side b, which is just the next number in the sorted array after the first side.
  • Using the triangle inequality theorem, we know that in order to form a triangle, the third side c must be less than the sum of a and b but also greater than their difference. Since the array is sorted and we only need the sum condition ("less than the sum"), we can use binary search to quickly find the largest index k such that nums[k] is less than the sum of nums[i] plus nums[j] (where nums[i] is the first side and nums[j] is the second side).

With this approach, for each pair of a and b, binary search helps us find the count of possible third sides. We then subtract the index of the second side j from k to get the number of valid third sides c, and add this to our answer ans. We repeat this process until we have considered all possible pairs of sides a and b.

To sum up, the solution uses a combination of sorting, iterating through pairs of potential sides, and binary search to efficiently calculate the number of valid triangles that can be formed from the array.

Learn more about Greedy, Two Pointers, Binary Search and Sorting patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Solution Approach

The solution begins with sorting the array nums. Sorting is a critical step because it allows us to take advantage of the triangle inequality in a sorted sequence, which makes it easier to reason about the relationship between the sides. With sorting, we guarantee that if nums[i] and nums[j] (where i < j) are two sides of a potential triangle, then any nums[k] (where k > j) is at least as large as nums[j]. This means that for the triangle inequality to be satisfied (nums[i] + nums[j] > nums[k]), we only need to find the first k where the inequality does not hold and then all indices before k will form valid triangles with nums[i] and nums[j].

Here is how the solution is implemented:

  • After sorting, a for loop is used to iterate through the array as the outer loop. This loop starts from the first element and stops at the third-to-last element, with i representing the index of the first side of a potential triangle.

  • Inside the outer loop, a nested for loop starts from i+1, iterates over the remaining elements, and stops at the second-to-last element, with j representing the index of the second side of a potential triangle.

  • For each pair of sides represented by nums[i] and nums[j], binary search is used to find the right-most element which could be a candidate for the third side of the triangle. The bisect_left function from the Python bisect module is used to find the index k, where nums[k] is the smallest number greater than or equal to the sum of nums[i] and nums[j]. Since nums[k] itself cannot form a triangle with nums[i] and nums[j] (it's not strictly less than the sum), we subtract one to get the index of the largest valid third side.

  • Now with k-1 being the largest index of a valid third side and j the index of the second side, all numbers in the range (j, k) will satisfy the triangle inequality. Thus, ans (the count of valid triangles) is incremented by k - j - 1.

  • By the end of these loops, ans will contain the total number of triplets that can form valid triangles.

The solution applies the sorting algorithm, iteration through nested loops, and binary search to solve the problem efficiently.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

A heap is a ...?

Example Walkthrough

Let's apply our solution approach on a small example array, nums = [4, 2, 3, 4].

First, we sort the array to get nums = [2, 3, 4, 4]. Sorting helps us apply the triangle inequality theorem effectively.

Next, we begin our outer loop with i = 0, where nums[i] = 2.

Inside our outer loop, we start our inner loop with j = i + 1, which makes j = 1, and nums[j] = 3.

For nums[i] = 2 and nums[j] = 3, we perform a binary search to find the largest index k where nums[k] is less than the sum of nums[i] and nums[j], which is 2 + 3 = 5. In this sorted array, nums[k] could be either 4 or 4, both are less than 5. Binary search finds that k = 3 (the last index of 4 in the sorted array). Since the actual element at k cannot be part of the triangle, to get the largest valid k, we subtract one from it, making k = 2.

Now we calculate the number of valid c sides between j and k, which is k - j - 1 = 2 - 1 - 1 = 0. There is no third side that can form a triangle with nums[i] = 2 and nums[j] = 3.

Next, we increment j to 2, making nums[j] = 4, and repeat the binary search. This finds that k = 3 (as 4 + 4 is not less than any element in the array). Subtracting one from k gives us k = 2. The number of valid third sides c is k - j - 1 = 2 - 2 - 1 = -1. No valid triangle can be formed in this case as well.

Then we increment i to 1 and j to i + 1 which is 2, and now we have nums[i] = 3 and nums[j] = 4. Repeating the binary search for the sum 3 + 4 = 7, we find that no such k exists since all existing elements are less than 7. Thus, k is the length of the array, k = 4. And the number of valid c sides is k - j - 1 = 4 - 2 - 1 = 1, so we can form one triangle using the indices (1, 2, 3).

Our next pair would be nums[i] = 3 and nums[j] = 4 (again, but with j = 3), but since there's no element after nums[j] when j = 3, we cannot form a triangle, and the process stops here.

Therefore, through our example, we found only one valid triplet (3, 4, 4) which can form a triangle. Our answer ans would be 1 for this example.

Solution Implementation

1from bisect import bisect_left
2
3class Solution:
4    def triangleNumber(self, nums: List[int]) -> int:
5        # First, sort the input array to arrange numbers in non-decreasing order
6        nums.sort()
7      
8        # Initialize the answer and get the length of the array
9        triangle_count, n = 0, len(nums)
10      
11        # Loop over each triple. For triangles, we just need to ensure that
12        # the sum of the lengths of any two sides is greater than the length of the third side.
13        for i in range(n - 2):  # The last two numbers are not needed as they are candidates for the longest side of the triangle
14            for j in range(i + 1, n - 1):  # j is always after i
15              
16                # Find the index of the smallest number that is greater than
17                # the sum of nums[i] and nums[j] using binary search.
18                # This determines the right boundary of possible valid triangles.
19                # We subtract 1 because bisect_left returns the index where we could insert the
20                # number keeping the list sorted, but we want the last valid index.
21                k = bisect_left(nums, nums[i] + nums[j], lo=j + 1) - 1
22              
23                # The count of triangles for this specific (i, j) pair is k - j
24                # because any index between j and k (exclusive) can be chosen as the
25                # third side of the triangle.
26                triangle_count += k - j
27
28        # Return the total count of triangles that can be formed
29        return triangle_count
30
1class Solution {
2    public int triangleNumber(int[] nums) {
3        // Sort the array in non-decreasing order
4        Arrays.sort(nums);
5        int count = nums.length;
6        // Initialize result to 0
7        int result = 0;
8
9        // Iterate over the array starting from the end
10        for (int i = count - 1; i >= 2; --i) {
11            // Set two pointers, one at the beginning and one before the current element
12            int left = 0, right = i - 1;
13
14            // Iterate as long as left pointer is less than right pointer
15            while (left < right) {
16                // Check if the sum of the elements at left and right pointers is greater than
17                // the current element to form a triangle
18                if (nums[left] + nums[right] > nums[i]) {
19                    // If condition is satisfied, we can form triangles with any index between left and right
20                    result += right - left;
21                    // Move the right pointer downwards
22                    --right;
23                } else {
24                    // If condition is not satisfied, move the left pointer upwards
25                    ++left;
26                }
27            }
28        }
29        // Return the total count of triangles found
30        return result;
31    }
32}
33
1class Solution {
2public:
3    int triangleNumber(vector<int>& nums) {
4        // Sort the numbers in non-decreasing order
5        sort(nums.begin(), nums.end());
6
7        // Initialize the count of triangles
8        int count = 0;
9      
10        // The total number of elements in the vector
11        int n = nums.size();
12      
13        // The outer loop goes through each number starting from the first until the third last
14        for (int i = 0; i < n - 2; ++i) {
15          
16            // The second loop goes through numbers after the current number chosen by the outer loop
17            for (int j = i + 1; j < n - 1; ++j) {
18              
19                // Find the rightmost position where the sum of nums[i] and nums[j] is not less than the element at that position
20                // This will ensure that the triangle inequality holds => nums[i] + nums[j] > nums[k]
21                int k = lower_bound(nums.begin() + j + 1, nums.end(), nums[i] + nums[j]) - nums.begin() - 1;
22              
23                // Increase the count by the number of valid triangles found with the base[i,j] pair
24                // k is the rightmost position before which all elements can form a triangle with nums[i] and nums[j], hence k - j
25                count += k - j;
26            }
27        }
28      
29        // Return the count of triangles
30        return count;
31    }
32};
33
1function triangleNumber(nums: number[]): number {
2    // Sort the array in non-decreasing order
3    nums.sort((a, b) => a - b);
4  
5    let count = nums.length;
6    let validTriangles = 0; // Initialize the count of valid triangles
7
8    // Iterate through each number starting from the end
9    for (let i = count - 1; i >= 2; i--) {
10        // Initialize two pointers
11        let left = 0;
12        let right = i - 1;
13      
14        // Use the two pointers to find valid triangles
15        while (left < right) {
16            // Check if the sum of the two sides is greater than the third side
17            if (nums[left] + nums[right] > nums[i]) {
18                // Count the number of triangles with nums[i] as the longest side
19                validTriangles += right - left;
20                // Move the right pointer to check for other possible triangles
21                right--;
22            } else {
23                // Move the left pointer to increase the sum of nums[left] + nums[right]
24                left++;
25            }
26        }
27    }
28
29    // Return the total count of valid triangles
30    return validTriangles;
31}
32
Not Sure What to Study? Take the 2-min Quiz：

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Time and Space Complexity

The given Python code sorts an array and then uses a double loop to find every triplet that can form a valid triangle, using binary search to optimize the finding of the third side.

Time Complexity

The time complexity of the code can be broken down as follows:

  1. nums.sort() has a time complexity of O(n log n) where n is the number of elements in nums.
  2. The outer for-loop runs (n - 2) times.
  3. The inner for-loop runs (n - i - 2) times per iteration of the outer loop, summing up to roughly (1/2) * n^2 in the order of growth.
  4. The bisect_left call within the inner loop does a binary search, which has a time complexity of O(log n).

Thus, the total time complexity of the nested loop (excluding the sort) would be O((n^2/2) * log n), as each iteration of j could potentially result in a binary search. When adding the sort, the overall time complexity is O(n log n + (n^2/2) * log n) which simplifies to O(n^2 log n) when n is large.

Space Complexity

Space complexity is easier to analyze since the only extra space used is for sorting, which in Python is O(n) because Timsort (the algorithm behind Python's sort) can require this much space. No other significant extra space is used, as the variables i, j, k, and ans use constant space. Therefore, the space complexity of the algorithm is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is a good use case for backtracking?

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

Tech Interview Pattern | Two Pointers Introduction

Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers iframe width 560 height 315 src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe Two pointers is a common interview technique

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫