Coding Interview Questions | House Robber

January 26th, 2024

House Robber Problem Introduction:

This summary will talk about my solution to the house robber problem as seen on leetcode here. A synopsis of the problem summary will be shown below:

You are a professional robber planning to rob houses along a street.
Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them
is that adjacent houses have security systems connected and it will automatically contact the police if two
adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money
you can rob tonight without alerting the police.

How do you solve the House Robber Problem using Dynamic Programming?

Solution:

function rob(nums: number[]): number {
  const maxLoot = Array.from({ length: nums.length }, () => 0);

  for (let numIdx = 0; numIdx < nums.length; numIdx++) {
    const num = nums[numIdx];
    if (numIdx === 0) {
      maxLoot[numIdx] = num;
      continue;
    }

    if (numIdx === 1) {
      maxLoot[numIdx] = Math.max(num, nums[0]);
      continue;
    }

    maxLoot[numIdx] = Math.max(num + maxLoot[numIdx - 2], maxLoot[numIdx - 1]);
  }

  return Math.max(...maxLoot);
}

House Robber Solution Summary:

Below is a breakdown of the key aspects of the provided solution for the house robber problem seen above:

  1. Dynamic Programming Array Initialization: The algorithm initializes an array maxLoot of length equal to the number of houses. This array represents the maximum loot that can be obtained up to the current house and is set to 0 initially.

  2. Iterative House Robbery Calculation: The algorithm iterates through each house, calculating the maximum loot that can be obtained up to that house. It considers the scenario of robbing the current house versus skipping it.

  3. Base Cases Handling: Special handling is provided for the first and second houses to establish initial conditions for the dynamic programming approach.

  4. Maximum Loot Update: For each house, the algorithm calculates the maximum loot by considering the loot from the current house plus the loot from two houses back (to avoid alerting the police) or the loot from the previous house, whichever is greater.

  5. Final Result: The final result is the maximum value stored in the maxLoot array, representing the maximum amount of money that can be robbed without alerting the police.

Complexities

  1. Time Complexity: The time complexity of the solution is determined by the single iteration through the array of houses, denoted as O(n), where n is the number of houses.

  2. Space Complexity: The space complexity is O(n) as the algorithm uses an array of size n to store the maximum loot for each house.