How do you solve Valid Triangles Count?

Sort the array. Iterate from the end to fix the largest side. Use two pointers (left at start, right just before largest) to find pairs where the sum is greater than the largest side. When the sum condition is met, add all pairs between left and right to the count and move right pointer leftward; otherwise, move left pointer rightward. This approach counts all valid triangles in O(n^2) time.

Valid Triangles Count

Q: What is the time complexity of Valid Triangles Count?

O(n^2). Sorting takes O(n log n). The main loop iterates over n elements, and the two-pointer inner loop moves pointers across the array at most n times per iteration, resulting in O(n^2) total time.

Q: What pattern does Valid Triangles Count use?

The Pattern: Two Pointers (Sorted Array Pair Search) The Heuristic: When searching for pairs that satisfy a sum condition relative to a fixed element in a sorted array, use two pointers from opposite ends to efficiently count or find all valid pairs by moving pointers based on the sum comparison.

Medium Two Pointers

Problem

Given an integer array nums, return the number of triplets chosen from the array that can form valid triangles where the sum of any two sides is greater than the third side.

1 ≤ nums.length ≤ 1000
0 ≤ nums[i] ≤ 1000

Example

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

Output: 3

After sorting, nums = [2,2,3,4]. The valid triangles are (2,3,4), (2,3,4), and (2,2,3). The algorithm sorts the array to leverage the property that if nums[left] + nums[right] > nums[largest_index], then all elements between left and right can form valid triangles with nums[largest_index]. The two-pointer approach efficiently counts these without checking every triplet explicitly.

Approach

Straightforward Solution

A brute-force approach checks all triplets (O(n^3)) by verifying the triangle inequality for each. This is too slow for large inputs.

Core Observation

A triangle is valid if the sum of the lengths of any two sides is greater than the third side. Sorting the array allows us to fix the largest side and use two pointers to find pairs that satisfy this condition efficiently.

Path to Optimal

Preview

Sorting the array enables a key insight: for a fixed largest side, if nums[left] + nums[right] > nums[largest_index], then all elements between left and right can form valid triangles with nums[largest_index]…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Sort the array. Iterate from the end to fix the largest side…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n^2)

Sorting takes O(n log n). The main loop iterates over n elements, and the two-pointer inner loop moves pointers across the array at most n times per iteration, resulting in O(n^2) total time.

Space

O(1)

The algorithm sorts the input in place and uses only a few variables for pointers and counters, requiring constant auxiliary space.

Pattern Spotlight

Two Pointers (Sorted Array Pair Search)

When searching for pairs that satisfy a sum condition relative to a fixed element in a sorted array, use two pointers from opposite ends to efficiently count or find all valid pairs by moving pointers based on the sum comparison.

Solution

Python

1class Solution:
  def triangleNumber(self, nums: list[int]) -> int:
      nums.sort()
      triangle_count = 0
5
      for largest_index in range(len(nums) - 1, 1, -1):
          left = 0
          right = largest_index - 1
9
          while left < right:
              if nums[left] + nums[right] > nums[largest_index]:
                  triangle_count += right - left
                  right -= 1
              else:
                  left += 1
16
      return triangle_count

Step-by-Step Solution

Sort the Input Array to Enable Two-Pointer Strategy

3nums.sort()
4triangle_count = 0

Objective

To arrange the array in ascending order so that the triangle inequality can be efficiently checked using two pointers.

Key Insight

Sorting the array is crucial because it allows the algorithm to fix the largest side and then use two pointers to find all pairs that satisfy the triangle condition without redundant checks. The sorted order guarantees that if a pair sum exceeds the largest side, all pairs between the pointers also satisfy the condition.

Interview Quick-Check

Core Logic

Sorting transforms the problem into a structured search where the triangle inequality can be checked efficiently using two pointers.

Common Pitfalls & Bugs

Forgetting to sort leads to incorrect assumptions about pair sums and invalid counting.

Iterate Backwards Fixing the Largest Side and Use Two Pointers to Count Valid Pairs

To fix the largest side of the triangle and use two pointers to find all pairs that satisfy the triangle inequality with it.

Return the Total Count of Valid Triangles

To output the total number of valid triangles found after processing all possible largest sides.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 11 Critical

if nums[left] + nums[right] > nums[largest_index]:

Check if the sum of nums[left] and nums[right] is greater than nums[largest_index].

This comparison is the core algorithmic check that determines whether the current pair with the fixed largest side forms a valid triangle, enabling bulk counting of all pairs between left and right.

Line 12 Critical

triangle_count += right - left

Add the number of valid pairs between left and right to the triangle count.

This line exploits the sorted order to count all valid pairs between left and right in constant time, dramatically reducing the complexity from checking each pair individually.

Full line-by-line criticality + rationale for all 12 lines available on Pro.

Test Your Understanding

Why does moving the right pointer leftward after finding a valid pair count all intermediate pairs between left and right?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Valid Triangles Count from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Valid Triangles Count drill

or drill a free problem

1	`class Solution:`
2	`def triangleNumber(self, nums: list[int]) -> int:`
3	`nums.sort()`
4	`triangle_count = 0`
5
6	`for largest_index in range(len(nums) - 1, 1, -1):`
7	`left = 0`
8	`right = largest_index - 1`
9
10	`while left < right:`
11	`if nums[left] + nums[right] > nums[largest_index]:`
12	`triangle_count += right - left`
13	`right -= 1`
14	`else:`
15	`left += 1`
16
17	`return triangle_count`