House Robber - JS Solution

Editorial

Editorial solutions and visualizations are prepared with care, but we do not guarantee 100% accuracy or completeness. Please use your own judgment to verify results. Visucodize is not responsible for decisions made based on this content.

const CURRENT_HOUSE = 'current_house', CURRENT_HOUSE_COLOR = 'blue';

function visMainFunction(inputNums) {
    initClassProperties();

    startBatch();
    const nums = VisArray.from(inputNums);

    let prevMax = 0;
    let currMax = 0;

    makeVisVariable(prevMax).options({ label: 'prevMax (Exclude Last Evaluated House)' }).createVis();
    makeVisVariable(currMax).options({ label: 'currMax (Include Last Evaluated House)' }).createVis();

    let currentHouseIndex = 0;
    makeVisVariable(currentHouseIndex).registerAsIndexPointer(nums, CURRENT_HOUSE);
    endBatch();

    notification(`
      • <b>prevMax</b>: maximum money robbed so far <b>excluding</b> the last evaluated house (initially <b>0</b>).<br/>
      • <b>currMax</b>: maximum money robbed so far (initially <b>0</b>).<br/><br/>
      ▶️ We’ll now iterate through each house and update <b>prevMax</b> and <b>currMax</b> accordingly.
    `);

    while (currentHouseIndex < nums.length) {
        startPartialBatch();
        const currentHouseValue = nums[currentHouseIndex];

        notification(`
          📌 <b>Evaluating house ${makeColoredSpan(currentHouseIndex, CURRENT_HOUSE_COLOR)}</b> 
          (Value: <b>${currentHouseValue}</b>):
          <ul>
            <li><b>prevMax (${prevMax})</b>: maximum money robbed so far <b>excluding</b> the last evaluated house.</li>
            <li><b>currMax (${currMax})</b>: maximum money robbed so far.</li>
            <li>If we <b>rob</b> this house (so we must skip the last evaluated one) → total money = 
              <b>prevMax(${prevMax}) + currentHouseValue(${currentHouseValue}) = ${prevMax + currentHouseValue}</b>.
            </li>
            <li>If we <b>skip</b> this house → total money = <b>currMax = ${currMax}</b>.</li>
          </ul>
        `);

        const newMax = Math.max(currMax, prevMax + currentHouseValue);

        notification(`
          ✅ <b>Best choice</b> for house ${makeColoredSpan(currentHouseIndex, CURRENT_HOUSE_COLOR)}:
          <ul>
            <li>Maximum possible = <b>${newMax}</b>.</li>
            <li>We now update the states:</li>
            <ul>
              <li><code>prevMax = currMax</code> → <b>${currMax}</b></li>
              <li><code>currMax = newMax</code> → <b>${newMax}</b></li>
            </ul>
          </ul>
        `);

        prevMax = currMax;
        currMax = newMax;

        currentHouseIndex += 1;
        endBatch();
    }

    notification(`🏁 <b>Finished!</b> Maximum amount of money robbed is <b>${currMax}</b>.`);
    return currMax;
}

function initClassProperties() {
    setClassProperties(CURRENT_HOUSE, {
        backgroundColor: CURRENT_HOUSE_COLOR
    });
}

Approach

Intuition:
We cannot rob two adjacent houses, so for each house we decide whether to rob it or skip it based on which choice yields a higher total. This leads to a simple recurrence: at every step, our best total depends only on the results of the last two evaluated houses.
State Representation:
Instead of keeping a full DP array, we only need two running values:
- prevMax — maximum money robbed so far excluding the last evaluated house.
- currMax — maximum money robbed so far (including all evaluated houses up to this point).
Transition:
For each house with value currentHouseValue:
- If we rob this house, we must skip the last evaluated one to avoid triggering the alarm. Therefore, the best total in this case is the money robbed up to the house before the last one (prevMax) plus the value of the current house: prevMax + currentHouseValue.
- If we skip this house, we simply carry forward the best total so far, which is currMax.
- The optimal total for the current house is the maximum of these two choices: newMax = max(currMax, prevMax + currentHouseValue).
State Update:
After each house:
- prevMax = currMax
- currMax = newMax
This effectively moves the window forward by one house while keeping only the last two states in memory.
Termination:
After processing all houses, currMax holds the maximum amount of money that can be robbed without alerting the police.

Time Complexity

We iterate through each house exactly once, performing a constant amount of work per iteration (a few arithmetic operations and comparisons). Therefore, the overall time complexity is O(n), where n is the number of houses.

Space Complexity

We only keep track of two variables — prevMax and currMax — regardless of how many houses there are. Since no additional data structures grow with input size, the space complexity is O(1).

Input-1

House Robber - JS Solution

Solution code

Solution explanation

Solution explanation

Approach

Time Complexity

Space Complexity