☕ DSA Java Articles

Topics › Dynamic Programming › 1D DP

House robber

Medium TUF ID 290 A2ZBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

A thief plans to rob houses arranged in a circle. House i holds nums[i] money (non-negative). Robbing two adjacent houses sets off an alarm, and because the street is circular, the first house and the last house are adjacent too. Return the most money the thief can take without robbing two neighbours.

In Striver’s sheet this entry is the circular version (LeetCode 213, “House Robber II”). The straight-line version, where the first and last houses are not neighbours, is the previous problem, Maximum sum of non adjacent elements.

Constraints on LeetCode: 1 ≤ n ≤ 100, 0 ≤ nums[i] ≤ 1000. The Java methods return long and also accept an empty array (answer 0).

Example 1

nums = [2, 3, 2]
answer = 3          // houses 0 and 2 are neighbours on the circle, so the two 2s cannot both be taken

Example 2

nums = [1, 2, 3, 1]
answer = 4          // houses 0 and 2: 1 + 3

Approach 1: Brute force over all subsets

Intuition. With n houses there are 2^n possible sets of houses to rob. Represent each set as a bit mask, reject any set containing two neighbours on the circle (house i and house (i + 1) % n), and keep the best sum. This is slow, but it follows the problem statement literally, so it is a trustworthy reference for testing the faster methods.

Algorithm.

  1. For every mask from 0 to 2^n - 1:
  2. For each house i in the mask, check that its circular neighbour (i + 1) % n is not in the mask, and add nums[i] to the sum.
  3. If no neighbour pair was found, update the best sum.

With one house, (0 + 1) % 1 = 0 points back to the house itself, so the code skips that comparison (next != i).

static long bruteForce(int[] nums) {
    int n = nums.length;
    long best = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        boolean ok = true;
        long sum = 0;
        for (int i = 0; i < n && ok; i++) {
            if ((mask >> i & 1) == 0) continue;
            int next = (i + 1) % n;                         // the neighbour on the circle (house 0 after house n-1)
            if (next != i && (mask >> next & 1) == 1) ok = false;
            sum += nums[i];
        }
        if (ok) best = Math.max(best, sum);
    }
    return best;
}

Complexity. Time O(2^n · n), space O(1). Only usable for about 20 houses.

The key observation: break the circle

The linear problem is solved by the pick / not-pick DP. The circle adds exactly one extra constraint: houses 0 and n - 1 cannot both be robbed. So in any valid plan, at least one of them is left alone:

The converse also holds. A valid plan for the line 0 .. n - 2 never touches house n - 1, so the wrap-around pair (n - 1, 0) cannot be violated, and the plan is valid on the circle. The same goes for the other line. So the circular answer is exactly

max( linear(0 .. n - 2), linear(1 .. n - 1) )

Plans that skip both end houses are counted in both lines; that is harmless when taking a maximum.

One special case: with a single house the two lines are empty and would give 0, but a lone house has no neighbour, so the answer is nums[0].

Approach 2: Memoization on both lines

Intuition. Solve each line with the memoized pick / not-pick recursion. For a line lo .. hi, let f(i) be the best sum using houses lo .. i. Either rob house i and continue from i - 2, or skip it and continue from i - 1; below lo there is nothing left.

Algorithm.

  1. Handle n == 0 and n == 1 directly.
  2. Run the memoized recursion on 0 .. n - 2 and on 1 .. n - 1, each with its own table.
  3. Return the larger result.

Each line needs a fresh table: dp[i] means “best sum from lo to i”, and that depends on lo.

static long memoization(int[] nums) {
    int n = nums.length;
    if (n == 0) return 0;
    if (n == 1) return nums[0];                             // a single house has no neighbour
    long[] dpA = new long[n], dpB = new long[n];
    Arrays.fill(dpA, -1);
    Arrays.fill(dpB, -1);
    long skipLast = robRange(nums, 0, n - 2, dpA);          // houses 0 .. n-2
    long skipFirst = robRange(nums, 1, n - 1, dpB);         // houses 1 .. n-1
    return Math.max(skipLast, skipFirst);
}

static long robRange(int[] nums, int lo, int i, long[] dp) {
    if (i < lo) return 0;
    if (dp[i] != -1) return dp[i];
    long pick = nums[i] + robRange(nums, lo, i - 2, dp);
    long skip = robRange(nums, lo, i - 1, dp);
    return dp[i] = Math.max(pick, skip);
}

Complexity. Time O(n): two lines, each with n - 1 states computed once. Space O(n) for the tables and the recursion stack.

Approach 3: Optimal, two linear passes in O(1) space

Intuition. Each line only needs the classic two-variable House Robber loop. prev is the best sum up to the previous house, prev2 the best sum up to the one before it. For each house, either skip it (prev) or rob it on top of prev2.

Instead of copying the array twice, as some solutions do, the helper takes the index range lo .. hi. The work is the same; it just avoids two O(n) copies.

Algorithm.

  1. If n == 0 return 0; if n == 1 return nums[0].
  2. Return max(robLine(0, n - 2), robLine(1, n - 1)).
static long optimal(int[] nums) {
    int n = nums.length;
    if (n == 0) return 0;
    if (n == 1) return nums[0];
    return Math.max(robLine(nums, 0, n - 2), robLine(nums, 1, n - 1));
}

static long robLine(int[] nums, int lo, int hi) {
    long prev2 = 0, prev = 0;                               // best up to i - 2 and up to i - 1
    for (int i = lo; i <= hi; i++) {
        long cur = Math.max(prev, prev2 + nums[i]);
        prev2 = prev;
        prev = cur;
    }
    return prev;
}

Dry run on nums = [1, 3, 1, 3, 100]. The line without the last house, [1, 3, 1, 3], gives 6. The line without the first house, [3, 1, 3, 100]:

house value skip (prev) rob (prev2 + value) new prev
1 3 0 0 + 3 = 3 3
2 1 3 0 + 1 = 1 3
3 3 3 3 + 3 = 6 6
4 100 6 3 + 100 = 103 103

The answer is max(6, 103) = 103: houses 1 and 4, which are not neighbours on the circle.

Complexity. Time O(n), space O(1).

Edge cases and pitfalls