Widest Triangle Fence
Problem
A farmer has fence poles of lengths poles and wants to enclose a triangular pen using exactly three poles as the sides. The triangle must have positive area: each side must be strictly shorter than the sum of the other two.
Return the largest possible perimeter, or 0 if no three poles form such a triangle.
Example 1
- Input:
- poles = [3, 6, 2, 3]
- Output:
- 8
6, 3, 3 is flat (6 = 3 + 3). The next candidate 3, 3, 2 works: perimeter 8.
Example 2
- Input:
- poles = [1, 2, 3]
- Output:
- 0
Constraints
- 3 ≤ poles.length ≤ 10^5
- 1 ≤ poles[i] ≤ 10^6
Hint
Show the first hint
If you fix the longest side, which two other poles give it the best chance?
Walkthrough
How to approach it
01Clarify before coding
- Is a flat triangle allowed? No: the area must be positive, so the inequality is strict.
- Must the poles be distinct lengths? No, equal lengths are fine.
- What if nothing works? Return 0.
02Brute force
Try every triple of poles and keep the best valid perimeter.
Cost: O(n³): 10^15 triples for n = 10^5.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.