LeetCode 213 House Robber II: Final 2D DP Solution Handling Both Intervals

2025-06-206 minutes read
A clear and clean JavaScript solution for LeetCode 213 using a 2D dynamic programming array to handle two intervals (rob first house or not) simultaneously.

Problem Overview

LeetCode 213 "House Robber II" is about robbing houses arranged in a circle, where you cannot rob both the first and last house.

The classic approach is to split the problem into two subproblems:

  • Rob houses from index 0 to n-2
  • Rob houses from index 1 to n-1

Then return the maximum of the two results.

Code Implementation

Below is the 2D DP array approach that simultaneously handles these two cases:

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    const n = nums.length
    if (n === 0) return 0
    if (n === 1) return nums[0]
    if (n === 2) return Math.max(nums[0], nums[1])
    
    // dp[0]: rob first house, interval [0..n-2]
    // dp[1]: skip first house, interval [1..n-1]
    const dp = Array.from({ length: 2 }, () => new Array(n).fill(0))
    
    // Initialize dp[0]
    dp[0][0] = nums[0]
    dp[0][1] = Math.max(nums[0], nums[1])
    
    // Initialize dp[1]
    dp[1][0] = 0  // skip the first house
    dp[1][1] = nums[1]
    
    for (let i = 2; i < n; i++) {
        if (i < n - 1) {
            dp[0][i] = Math.max(dp[0][i - 2] + nums[i], dp[0][i - 1])
        }
        dp[1][i] = Math.max(dp[1][i - 2] + nums[i], dp[1][i - 1])
    }
    
    return Math.max(dp[0][n - 2], dp[1][n - 1])
}

Explanation

  • We use a 2D dp array, where each row represents whether to rob the first house or not.
  • Each row follows the classic House Robber state transitions independently.
  • Finally, return the maximum result between the two intervals.

Summary

This approach uses more space than the conventional solution but has a clear and intuitive state partitioning, making it good for demonstrating DP thinking in interviews. You may optimize space later using rolling variables.

Keep practicing and accumulate more solid problem-solving techniques! πŸš€