Okay, so today I tried to tackle this coding problem, “Largest Perimeter Triangle”. The number is 976. I found it on this coding practice site.
First, I read the problem carefully. It seemed pretty straightforward. Given an array of numbers, find the largest perimeter of a triangle that can be formed using three of those numbers, provided it’s a valid triangle.
I remembered the triangle inequality theorem – the sum of any two sides of a triangle must be greater than the third side. That was the key!
My initial thought was, “Okay, I’ll just brute-force this thing.” I started writing nested loops, like three levels deep, to check every possible combination of three numbers.
- First loop picks number ‘a’.
- Second loop picks number ‘b’.
- Third loop picks number ‘c’.
Inside the loops, I had a bunch of ‘if’ statements to check if a + b > c, a + c > b, and b + c > a. If all those were true, I’d calculate the perimeter (a + b + c) and keep track of the largest one I found.
I ran it on small sample first. It is working!
Then I submitted my first try with that brute-force approach. I got a “Time Limit Exceeded” error. Ugh, I should be thinking better ways!
I realized I didn’t need all those nested loops. I can just use a trick. It’s simple! Sort that number first!
So,I sorted the array in descending order. My thinking was, if I start with the largest numbers, I’m more likely to find a valid triangle and a large perimeter quickly.
I sorted the array, and I only needed one loop.
Here’s what I use inside of the loop.
- I take the first three numbers (let’s call them a, b, and c, after sorting).
- Check if a < b + c, because after sorting, we already made a >=b >=c. if it is, that’s the largest possible perimeter, I can return right here.
- If not, move on to the next set of three numbers.
I ran it, and bang! It passed all the test cases, really fast! It’s really satisfying and exciting!
