House Robber Ii - 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';
const EXCLUDED_HOUSE = 'excluded_house', EXCLUDED_HOUSE_COLOR = 'lightgray';

function visMainFunction(inputNums) {
  initClassProperties();

  // Edge case: single house
  if (inputNums.length === 1) {
    notification(`🏠 <b>Edge Case:</b> Only one house available. Returning <b>${inputNums[0]}</b>.`);
    return inputNums[0];
  }

  const nums = VisArray.from(inputNums).options({ label: 'Houses' });

  explanationAndcolorSchemaNotifications();

  // Case 1: Exclude first house (mark index 0 as excluded)
  nums.makeVisManagerForIndex(0).addClass(EXCLUDED_HOUSE);
  notification(`▶️ Running linear robber on <b>case 1</b> — ${makeColoredSpan('Exclude first house', EXCLUDED_HOUSE_COLOR)}: <code>[1 .. ${nums.length - 1}]</code>`);
  const excludeFirstResult = linearHouseRobber(nums, 1, nums.length - 1, makeColoredSpan('Exclude First House', EXCLUDED_HOUSE_COLOR));
  nums.makeVisManagerForIndex(0).removeClass(EXCLUDED_HOUSE);

  // Case 2: Exclude last house (mark last index as excluded)
  nums.makeVisManagerForIndex(nums.length - 1).addClass(EXCLUDED_HOUSE);
  notification(`▶️ Running linear robber on <b>case 2</b> — ${makeColoredSpan('Exclude last house', EXCLUDED_HOUSE_COLOR)}: <code>[0 .. ${nums.length - 2}]</code>`);
  const excludeLastResult = linearHouseRobber(nums, 0, nums.length - 2,  makeColoredSpan('Exclude Last House', EXCLUDED_HOUSE_COLOR));
  nums.makeVisManagerForIndex(nums.length - 1).removeClass(EXCLUDED_HOUSE);

  const result = Math.max(excludeFirstResult, excludeLastResult);
  notification(`🏆 <b>Final Answer:</b> max(<b>excludeLastResult(${excludeFirstResult})</b>, <b>excludeLastResult(${excludeLastResult})</b>) = <b>${result}</b>.`);
  return result;
}

/**
 * Runs linear House Robber over inclusive range [start .. end].
 */
function linearHouseRobber(nums, start, end, label) {
  startBatch();
  let prevMax = 0, currMax = 0;

  const prevMaxVis = makeVisVariable(prevMax).options({ label: `prevMax (${label})` }).createVis();
  const currMaxVis = makeVisVariable(currMax).options({ label: `currMax (${label})` }).createVis();

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

  notification(`
    <b>${label}</b> — considering range <code>[${start} .. ${end}]</code> (inclusive).<br/>
    • <code>prevMax</code>: best total <b>excluding</b> the last evaluated house.<br/>
    • <code>currMax</code>: best total <b>so far</b>.<br/><br/>
    ▶️ We’ll iterate through that range and update <code>prevMax</code> / <code>currMax</code>.
  `);

  while (currentHouseIndex <= end) {
    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 robbed so far <b>excluding</b> the last evaluated house.</li>
        <li><b>currMax (${currMax})</b>: maximum robbed so far.</li>
        <li>If we <b>rob</b> this house (must skip the last evaluated one) → total =
          <b>prevMax(${prevMax}) + currentHouseValue(${currentHouseValue}) = ${prevMax + currentHouseValue}</b>.
        </li>
        <li>If we <b>skip</b> this house → total = <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>Update 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();
  }

  startPartialBatch();
  notification(`🏁 <b>Finished case "${label}":</b> maximum robbed = <b>${currMax}</b>.`);
  [currMaxVis, prevMaxVis].forEach(el => el.destroyVis());
  endBatch();

  return currMax;
}

function explanationAndcolorSchemaNotifications() {
  explanationNotification();
  notification(`
    🎨 <b>Visualization Color Legend</b><br/><br/>
    <ul>
      <li>
        <span style="display:inline-block; border:2px solid ${CURRENT_HOUSE_COLOR}; padding:0 8px; border-radius:6px;">&nbsp;</span>
        <b>Current house</b> (<code>currentHouseIndex</code>): the index currently being evaluated in the active linear range
        <code>[start .. end]</code>. Highlighted with a ${makeColoredSpan('border', CURRENT_HOUSE_COLOR)}.
      </li>
      <li>
        <span style="display:inline-block; background-color:${EXCLUDED_HOUSE_COLOR}; padding:0 8px; border-radius:6px;">&nbsp;</span>
        <b>Excluded house</b>: the first or last house that is disallowed in the current case
        (cannot be robbed due to the circular constraint). Shown with a ${makeColoredSpan('dim '+EXCLUDED_HOUSE_COLOR+' background', EXCLUDED_HOUSE_COLOR)} and a <code>-</code> label.
      </li>
    </ul>
  `);
}

function initClassProperties() {
  setClassProperties(CURRENT_HOUSE, { borderColor: CURRENT_HOUSE_COLOR });
  setClassProperties(EXCLUDED_HOUSE, {
    backgroundColor: EXCLUDED_HOUSE_COLOR,
    label: '-'
  });
}

Approach

Approach (Reduce Circle to Two Linear Passes + O(1) DP State)

In House Robber II, houses form a circle, so the first and last houses are adjacent and cannot both be robbed. We convert this circular constraint into two linear subproblems and take the maximum result. Let n denote the number of houses.

Exclude first house → evaluate the inclusive range [1 .. n-1].
Exclude last house → evaluate the inclusive range [0 .. n-2].

Let linearHouseRobber(start, end) denote the standard linear House Robber executed directly over the indices without slicing. The final answer is max(linearHouseRobber(1, n-1), linearHouseRobber(0, n-2)).

Why the n = 1 Edge Case Needs Special Handling

When there is only one house (n = 1), that single house will not be part of either of the two linear ranges — [1 .. n-1] or [0 .. n-2] — because both become empty. As a result, the main algorithm would incorrectly skip it and return 0. Therefore, we handle this case separately by directly returning nums[0].

Linear Subproblem (State & Transition)

State variables:
prevMax — best total robbed so far excluding the last evaluated house.
currMax — best total robbed so far.
Initialization: prevMax = 0, currMax = 0.
Transition (for each house i in [start .. end]):
- If we rob it (must skip the last evaluated one) → total = prevMax + nums[i].
- If we skip it → total = currMax.
- Then newMax = max(currMax, prevMax + nums[i]) and roll forward: prevMax = currMax, currMax = newMax.
Result: currMax after the loop gives the optimal value for that range.

Why Two Cases Solve the Circle

Because the first and last houses are adjacent, robbing one forbids the other. By separately computing the optimal totals for ranges [1 .. n-1] and [0 .. n-2], we ensure that both endpoints are never chosen together. The overall maximum of the two linear results gives the optimal circular solution.

Time Complexity

O(n) Each of the two linear runs ([1 .. n-1] and [0 .. n-2]) processes every house once. Both runs together still form a linear pass through the input, so the overall time remains O(n).

Space Complexity

O(1) The algorithm maintains only a constant number of running variables regardless of input size.

Input-1

House Robber Ii - JS Solution

Solution code

Solution explanation

Solution explanation

Approach

Approach (Reduce Circle to Two Linear Passes + O(1) DP State)

Why the n = 1 Edge Case Needs Special Handling

Linear Subproblem (State & Transition)

Why Two Cases Solve the Circle

Time Complexity

Space Complexity