House Robber II - Dynamic Programming - Leetcode 213

0:00 - Read the problem
1:27 - Drawing Explanation
6:00 - Coding Solution

leetcode 213

#sorted #array #python
Disclaimer: Some of the above links may be affiliate links.

[applesmith]

This explanation cleared up both house robber I and house robber II. This is a much better video than the House Robber I explanation. Thank you.

[vinoddiwan]

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

[appcolab]

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) <= 3:
return max(nums)

return max(self.helper(nums[1:]), self.helper(nums[:-1]))

def helper(self, nums):
rob1, rob2 = 0, 0
for n in nums:
new_rob = max(rob1 + n, rob2)
rob1 = rob2
rob2 = new_rob
return rob2

[joshr]

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.

[jcn]

Dude, you keep blowing my mind! Everytime I am stucked I will come over to your video to get some EMOTIONAL DAMAGE

[nguyen-dev]

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.

[balajinagappan]

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

[Zac-Willmington]

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.

[adipratapsinghaps]

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.

[_control_]

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)

[leoncai]

very clear!! I used Java Deque to store recent values

[champagnemmmyyyyy]

My code, pretty similar to yours i guess:
def rob(self, nums: List[int]) -> int:
if len(nums)==1:
return nums[0]
r1=0; r2=0
for i in range(len(nums)-1):
temp1=max(nums[i]+r1, r2)
r1=r2
r2=temp1

r3=0; r4=0
for i in range(1, len(nums)):
temp2=max(nums[i]+r3, r4)
r3=r4
r4=temp2
return max(r2, r4)

[alirezafereydoni]

Thanks for your awesome explanation for both house rob 1 and 2

[sahilchoudhary]

you are the best teacher for data structure and algorithms, all over the youtube

[sivaganesh]

subscribed by watching half of the video

[avanishgvyas]

A small feedback: Please explain the algorithm with a longer array instead of just 3 elements. Same feedback applied to other videos as well.

[ehabteima]

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.

[vyshakhbabji]

I laughed so hard after breaking my head for 30 min even after solving houserob1 lol

[ChiCity]

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

[anjanobalesh]

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