🗓️ Day 20: House Robber II (Circular Houses)

📘 What You’ll Learn

• How House Robber II differs from the original
• Why circular houses complicate things
• How to split the problem into two subproblems
• Implementing two DP runs to solve the problem
• Optimizing in TypeScript
• Real LeetCode example

🧠 Concept

Welcome to the circular version of the house robbing problem! 🏠🌀

You’re still a professional robber, but now the houses are arranged in a circle — meaning the first and last houses are neighbors! 😱

You can’t rob both the first and the last house. So, you split the problem into two linear DP runs:

• Rob from house 0 to n-2
• Rob from house 1 to n-1

Then, return the max of those two results.

📊 Visualization

Given:

Index:   0   1   2   3   4
Money:  2   3   2   5   1

Because it's circular, you have to:

• Either rob houses 0 to 3
• Or rob houses 1 to 4

Run the standard House Robber DP on both ranges and take the best.

💻 TypeScript Example

function rob(nums: number[]): number {
  if (nums.length === 0) return 0;
  if (nums.length === 1) return nums[0];

  function robLinear(arr: number[]): number {
    let prev1 = 0, prev2 = 0;
    for (let num of arr) {
      const temp = Math.max(prev1, prev2 + num);
      prev2 = prev1;
      prev1 = temp;
    }
    return prev1;
  }

  const excludeLast = robLinear(nums.slice(0, nums.length - 1));
  const excludeFirst = robLinear(nums.slice(1));

  return Math.max(excludeLast, excludeFirst);
}

• ⏱️ Time: O(n)
• 💾 Space: O(1)

🧪 LeetCode Homework

📘 213. House Robber II

You’re a pro robber with circular house targets. Return the max amount of money you can rob without hitting two adjacent houses in a circle.

const houses = [2,3,2];
console.log(rob(houses)); // 3

const houses2 = [1,2,3,1];
console.log(rob(houses2)); // 4

📌 Key Takeaways

• Circular houses = you can’t rob first and last
• Solve two linear rob problems and take the best result
• Reuse your linear House Robber DP helper
• This technique is useful for other "circular" array problems!

🔮 Up Next

▶️ Day 21: Climbing Stairs Variants