Maximum Product Difference Between Two - Leetcode 1913 - Python
VloĆŸit
- Äas pĆidĂĄn 24. 07. 2024
- đ neetcode.io/ - A better way to prepare for Coding Interviews
đ§âđŒ LinkedIn: / navdeep-singh-3aaa14161
đ„· Discord: / discord
đŠ Twitter: / neetcode1
đź Support the channel: / neetcode
â BLIND-75 PLAYLIST: âą Two Sum - Leetcode 1 -...
đĄ DYNAMIC PROGRAMMING PLAYLIST: âą House Robber - Leetco...
Problem Link: leetcode.com/problems/maximum...
0:00 - Read the problem
0:17 - Drawing Explanation
7:51 - Coding Explanation
leetcode 1913
#neetcode #leetcode #python
Figured this one out on my own but came to see your solution. Nearly identical solution. Either I have watched so much neetcode that i am getting neetcode brain, or I am finally actually getting the hang of this. Either one works with me
Neetcode brain is hilarious lol - I hope to be there soon.
Hey Neetcode, would you be able to do a video on Meeting Rooms III? It's the most frequent question on the Google Leetcode tag and I've actually gotten this question in a Google interview 2 years ago.
heyy @dorio5535, thanks for letting us know you encountered this problem in your Google interview
I am no @Neetcode but there is my solution. Just solved after seeing your comment
class Solution:
def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
# NOTE: use 2 min-heaps: one for currently running meetings and
# one for rooms (we need to use the available room with least room number)
# min-heap used for running meetings as it allows us to get the meeting
# that ends next.
# NOTE: in the running_meetings heap, we push (end_time, assigned_room)
# assigned_room is used to free the room
# in some test cases, the meetings are NOT in ascending order by start time
meetings.sort()
running_meetings = []
rooms = [i for i in range(n)]
heapq.heapify(rooms)
counter = {i:0 for i in range(n)} # counts the number of meetings held at each room
for start, end in meetings:
# pop the meetings that end before this meeting starts
# this is needed to handle the cases where a meeting starts waaay later than other meetings
while running_meetings and running_meetings[0][0] most_meetings:
most_meetings = meeting_count
result_room = room_num
return result_room
The BF that I came up with:
class Solution:
def maxProductDifference(self, nums: List[int]) -> int:
nums.sort()
result = (nums[-1]*nums[-2])-(nums[0]*nums[1])
return result
Sort is O(n * log n) which is slower than O(n) solution just finding two largest and two smallest elements.
Also why do you call it BF?
@@KeyAndLock77what else do I call it if I come up with the quickest possible solution?
@@foodoodle4415 They just explained that your solution is not the quickest.
this is what I did and it runs about as fast as Neetcode's solution
@@phatboislym pretty big difference between nlogn and n.
why is heap o(n)? i thought putting each element in a heap is o(log(n)) and there are n elements?
That's true when the heap has already n elements, but if you are adding one element to an empty heap it will only take log(0), the second element log(1)... you will need at most (I think) 2n operations to build a heap of size n
Twist in problem:
What if the array contains mix of positive and negative? You probably want to choose one largest negatvie and another largest positive so the subtration is added unto instead subtracted?
Similarly for two largest numbers, we can also choose two smallest -ve numbers
No bro you can also tackle that type of problem also
Initialize min variables to -inf
why you only make videos on easy daily challenge and skips most of the time hard daily challenge
I don't skip problems based on difficulty, have done plenty of Hards this year
I think he is skipping easies ,if any. Check your facts
Nibba you donât owe him anything, you are acting like you paid him, he can make whatever videos he wants to
@@shreehari2589 I know he can make whatever he wants and Im not ordering him I just noticed it that's why I am asking because many times I don't see any videos on medium-hard and hard problems and that's what most people wants.