Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
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
step 1 / 33
2
3
4
4
5
[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
  • n5

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