I have no words, how can I thank you. your explanation is great. Being from an Electronics background it is very tough for me to learn code. you made it simple
Very helpful, thank you !! Instead of passing 3 args in max, we can also check if the list has 3 or less elements. Above 86% faster def rob(self, nums: List[int]) -> int: # Check if nums has elements if len(nums)
I would just add by means of explaining why we leave one out - when we remove an element, the "circle" of houses becomes a line of houses, reducing the house robber 2 problem to the house robber 1 problem.
Some optimizations to the original solution: * passing indexes instead of creating new arrays when passing to helper function. * in the first iteration, keeptrack a boolean to determine if we decide to rob the first house or not. Before start the second iteration, check the result if we decide to rob the last house. If the result doesn't need to rob the first house, we can skip the 2nd call to helper function.
Not sure what happens to TH-cam, my replies are always disappear. Try the last time to post the solution with optimization. The tradeoff is that it's a lot more complex than the original solution. fun rob(nums: IntArray): Int { // TO(n) / SO(1)
// return: max, includeFirstHouse, includeLastHouse fun innerRob(from: Int, to: Int): Triple { // Pair var maxA = 0 to false var maxB = 0 to false var includeLastHouse = false
for (i in from .. to) { val num = nums[i]
if (maxA.first + num > maxB.first) { // steal current house maxB = ((maxA.first + num) to (i == 0 || maxA.second)).also { maxA = maxB } includeLastHouse = i == to } else if (maxA.first + num == maxB.first) { maxB = maxB.first to (maxA.second && maxB.second).also { maxA = maxB } includeLastHouse = i == to } else { // don't steal current house maxA = maxB } }
return if (ans1.second || ans1.third) { // if we rob the first or the previous of the last house // we need to check if we should rob the last house val ans2 = innerRob(1, nums.lastIndex) max(ans1.first, ans2.first) } else { // if we didn't rob the first and the previous of the last house // we can definitely rob the last house ans1.first + nums.last() } }
Nice work! Thanks for sharing these solutions. I think you could further improve this solution by setting the first element to '0', then running the helper on the array, add it back, and do the same for the last element. This will save Python having to do two O(n) operations to 'remove' that first element and the last element.
it will probably make it worse because nums[1:] deletes nothing just goes to said indexes, which means it will make n-1 calls to an array, but if you set 1 to zero and go through it it will do 1 changing operation and n calls to array which is not faster
Here is my solution without the helper function, in this way, we don't allocate two new arrays. class Solution: def rob(self, nums: List[int]) -> int: # Check if only one element if len(nums) == 1: return nums[0]
# First iteration rob1, rob2 = 0, 0 for i in nums[:-1]: temp = max(i+rob1, rob2) rob1 = rob2 rob2 = temp res1 = rob2 # Second iteration rob1, rob2 = 0, 0 for i in nums[1:]: temp = max(i+rob1, rob2) rob1 = rob2 rob2 = temp res2 = rob2 return max(res1,res2)
Great solution but the space complexity would be O(n) I expect since you're passing two new arrays to the function. The new arrays will be referencing the original array but they still need space n nonetheless. It would be O(1) if you pass the index instead.
Instead of calling the helper function twice We can call it once passing all the array elements except first and last index Then return Max (arr[0]+helper function output ,arr[last]+helper function output) This allows not to loop over 2 times
![เบิ้ล ปทุมราช - สาวสอง ( มีมี่ของอ้าย ) ft. ตาต้า,ต้องเต [OFFICIAL MV]](http://i.ytimg.com/vi/mqlMjnP08XI/mqdefault.jpg)
Dynamic Programming Playlist: th-cam.com/video/73r3KWiEvyk/w-d-xo.html
I have no words, how can I thank you. your explanation is great.
Being from an Electronics background it is very tough for me to learn code.
you made it simple
Very helpful, thank you !!
Instead of passing 3 args in max, we can also check if the list has 3 or less elements. Above 86% faster
def rob(self, nums: List[int]) -> int:
# Check if nums has elements
if len(nums)
I would just add by means of explaining why we leave one out - when we remove an element, the "circle" of houses becomes a line of houses, reducing the house robber 2 problem to the house robber 1 problem.
This is very helpful wow
Dude, you keep blowing my mind! Everytime I am stucked I will come over to your video to get some EMOTIONAL DAMAGE
Doesn't num[1:] and num[:-1] create 2 new arrays? Isn't this technically O(N) space complexity? Asking coz I am not much hands on with python.
Yes it does. You can modify the original array instead and pass it to helper
I figured out house robber 1 on my own but couldn't figure this one out without looking at the solution. I feel dumb lol
Some optimizations to the original solution:
* passing indexes instead of creating new arrays when passing to helper function.
* in the first iteration, keeptrack a boolean to determine if we decide to rob the first house or not.
Before start the second iteration, check the result if we decide to rob the last house. If the result doesn't need to rob the first house, we can skip the 2nd call to helper function.
Can you explain on the second optimization?
Not sure what happens to TH-cam, my replies are always disappear.
Try the last time to post the solution with optimization. The tradeoff is that it's a lot more complex than the original solution.
fun rob(nums: IntArray): Int {
// TO(n) / SO(1)
// return: max, includeFirstHouse, includeLastHouse
fun innerRob(from: Int, to: Int): Triple {
// Pair
var maxA = 0 to false
var maxB = 0 to false
var includeLastHouse = false
for (i in from .. to) {
val num = nums[i]
if (maxA.first + num > maxB.first) {
// steal current house
maxB = ((maxA.first + num) to (i == 0 || maxA.second)).also { maxA = maxB }
includeLastHouse = i == to
} else if (maxA.first + num == maxB.first) {
maxB = maxB.first to (maxA.second && maxB.second).also { maxA = maxB }
includeLastHouse = i == to
} else {
// don't steal current house
maxA = maxB
}
}
return Triple(maxB.first, maxB.second, includeLastHouse)
}
val ans1 = innerRob(0, nums.lastIndex - 1)
return if (ans1.second || ans1.third) {
// if we rob the first or the previous of the last house
// we need to check if we should rob the last house
val ans2 = innerRob(1, nums.lastIndex)
max(ans1.first, ans2.first)
} else {
// if we didn't rob the first and the previous of the last house
// we can definitely rob the last house
ans1.first + nums.last()
}
}
Python list slicing does not create new arrays so it's the same as passing indexes.
@@nguyenquoctran8423it creates a shallow copy, which is O(N)
I laughed so hard after breaking my head for 30 min even after solving houserob1 lol
Thanks for making out these vidoes .They are crisp and explanative at the same time !! They are of great help. You definitely deserve more subscribers
Nice work! Thanks for sharing these solutions. I think you could further improve this solution by setting the first element to '0', then running the helper on the array, add it back, and do the same for the last element. This will save Python having to do two O(n) operations to 'remove' that first element and the last element.
read my thoughts, i wonder how much it actually impacts the solution...
@@director8656 not much, because its already O(n) which is almost equal to O(k*n)
@@nemesis_rc Yeah, I thought so don't think it could make or break a solution..
Or just store the original array in an instance variable and then work with indexes instead of copying over the entire array for each method call
it will probably make it worse because nums[1:] deletes nothing just goes to said indexes, which means it will make n-1 calls to an array, but if you set 1 to zero and go through it it will do 1 changing operation and n calls to array which is not faster
Thanks for the explanation
Don't know why I'm do dumb
skill fucking issue
very clear!! I used Java Deque to store recent values
subscribed by watching half of the video
Thanks for your awesome explanation for both house rob 1 and 2
After understanding the solution I am feeling dizzy, don't know why am I soooo dumb!!!!!
I also felt the same way!!!! I banged my head for two hours LOL🤣
@@slnop9724 😂😂
Here is my solution without the helper function, in this way, we don't allocate two new arrays.
class Solution:
def rob(self, nums: List[int]) -> int:
# Check if only one element
if len(nums) == 1:
return nums[0]
# First iteration
rob1, rob2 = 0, 0
for i in nums[:-1]:
temp = max(i+rob1, rob2)
rob1 = rob2
rob2 = temp
res1 = rob2
# Second iteration
rob1, rob2 = 0, 0
for i in nums[1:]:
temp = max(i+rob1, rob2)
rob1 = rob2
rob2 = temp
res2 = rob2
return max(res1,res2)
you are the best teacher for data structure and algorithms , all over the youtube
i was able to do house robber 1 by myself, had trouble with house robber 2 now i just feel dumb after watching this explanation
U just nailed it man🔥
Can you also prove max(nums) = max(dp(nums[1:]), dp[nums[:-1]]), leaving out the edge case?
Thanks
Great solution but the space complexity would be O(n) I expect since you're passing two new arrays to the function. The new arrays will be referencing the original array but they still need space n nonetheless. It would be O(1) if you pass the index instead.
slicing doesn't create new lists
i could solve the house robber one but I was not able to see this small observations to solve the second one. (EMOTIONAL DAMAGE !!!!)
This is just amazing!!!
Thank you for the explaination.
Awesome, great as always!
Thanks :)
Gosh it is so easy to go from HR1 to HR2
public static int f(int n, int[] nums){
if(n==0){
return 0;
}
if(n
Yes you can.
class Solution:
def rob(self, nums: List[int]) -> int:
return max(nums[0], self.rob1(nums[:-1]), self.rob1(nums[1:]))
def rob1(self, nums):
if len(nums) == 0:
return 0
if len(nums) == 1:
return nums[0]
if len(nums) == 2:
return max(nums[0], nums[1])
dp = nums[:]
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i-1], dp[i-2]+ dp[i])
return dp[len(nums)-1]
Good one
Great explanation
very clear!!
Bro pls upload longest common subsequence (LCS) WITH ONE DIMENSIONAL DP SOLUTION
eagerly waiting
U r the best
Instead of calling the helper function twice
We can call it once passing all the array elements except first and last index
Then return Max (arr[0]+helper function output ,arr[last]+helper function output)
This allows not to loop over 2 times
I guess that wont wokr beacause we may take adjacent houses without knowing in this way
yea it won't work in that way
house rubber.
Really great explanation! Thank you 🙌🏻
Python solution using DP:
class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]
def rob1(nums):
dp = [0]*(len(nums)+1)
dp[0] = 0
dp[1] = nums[0]
for i in range(1,len(nums)):
dp[i+1] = max(dp[i],dp[i-1]+nums[i])
return dp[len(nums)]
a = rob1(nums[1:])
b = rob1(nums[:-1])
return max(a,b)
Goddam Genius
I'm so stupid!.such a simple idea,wasted 30min on trying and got nowhere.😭😭
D9ne and dusted
yesssssssssssssssssssssssssssssssssssss
dont waste so much time on explaining previous problem
Keep calm keyboard warrior
how do i connect with you on linkedin