Maximize Score after N Operations - Leetcode 1799 - Python
Vložit
- čas přidán 23. 07. 2024
- Solving leetcode 1799, maximize score after N operations. Today's daily leetcode problem on May 13th.
🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 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/maximiz...
0:00 - Understand problem
3:55 - Brute force explanation
5:25 - Memoization explanation
10:35 - Time Complexity
11:35 - Coding solution
leetcode 1799
#neetcode #leetcode #python
Sorry for the wait... this one took a 'bit' longer than I expected 😆
Nice pun 🤣
Never have I ever thought a DP problem with bitmasking would make sense in just one time explanation. Your channel is superb! Thank you for this!
Thank you for the update! I've been waiting for your new video all day cuz I found other videos about the same problem are always not satisfying compared to yours.
Hey NeetCode! Thank you for the great explanation and for introducing a new concept to me. I really learn a lot from you.
Keep up the good work by educating us.
Awesome explanation on the Bitmask part...Helped me visualize it.
Thanks! Couldn't have solved the problem without this video.
Just like to share a little trick I saw in others' solutions
for i in range(len(nums)):
if mask & (1
The best coding channel on youtube
I was going to skip today's challenge because the solution on leetcode looked so difficult. Thanks for what you do, you make learning so simple.☺
9:33 Precious Information✨✨
I made the mistake where, I used the operation number as the key because I thought that
It is the only changing number, this should be the key.
Thanks for telling why not to use that
Thank you for everything you do!
wow u are life savior NEET!
Wooh that was some problem. Not easy to figure out Bit masking. thanks!
Shouldn't the inner loop j be in range from 1st to last element as well and not from i+1 as the even though the pair may get computed again but its order is important as well to maximise as op is considered.?
Clean as usual hats off
Please do a separate video for explaining bit mask.
If anyone's confused why we have n squared choices for each operation
[1, 2, 3, 4, 5, 6]
In the explanation, Neet kinda missed to explain this part
He was saying we have n squared choice but the way he proceed to explain looks like n choice as (1,2) or (1,3) or(1,4) and so on
But in reality, we need to choose the max for each operation count, so we can choose (1,2) or (2,4), or (5,6) or anything which gives us a max gcd
Thus for each operation we make n squared comparisons :)
Great explanation
Thanks for the daily
The best solution!
great explanation
some people get to be this awesome!
How do you do these drawings?
Was waiting for this.
Edit:
Easy GCD function: gcd(a,b) { while( b!=0 ) { r=a%b; a=b; b=r; } return a; }
Euclid's algorithm.
Why code it when in just about all the major languages you have built-in functions that do it for you?
@@psibarpsi it is not that big of code and I think it would make a good impression in interview
@@psibarpsi Because I remember learning it recently😅 Also like Aryan above said, good impression👍🏻
I have this error I don't know why? Please help
AttributeError: 'module' object has no attribute 'gcd'
score = op * math.gcd(nums[i], nums[j])
You are a 'bit' of a genius!😂
we can cache also the gcd result if we use (1
can you add this google question to your playlist
2184 Number of Ways to Build Sturdy Brick Wall
thought you said op was redundant information?
can someone help me know what the problem with my solution is ?
1 -> sort the array nums then take the last element(the biggest) and look for the second biggest such that their remainder == 0 and take their gcd and store this gcd in an array
2 -> for the remaining pairs take their GCD as 1
3 -> now sort the GCD array, multiply the largest with n then the second largest with n-1 and so on and as for those remaining pairs we had earlier, add one for each pair
this gives me 80% correct answer and fails for some big test cases
daily savior
class Solution:
def maxScore(self, nums: List[int]) -> int:
n = len(nums)
@lru_cache(None)
def dfs(k,avail):
if k == half_n + 1:
return 0
maxi = 0
for i in range(n):
if avail & (1
I think we should not have cached the score with operation multiplied. Because as an example I can pick 5,6 in operation 2 as well
At 10:15
Why this method doesnt work ?
class Solution:
def maxScore(self, nums: List[int]) -> int:
heap=[]
numDict=Counter(nums)
n2=len(nums)
n=n2//2
for i in range(n2):
for j in range(i+1,n2):
heapq.heappush(heap,(-math.gcd(nums[i],nums[j]),nums[i],nums[j]))
res=0
while(heap and n):
gcd,num1,num2=heapq.heappop(heap)
if not numDict[num1] or not numDict[num2]:
continue
numDict[num1]-=1
numDict[num2]-=1
res+=-gcd*n
n-=1
return res
this video has many conceptual gaps...Explanation is not crystal clear
Is there any portion that is lacking?
had no idea you had this second channel. I thought you stopped leetcode because you started working
tried a greedy approach. Idea being we have to use the largest gcd for the nth operation.
Step 1: compute GCD for all combination of 2n nums. Push into a heap along with the index of nums for which the GCD was calculated.
Step 2: Pop from the heap and keep track of the indices which were already used in the result calculation.
Repeat step 2 until all the indices have been used.
finally return the result.
It failed for this test case: [109497,983516,698308,409009,310455,528595,524079,18036,341150,641864,913962,421869,943382,295019]
expected: 527
actual output: 525
Not sure where the bug is in my code.
from typing import List
import heapq
class Solution:
def maxScore(self, nums: List[int]) -> int:
def gcd(a, b):
while b:
a, b = b, a % b
return a
max_heap = []
len_nums = len(nums)
for i in range(len_nums):
for j in range(i+1,len_nums):
val = gcd(nums[i],nums[j])
heapq.heappush(max_heap, (-val,(i,j)))
ans = 0
seen_nums = set()
for i in range((len_nums//2),0,-1):
while True:
val = heapq.heappop(max_heap)
gcd_val = -val[0]
n1,n2 = val[1][0],val[1][1]
if n1 in seen_nums or n2 in seen_nums:
continue
else:
seen_nums.add(n1)
seen_nums.add(n2)
break
ans = ans + (i*gcd_val)
return ans
i too used somewhat same approach and it works for like 80% of the test cases, i wonder what the problem is with this approach. if you find out please let me know !
@@kartikeyrana3736
When there are multiple pairs that gives the same GCD, we cannot blindly pick any pair.
We need to pick a pair such that we maximize the GCD for the nums there were not picked.
@@AR_7333 ohh i see, thanks