Problem

Valid Triangle Number

LeetCode #611Medium

Count triples that form a triangle

Given an array of non-negative integers representing side lengths, count how many triplets can form a valid triangle.

Asked atAmazonGoogle

Brute force

time O(n³)space O(1)

step 1 / 33

Brute force

Optimized · fix k + two pointers

[0][1][2][3][4]

Brute force


▸
1sort arr
2count ← 0
3for i ← 0 to n − 3:
4    for j ← i + 1 to n − 2:
5        for k ← j + 1 to n − 1:
6            if arr[i] + arr[j] > arr[k]:
7                count++
8return count

state

Count triples (i, j, k) with i < j < k that form a valid triangle.

Memoizing...

warming up the animation