Skip to main content

27. House Robber

mediumAsked at Workday

Maximize the sum of values you can take from a row of houses without taking two adjacent. Workday uses this as a DP warmup — same shape as scheduling non-overlapping shift-bonuses across consecutive pay periods.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2025-Q4)— Workday SDE2 phone screen — DP intro.
  • LeetCode Discuss (2026)— Workday compensation team variant: 'select non-adjacent bonuses'.

Problem

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint 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.

Constraints

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 400

Examples

Example 1

Input
nums = [1,2,3,1]
Output
4

Explanation: Rob house 1 (1) and house 3 (3) = 4.

Example 2

Input
nums = [2,7,9,3,1]
Output
12

Explanation: Rob 2 + 9 + 1 = 12.

Approaches

1. Recursive without memo

rob(i) = max(nums[i] + rob(i+2), rob(i+1)).

Time
O(2^n)
Space
O(n)
function rob(i){ if (i >= nums.length) return 0; return Math.max(nums[i] + rob(i+2), rob(i+1)); }

Tradeoff: Exponential. Don't ship.

2. DP with two-variable rolling

Track prev (rob i-2) and curr (rob i-1). New curr = max(prev + nums[i], curr).

Time
O(n)
Space
O(1)
function rob(nums) {
  let prev = 0, curr = 0;
  for (const x of nums) {
    const next = Math.max(prev + x, curr);
    prev = curr;
    curr = next;
  }
  return curr;
}

Tradeoff: Two rolling variables. The recurrence is: at each house, either take it (+ prev) or skip (+ curr).

Workday-specific tips

Workday wants the rolling-variables version, not a full DP array. State 'rob(i) = max(skip i, take i + best of i-2)' clearly before coding. The 'why prev = curr; curr = next' update order is what they grade.

Common mistakes

  • Updating prev = curr AFTER curr = next — prev becomes the new curr, off by one.
  • Using nums[i] + curr — that's adjacent.
  • Returning prev instead of curr at the end.

Follow-up questions

An interviewer at Workday may pivot to one of these next:

  • House Robber II (LC 213) — houses in a circle.
  • House Robber III (LC 337) — houses in a tree.
  • Delete and Earn (LC 740) — same shape, different framing.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why is this DP?

At each house we have two choices that depend only on previous decisions: take (commit to skipping prev) or skip (carry over). The recurrence has overlapping subproblems.

Can I solve with a greedy?

No — taking every other house fails on [2, 1, 1, 2]. You'd take 2+1 = 3 instead of 2+2 = 4. Greedy doesn't see ahead.

Practice these live with InterviewChamp.AI

Drill House Robber and other Workday interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →