Saturday, June 20, 2020

Leetcode solution 198. House Robber

Problem Statement 




Example 1:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
             Total amount you can rob = 1 + 3 = 4.

Example 2:

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
             Total amount you can rob = 2 + 9 + 1 = 12.



  • 0 <= nums.length <= 100
  • 0 <= nums[i] <= 400
 Problem link

Video Tutorial

You can find the detailed video tutorial here

Thought Process

Easy problem and Dynamic Programming(DP) should jump into mind given it's only asking for max values (Just think about different combo we have to do without using DP, a little less than 2^N)

The mathematical induction formula is below, for any current max money at index i, you either choose to use the i-1 or i-2 + current house's money to not trigger police.
max[i] = max(max[i - 2] + a[i], max[i-1])



Time Complexity: O(N) N is the array size
Space Complexity: O(N) since we used an extra array


No comments:

Post a Comment
