SyntaxPilot
Courses/DSA and Coding Problems/Lesson 63
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 63 of 90

House robber

queued

These are the notes for DSA episode 63. Last episode's DP had no choice to make; today every item has one: take it or skip it. A volunteer collects festival donations on one street but can never visit two next-door houses on the same evening. The take-or-skip recursion is correct but Time Limit Exceeded on 100 houses; two greedy rules (every other house, biggest first) give 3 instead of 4 and 4 instead of 6. The DP recipe gives dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]), which shrinks to two variables, and House Robber II (houses in a circle) becomes two straight-line problems. Every program below was run with javac 21 (25-second limit, like the SyntaxPilot compiler), g++ 13 and Python 3, and every output shown is real.

The problem, in real life

A volunteer collects pledged donations for a festival on one street, in one evening. If she visits two houses next door to each other, the neighbours compare notes and both back out. Which houses should she visit to collect the most? LeetCode tells the same story with a robber, so the problem is called House Robber.

On the street In code
House i's pledge nums[i]
Next-door houses indexes i and i + 1
Visit / don't visit take / skip
Best total from the first i houses dp[i]
Houses around a square House Robber II (a circle)

Every word, from zero

  • Adjacent: next to each other (indexes differ by 1).
  • Take or skip: the two choices at every item; the core of many DP problems (knapsack next).
  • State: dp[i] = the most we can collect from the first i houses (nums[0..i-1]).
  • Recurrence: from the last house: skip it (dp[i - 1]) or take it (nums[i - 1] + dp[i - 2]).
  • Greedy: a rule that commits now; here every greedy rule fails.
  • Suffix: the houses from some index to the end; the brute force re-solves the same suffixes.
  • Circular array: the last element is next to the first.
  • O(1) space: a fixed number of variables, whatever n is.

Problem statement

LeetCode 198, House Robber. nums[i] is the money at house i. You can't take two adjacent houses. Return the maximum total.

nums Answer Houses taken
[1, 2, 3, 1] 4 1 + 3
[2, 7, 9, 3, 1] 12 2 + 9 + 1

Constraints: 1 ≤ nums.length ≤ 100, 0 ≤ nums[i] ≤ 400.

Obvious idea: take or skip, recursively

import java.util.*;

public class Main {
    static int rob(int[] nums) {
        return best(nums, 0);
    }
    static int best(int[] nums, int i) {
        if (i >= nums.length) return 0;
        int take = nums[i] + best(nums, i + 2);
        int skip = best(nums, i + 1);
        return Math.max(take, skip);
    }
    public static void main(String[] args) {
        System.out.println(rob(new int[]{1, 2, 3, 1}));
        System.out.println(rob(new int[]{2, 7, 9, 3, 1}));
    }
}
4
12

On 100 random houses: Time Limit Exceeded. The call count grows like Fibonacci numbers: best(i) calls best(i + 1) and best(i + 2), and the same suffixes are solved again and again.

Two greedy traps

import java.util.*;

public class Main {
    static int everyOther(int[] nums) {
        int even = 0, odd = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i % 2 == 0) even += nums[i];
            else odd += nums[i];
        }
        return Math.max(even, odd);
    }
    static int biggestFirst(int[] nums) {
        int n = nums.length, total = 0;
        boolean[] blocked = new boolean[n];
        Integer[] order = new Integer[n];
        for (int i = 0; i < n; i++) order[i] = i;
        Arrays.sort(order, (a, b) -> nums[b] - nums[a]);
        for (int i : order)
            if (!blocked[i]) {
                total += nums[i];
                if (i > 0) blocked[i - 1] = true;
                if (i + 1 < n) blocked[i + 1] = true;
            }
        return total;
    }
    public static void main(String[] args) {
        System.out.println("every other: " + everyOther(new int[]{2, 1, 1, 2}));
        System.out.println("biggest first: " + biggestFirst(new int[]{3, 4, 3}));
    }
}
every other: 3
biggest first: 4

[2, 1, 1, 2]: take the first and last houses for 4 (one even index, one odd). [3, 4, 3]: skip the 4 and take both 3s for 6.

The key insight: the DP recipe

  1. State: dp[i] = most from the first i houses.
  2. Recurrence: house i (that's nums[i - 1]) is skipped → dp[i - 1]; or taken → nums[i - 1] + dp[i - 2]. dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1])
  3. Base cases: dp[0] = 0, dp[1] = nums[0].
  4. Order: i = 2 … n; answer dp[n].

By hand on [2, 7, 9, 3, 1]:

i house value skip dp[i-1] take nums[i-1] + dp[i-2] dp[i]
0 0
1 2 2
2 7 2 7 + 0 = 7 7
3 9 7 9 + 2 = 11 11
4 3 11 3 + 7 = 10 11
5 1 11 1 + 11 = 12 12

Solution in Java: the table

import java.util.*;

public class Main {
    static int rob(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n + 1];
        dp[1] = nums[0];
        for (int i = 2; i <= n; i++)
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        return dp[n];
    }
    public static void main(String[] args) {
        System.out.println(rob(new int[]{1, 2, 3, 1}));
        System.out.println(rob(new int[]{2, 7, 9, 3, 1}));
        System.out.println(rob(new int[]{2, 1, 1, 2}));
        System.out.println(rob(new int[]{3, 4, 3}));
        System.out.println(rob(new int[]{5}));
    }
}
4
12
4
6
5

The 100 houses that timed out: 11847 rupees, 0 ms.

Top-down: the recursion plus a notebook

The slow recursion was only forgetful. memo[i] = best from house i to the end; -1 means unknown (0 can be a real answer).

import java.util.*;

public class Main {
    static int[] memo;
    static int rob(int[] nums) {
        memo = new int[nums.length];
        Arrays.fill(memo, -1);
        return best(nums, 0);
    }
    static int best(int[] nums, int i) {
        if (i >= nums.length) return 0;
        if (memo[i] != -1) return memo[i];
        int take = nums[i] + best(nums, i + 2);
        int skip = best(nums, i + 1);
        memo[i] = Math.max(take, skip);
        return memo[i];
    }
    public static void main(String[] args) {
        System.out.println(rob(new int[]{1, 2, 3, 1}));
        System.out.println(rob(new int[]{2, 7, 9, 3, 1}));
        int[] nums = new int[100];
        Random rnd = new Random(7);
        for (int i = 0; i < 100; i++) nums[i] = rnd.nextInt(401);
        long t0 = System.nanoTime();
        int total = rob(nums);
        System.out.println(total + " rupees, " + (System.nanoTime() - t0) / 1000000 + " ms");
    }
}
4
12
11847 rupees, 0 ms

Which houses? Walk the table backwards

import java.util.*;

public class Main {
    static void plan(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n + 1];
        dp[1] = nums[0];
        for (int i = 2; i <= n; i++)
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        System.out.println("dp = " + Arrays.toString(dp));
        List<Integer> houses = new ArrayList<>();
        for (int i = n; i >= 1; ) {
            if (i >= 2 && dp[i] == dp[i - 1]) i--;
            else { houses.add(0, i); i -= 2; }
        }
        System.out.println("visit houses " + houses + ", total " + dp[n]);
    }
    public static void main(String[] args) {
        plan(new int[]{2, 7, 9, 3, 1});
        plan(new int[]{2, 1, 1, 2});
    }
}
dp = [0, 2, 7, 11, 11, 12]
visit houses [1, 3, 5], total 12
dp = [0, 2, 2, 3, 4]
visit houses [1, 4], total 4

Two variables: O(1) space

import java.util.*;

public class Main {
    static int rob(int[] nums) {
        int prev2 = 0, prev1 = 0;
        for (int x : nums) {
            int cur = Math.max(prev1, prev2 + x);
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
    public static void main(String[] args) {
        System.out.println(rob(new int[]{1, 2, 3, 1}));
        System.out.println(rob(new int[]{2, 7, 9, 3, 1}));
    }
}
4
12

On ten lakh houses: 1000000 houses: 117346025 rupees, 16 ms (times vary). (With values ≤ 400 and n ≤ 100, int is plenty for LeetCode; ten lakh houses still fit under 2³¹ here, but use long for bigger totals.)

House Robber II (LeetCode 213): houses in a circle

The first and last houses are neighbours. Never both, so solve two ordinary streets, without the last and without the first, and take the better. One house is a special case (both streets would be empty).

nums Answer
[2, 3, 2] 3
[1, 2, 3, 1] 4
[1, 2, 3] 3
import java.util.*;

public class Main {
    static int robLine(int[] nums, int from, int to) {
        int prev2 = 0, prev1 = 0;
        for (int i = from; i <= to; i++) {
            int cur = Math.max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
    static int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) return nums[0];
        return Math.max(robLine(nums, 0, n - 2), robLine(nums, 1, n - 1));
    }
    public static void main(String[] args) {
        System.out.println(rob(new int[]{2, 3, 2}));
        System.out.println(rob(new int[]{1, 2, 3, 1}));
        System.out.println(rob(new int[]{1, 2, 3}));
        System.out.println(rob(new int[]{5}));
    }
}
3
4
3
5

The same solutions in C++

#include <bits/stdc++.h>
using namespace std;

// House Robber (LeetCode 198) and House Robber II (LeetCode 213): take or skip, two variables.
int robLine(const vector<int>& nums, int from, int to) {
    int prev2 = 0, prev1 = 0;
    for (int i = from; i <= to; i++) {
        int cur = max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}
int rob(const vector<int>& nums) { return robLine(nums, 0, (int)nums.size() - 1); }
int robCircle(const vector<int>& nums) {
    int n = nums.size();
    if (n == 1) return nums[0];
    return max(robLine(nums, 0, n - 2), robLine(nums, 1, n - 1));
}

int main() {
    cout << rob({1, 2, 3, 1}) << " " << rob({2, 7, 9, 3, 1}) << " " << rob({2, 1, 1, 2}) << " " << rob({3, 4, 3}) << "\n";
    cout << robCircle({2, 3, 2}) << " " << robCircle({1, 2, 3, 1}) << " " << robCircle({1, 2, 3}) << " " << robCircle({5}) << "\n";
}
4 12 4 6
3 4 3 5

The same solutions in Python

# House Robber (LeetCode 198) and House Robber II (LeetCode 213).
def rob_line(nums):
    prev2 = prev1 = 0
    for x in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + x)
    return prev1

def rob_circle(nums):
    if len(nums) == 1:
        return nums[0]
    return max(rob_line(nums[:-1]), rob_line(nums[1:]))

print(rob_line([1, 2, 3, 1]), rob_line([2, 7, 9, 3, 1]), rob_line([2, 1, 1, 2]), rob_line([3, 4, 3]))
print(rob_circle([2, 3, 2]), rob_circle([1, 2, 3, 1]), rob_circle([1, 2, 3]), rob_circle([5]))
4 12 4 6
3 4 3 5

Three real bugs

Bug 1: always taking the current house

dp[i] = dp[i - 2] + nums[i - 1]; on [2, 1, 1, 2]:

3

Should be 4. The best from the first i houses doesn't have to include house i: the skip choice is missing.

Bug 2: the circle solved as a line

The two-variable line solution on [2, 3, 2]:

4

It took the first and last houses (2 + 2), which are neighbours on a circle. The answer is 3.

Bug 3: no one-house check on the circle

Without if (n == 1) return nums[0];, on [5]:

0

Both ranges (0..-1 and 1..0) are empty. A single house has no neighbour to clash with: the answer is 5.

Complexity

Approach Time Space Big input
Take or skip, recursively O(1.618ⁿ) O(n) stack 100 houses: Time Limit Exceeded
Every other / biggest first O(n) / O(n log n) O(n) wrong
DP table O(n) O(n) instant
Two variables O(n) O(1) 10 lakh houses: 16 ms
Circle: two passes O(n) O(1)

Common mistakes

Mistake What you see (real) Why Fix
Every other house 3 instead of 4 greedy with no proof DP: take or skip
Biggest first 4 instead of 6 greedy with no proof DP
Always take house i 3 instead of 4 the skip choice is missing max(dp[i - 1], …)
Circle as a line 4 instead of 3 first and last touch two lines, take the max
Circle, one house 0 instead of 5 both lines empty if (n == 1) return nums[0]
dp[1] = nums[1] wrong or crash off-by-one: dp[i] uses nums[i - 1] write the state in words first

Mini project: which houses?

Walk the table backwards to print the houses chosen: if dp[i] == dp[i - 1], house i was skipped; otherwise it was taken and we jump to i - 2.

import java.util.*;

public class Main {
    // Mini project: House Robber that also prints which houses were visited.
    public static void main(String[] args) {
        int[] nums = {2, 7, 9, 3, 1, 8, 4};
        int n = nums.length;
        int[] dp = new int[n + 1];
        dp[1] = nums[0];
        for (int i = 2; i <= n; i++) dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        List<Integer> houses = new ArrayList<>();
        for (int i = n; i >= 1; ) {
            if (i >= 2 && dp[i] == dp[i - 1]) i--;
            else { houses.add(0, i); i -= 2; }
        }
        System.out.println("total " + dp[n] + " from houses " + houses);
    }
}
total 19 from houses [1, 3, 6]

Houses 1, 3 and 6 (numbered from 1) hold 2 + 9 + 8 = 19.

Practice

1. Delete and Earn (LeetCode 740). Taking a value x earns x and deletes every x - 1 and x + 1. Maximise the points.

Solution

Add up the points per value: points[x] = x × count(x). Then values x and x + 1 are "adjacent houses": House Robber on points.

import java.util.*;

public class Main {
    // Delete and Earn (LeetCode 740): House Robber over the values 0..max.
    static int deleteAndEarn(int[] nums) {
        int max = Arrays.stream(nums).max().getAsInt();
        int[] points = new int[max + 1];
        for (int x : nums) points[x] += x;
        int prev2 = 0, prev1 = 0;
        for (int p : points) {
            int cur = Math.max(prev1, prev2 + p);
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
    public static void main(String[] args) {
        System.out.println(deleteAndEarn(new int[]{3, 4, 2}));
        System.out.println(deleteAndEarn(new int[]{2, 2, 3, 3, 3, 4}));
    }
}
6
9

2. Maximum sum of non-adjacent elements with negatives. Values may be negative and you may take nothing. Hint: the same recurrence works, because skipping is always allowed (dp never goes below 0).

Solution
# Max sum of non-adjacent elements; negatives allowed, empty choice = 0.
def best(nums):
    prev2 = prev1 = 0
    for x in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + x)
    return prev1

print(best([-1, -2, -3]), best([3, -1, 4, -5, 9]), best([-5, 10, -5, 10]))
0 16 20

3. House Robber III (LeetCode 337). Houses form a binary tree; parent and child are adjacent. Hint: for each node return two numbers, (best if taken, best if skipped). Coming in episode 76.

Quick quiz

Houses [5, 1, 1, 5] in a line. Largest total? A) 10 B) 6 C) 11 D) 7

Answer

A) 10. Take the first and last house. dp: 0, 5, 5, 6, 10.

Interview questions

  1. State and recurrence? dp[i] = best from the first i houses; dp[i] = max(dp[i-1], dp[i-2] + nums[i-1]).
  2. Why does greedy fail? A big house can block two medium neighbours worth more together; parity can split the best pair.
  3. Space? O(1) with two variables, since dp[i] reads only dp[i-1] and dp[i-2].
  4. Circular version? Answer = max(line without the last, line without the first); one house is special.
  5. How do you recover the chosen houses? Keep the table and walk back: equal to dp[i-1] means skipped.
  6. Relation to Fibonacci? Same shape of recurrence (two previous states), but with max and a value added.

Glossary

Term Meaning
Adjacent Next to each other (indexes differ by 1)
Take or skip The two choices at each item
State dp[i] = best from the first i houses
Recurrence dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])
Suffix The items from some index to the end
Circular array The last element touches the first
O(1) space A fixed number of variables

Summary

  • At each house: take it (nums[i-1] + dp[i-2]) or skip it (dp[i-1]); keep the max.
  • Take-or-skip recursion is exponential (Time Limit Exceeded at 100 houses); greedy rules give wrong answers.
  • Two variables give O(n) time and O(1) space; a circle is two lines, with one house as a special case.
  • Next episode: coin change: the fewest coins and the number of ways.