Find Polygon with the Largest Perimeter - Leetcode 2971

Find Polygon with the Largest Perimeter - Leetcode 2971 - Python

Рет қаралды 12,783

Күн бұрын

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🧑‍💼 LinkedIn: / navdeep-singh-3aaa14161
🐦 Twitter: / neetcode1
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
Problem Link: leetcode.com/p...
leetcode 2971
#neetcode #leetcode #python

Пікірлер: 21

@unknown-ut5qn 7 ай бұрын

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

@joelbolkert4273 7 ай бұрын

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.

@satyamjha68 7 ай бұрын

I did the same thing

@sanis85 7 ай бұрын

total = 0 heap = [] for num in nums: total += num heapq.heappush(heap, -num) this approach gave me best time running it in leetcode

@siddhantvishnu4309 7 ай бұрын

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

@thiagot7706 7 ай бұрын

It is today daily challenge

@eshabaweja 7 ай бұрын

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

@shaco6630 7 ай бұрын

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 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 2 else -1

@alxolr 7 ай бұрын

Max Heap is still O(nlogn) for inserts.

@shaco6630 7 ай бұрын

@@alxolr Yes, you are correct. But that statement is not relevant here. You did not understand the solution correctly. Inserting n elements in a heap is O(nlogn), but we are not Inserting n elements. As I explained we build a heap from an array. Heapify (build a heap) of an array in Python is a O(n) operation. And we will pop at most 30 times (since max element is 10^9 according to problem constraints) in our algorithm which boils down to O(30logn) and we have final O(n) time complexity for this solution. I would recommend you familiarize yourself with the inner workings of heapq and C++ priority_queue to understand why this is true. Also, as I mentioned above the same can be achieved in C++.

@leeroymlg4692 7 ай бұрын

@@shaco6630 even with the constraint in mind, it's still nlogn because the input size influences the amount of iterations.

@ИгорьКабаков-з4м 7 ай бұрын

Thank you!

@banchanbet4524 7 ай бұрын

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

@Baseballchampion 7 ай бұрын

I believe this is similar to the prefix sum solution he describes before his optimal solution.

@yg1095 7 ай бұрын

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

@vietnguyenquoc4948 7 ай бұрын

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