Find Polygon with the Largest Perimeter - Leetcode 2971 - Python

leetcode 2971

#neetcode #leetcode #python

[unknown-utqn]

Man is always on top of leetcode, it's almost like they give him insights of a new daily problem

[joelbolkert]

You can also sum all the elements then go from right to left subtracting the current element and checking if it's larger than the remainder, in which case you can return the first valid perimeter you find (or -1 if you find none). Obviously you have to sum the array first and the time complexity comes from sorting either way so not a better or worse solution.

[siddhantvishnu]

Yooo I literally solved this one 10 mins ago and now seeing neetcode upload the same problem!! 🤯🤯

[shaco]

Hey Neet!

Great video as usual! We can also achieve O(n) time complexity in both Python & C++ by using a max heap instead of sorting.

By using heapq._heapify_max(nums) + heapq._heappop_max(nums) in Python or
priority_queue<int> and pop().

Time complexity of these two implementations are O(n + 30logn) ~ O(n). Here is an example in python:

def largestPerimeter(self, nums: List[int]) -> int:
curSum = sum(nums)
heapq._heapify_max(nums)
while nums and curSum <= nums[0] * 2:
curSum -= heapq._heappop_max(nums)
return curSum if len(nums) > 2 else -1

[eshabaweja]

I like how none of the drawings on the thumbnail are polygons. they're 3D. great explanation though!

[banchanbet]

what i did was assuming that the largest perimeter is the sum of the whole array, then i kept removing the maximum element that doesnt satisfy the condition and subtract that element from the total sum, then return -1 if the array has its length < 3, otherwise return the result

[yg]

Can you add this and all the new problems over the past few months to the Neetcode All section?

[vietnguyenquoc]

I tried to solve this using top down DP because I thought it is another variant of house robber to no avail then tried greedy.
I really still wonder if this can be solve using top down DP with memoize or not, if anyway did please do enlighten me

[xingyuxiang]

Though the input is 10^5, and the solution only looks at its closest neighbor in one direction, it is not a greedy problem.

[bollywoodboxoffice]

please add all your new problem to neetcode all sheet

[rajsuriyang]

Though it was greedy changed my mind to dynamic programming and found out it is greedy😢.