#52 · 1D DP

House Robber II

The houses are arranged in a circle, so the first and last houses are neighbours. Return the maximum you can rob without robbing two adjacent houses.

MediumLeetCode

Computing
Depends on
Answer

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Reduction to two linear problems

On a circle, house 0 and house n − 1 cannot both be robbed. So the optimum either skips the last house or skips the first one. Each case is an ordinary House Robber on a straight line, and the answer is the larger of the two.

Memory layout

No new structure: the same dp as House Robber, run on the subarrays [0, n − 2] and [1, n − 1].

Operation	Cost
time	O(n) (two passes)
space	O(1) with two variables

Rolling pair of values

For each straight range keep next1 (best from i + 1) and next2 (best from i + 2) and update them house by house.

Memory layout

Two integers.

Operation	Cost
per house	O(1)

Why it fits

The circle adds one constraint (the two ends are adjacent). Fixing "which end is excluded" removes that constraint and leaves a problem we already know how to solve.
The two cases cover every valid robbery: any valid set excludes at least one of the two end houses.
Doing both cases costs only twice the linear time, so there is no need for a more complicated circular DP.

Why alternatives degrade

Run plain House Robber on the whole array:: It may take both ends (here 2 + 9 + 1 = 12), which is illegal on a circle.
Track "first house robbed" in the DP state:: It works (a second dimension of size 2) but is more complicated than running the simple DP twice.
Greedy:: Greedy choices fail on a street already; the circle adds nothing that makes greedy work.

Four approaches, from naive to production

1 · beginner

Recursion on the two ranges

time O(2ⁿ)space O(n) recursion

Handle the circle by taking the better of two straight streets: houses 0…n−2 and houses 1…n−1. Each street is solved with the exponential rob-or-skip recursion.

int rob(vector<int>& nums) {
    int n = nums.size();
    if (n == 1) return nums[0];
    function<int(int, int)> best = [&](int i, int last) -> int {
        if (i > last) return 0;
        return max(nums[i] + best(i + 2, last), best(i + 1, last));
    };
    return max(best(0, n - 2), best(1, n - 1));
}

public int rob(int[] nums) {
    int n = nums.length;
    if (n == 1) return nums[0];
    return Math.max(best(nums, 0, n - 2), best(nums, 1, n - 1));
}
private int best(int[] nums, int i, int last) {
    if (i > last) return 0;
    return Math.max(nums[i] + best(nums, i + 2, last), best(nums, i + 1, last));
}

def rob(nums):
    n = len(nums)
    if n == 1: return nums[0]
    def best(i, last):
        if i > last: return 0
        return max(nums[i] + best(i + 2, last), best(i + 1, last))
    return max(best(0, n - 2), best(1, n - 1))

function rob(nums: number[]): number {
  const n = nums.length;
  if (n === 1) return nums[0];
  const best = (i: number, last: number): number => {
    if (i > last) return 0;
    return Math.max(nums[i] + best(i + 2, last), best(i + 1, last));
  };
  return Math.max(best(0, n - 2), best(1, n - 1));
}

Flaws & bottlenecks

Each range repeats the exponential recursion of the plain problem.
The single-house case must be handled separately: both ranges would be empty or invalid.
The same suffix is recomputed by different callers.

Interviewer cross-questions

Why do two ranges cover everything?

Say: In any valid robbery, at most one of the two end houses is robbed. If the first is not robbed, the answer lies in range B; if the last is not robbed, it lies in range A.

Why handle n = 1 separately?

Say: With one house both ranges would be empty (0…−1 and 1…0), returning 0, but the correct answer is nums[0].

Do the ranges overlap?

Say: Yes, in the middle (houses 1…n−2), and that is fine: we only need the maximum over each range separately.

2 · intermediate

Memoised recursion per range

time O(n)space O(n)

Same two ranges, each solved by a memoised rob-or-skip recursion with its own memo table, so every house is solved once per range.

int rob(vector<int>& nums) {
    int n = nums.size();
    if (n == 1) return nums[0];
    auto solve = [&](int first, int last) -> int {
        unordered_map<int, int> memo;
        function<int(int)> best = [&](int i) -> int {
            if (i > last) return 0;
            auto known = memo.find(i);
            if (known != memo.end()) return known->second;
            int result = max(nums[i] + best(i + 2), best(i + 1));
            memo[i] = result;
            return result;
        };
        return best(first);
    };
    return max(solve(0, n - 2), solve(1, n - 1));
}

public int rob(int[] nums) {
    int n = nums.length;
    if (n == 1) return nums[0];
    return Math.max(solve(nums, 0, n - 2), solve(nums, 1, n - 1));
}
private int solve(int[] nums, int first, int last) {
    Map<Integer, Integer> memo = new HashMap<>();
    return best(nums, memo, last, first);
}
private int best(int[] nums, Map<Integer, Integer> memo, int last, int i) {
    if (i > last) return 0;
    Integer known = memo.get(i);
    if (known != null) return known;
    int result = Math.max(nums[i] + best(nums, memo, last, i + 2), best(nums, memo, last, i + 1));
    memo.put(i, result);
    return result;
}

def rob(nums):
    n = len(nums)
    if n == 1: return nums[0]
    def solve(first, last):
        memo = {}
        def best(i):
            if i > last: return 0
            known = memo.get(i)
            if known is not None: return known
            result = max(nums[i] + best(i + 2), best(i + 1))
            memo[i] = result
            return result
        return best(first)
    return max(solve(0, n - 2), solve(1, n - 1))

function rob(nums: number[]): number {
  const n = nums.length;
  if (n === 1) return nums[0];
  const solve = (first: number, last: number): number => {
    const memo = new Map<number, number>();
    const best = (i: number): number => {
      if (i > last) return 0;
      const known = memo.get(i);
      if (known !== undefined) return known;
      const result = Math.max(nums[i] + best(i + 2), best(i + 1));
      memo.set(i, result);
      return result;
    };
    return best(first);
  };
  return Math.max(solve(0, n - 2), solve(1, n - 1));
}

Flaws & bottlenecks

A new memo for each range, since the right edge differs and cached values would be wrong across ranges.
Recursion depth up to n.
Closure and hash-table overhead for a simple linear pass.

Interviewer cross-questions

Why not share one memo between ranges?

Say: best(i) depends on where the range ends. A value computed for range A (which stops at n − 2) is wrong for range B (which stops at n − 1).

What is the complexity?

Say: Each range solves each house once: O(n) per range and O(n) overall.

How could you avoid the recursion?

Say: Fill an array from the last house of the range backwards, as the table approach does.

3 · advanced

Bottom-up table per range

time O(n)space O(n)

For each range fill dp from its last house to its first with dp[i] = max(nums[i] + dp[i + 2], dp[i + 1]), reading zeros past the range, and return the larger of the two answers.

int rob(vector<int>& nums) {
    int n = nums.size();
    if (n == 1) return nums[0];
    auto solve = [&](int first, int last) -> int {
        vector<int> dp(n + 2, 0);
        for (int i = last; i >= first; i--) {
            dp[i] = max(nums[i] + dp[i + 2], dp[i + 1]);
        }
        return dp[first];
    };
    return max(solve(0, n - 2), solve(1, n - 1));
}

public int rob(int[] nums) {
    int n = nums.length;
    if (n == 1) return nums[0];
    return Math.max(solve(nums, 0, n - 2), solve(nums, 1, n - 1));
}
private int solve(int[] nums, int first, int last) {
    int[] dp = new int[nums.length + 2];
    for (int i = last; i >= first; i--) {
        dp[i] = Math.max(nums[i] + dp[i + 2], dp[i + 1]);
    }
    return dp[first];
}

def rob(nums):
    n = len(nums)
    if n == 1: return nums[0]
    def solve(first, last):
        dp = [0] * (n + 2)
        for i in range(last, first - 1, -1):
            dp[i] = max(nums[i] + dp[i + 2], dp[i + 1])
        return dp[first]
    return max(solve(0, n - 2), solve(1, n - 1))

function rob(nums: number[]): number {
  const n = nums.length;
  if (n === 1) return nums[0];
  const solve = (first: number, last: number): number => {
    const dp = new Array<number>(n + 2).fill(0);
    for (let i = last; i >= first; i--) {
      dp[i] = Math.max(nums[i] + dp[i + 2], dp[i + 1]);
    }
    return dp[first];
  };
  return Math.max(solve(0, n - 2), solve(1, n - 1));
}

Flaws & bottlenecks

Allocates a new zeroed array for each range.
The zero padding past the range end is essential and easy to get wrong.
Still stores values that are needed only for a step or two.

Interviewer cross-questions

Why does dp need n + 2 cells even for a shorter range?

Say: The last house of the range reads dp[last + 1] and dp[last + 2]. Those cells must exist and be 0 (they were never written), which encodes "no houses beyond the range".

Is it correct that dp[last + 1] stays 0 for range A but not for range B?

Say: Each call allocates a fresh zeroed array, so both are 0 at the start. The array is never shared between the calls.

Can you do it in one pass?

Say: Yes: advance two independent rolling pairs (one for each range) in the same loop. It is the same work, merged.

4 · expert

Two rolling variables per range

time O(n)space O(1)

The same two-range reduction, with each straight street solved by a single loop that keeps only next1 and next2. Constant extra memory.

int rob(vector<int>& nums) {
    int n = nums.size();
    if (n == 1) return nums[0];
    auto solve = [&](int first, int last) -> int {
        int next1 = 0, next2 = 0;
        for (int i = last; i >= first; i--) {
            int cur = max(nums[i] + next2, next1);
            next2 = next1;
            next1 = cur;
        }
        return next1;
    };
    return max(solve(0, n - 2), solve(1, n - 1));
}

public int rob(int[] nums) {
    int n = nums.length;
    if (n == 1) return nums[0];
    return Math.max(solve(nums, 0, n - 2), solve(nums, 1, n - 1));
}
private int solve(int[] nums, int first, int last) {
    int next1 = 0, next2 = 0;
    for (int i = last; i >= first; i--) {
        int cur = Math.max(nums[i] + next2, next1);
        next2 = next1;
        next1 = cur;
    }
    return next1;
}

def rob(nums):
    n = len(nums)
    if n == 1: return nums[0]
    def solve(first, last):
        next1 = next2 = 0
        for i in range(last, first - 1, -1):
            cur = max(nums[i] + next2, next1)
            next2 = next1
            next1 = cur
        return next1
    return max(solve(0, n - 2), solve(1, n - 1))

function rob(nums: number[]): number {
  const n = nums.length;
  if (n === 1) return nums[0];
  const solve = (first: number, last: number): number => {
    let next1 = 0, next2 = 0;
    for (let i = last; i >= first; i--) {
      const cur = Math.max(nums[i] + next2, next1);
      next2 = next1;
      next1 = cur;
    }
    return next1;
  };
  return Math.max(solve(0, n - 2), solve(1, n - 1));
}

Flaws & bottlenecks

It cannot report which houses were robbed.
The single-house guard is required (otherwise the answer is 0).
Two passes over almost the same data; a merged single pass is possible but harder to read.

Interviewer cross-questions

How do you prove the reduction?

Say: A valid robbery cannot contain both house 0 and house n − 1, so it fits entirely inside range A or inside range B; and every robbery inside a range is valid on the circle (the ends are not both in it).

What about n = 2?

Say: Range A is house 0 only and range B is house 1 only, so the answer is max(nums[0], nums[1]), which is correct (the two houses are adjacent).

Could you extend to "k houses apart"?

Say: Yes: generalise the jump from i + 2 to i + k, and split the circle accordingly. The idea of removing the wrap-around constraint stays the same.

Synchronized code walkthrough

Showing: Recursion on the two ranges — shares the player above; click any step to jump.

int rob(vector<int>& nums) {
    int n = nums.size();
    if (n == 1) return nums[0];
    function<int(int, int)> best = [&](int i, int last) -> int {
        if (i > last) return 0;
        return max(nums[i] + best(i + 2, last), best(i + 1, last));
    };
    return max(best(0, n - 2), best(1, n - 1));
}

public int rob(int[] nums) {
    int n = nums.length;
    if (n == 1) return nums[0];
    return Math.max(best(nums, 0, n - 2), best(nums, 1, n - 1));
}
private int best(int[] nums, int i, int last) {
    if (i > last) return 0;
    return Math.max(nums[i] + best(nums, i + 2, last), best(nums, i + 1, last));
}

def rob(nums):
    n = len(nums)
    if n == 1: return nums[0]
    def best(i, last):
        if i > last: return 0
        return max(nums[i] + best(i + 2, last), best(i + 1, last))
    return max(best(0, n - 2), best(1, n - 1))

function rob(nums: number[]): number {
  const n = nums.length;
  if (n === 1) return nums[0];
  const best = (i: number, last: number): number => {
    if (i > last) return 0;
    return Math.max(nums[i] + best(i + 2, last), best(i + 1, last));
  };
  return Math.max(best(0, n - 2), best(1, n - 1));
}

int rob(vector<int>& nums) {
    int n = nums.size();
    if (n == 1) return nums[0];
    auto solve = [&](int first, int last) -> int {
        unordered_map<int, int> memo;
        function<int(int)> best = [&](int i) -> int {
            if (i > last) return 0;
            auto known = memo.find(i);
            if (known != memo.end()) return known->second;
            int result = max(nums[i] + best(i + 2), best(i + 1));
            memo[i] = result;
            return result;
        };
        return best(first);
    };
    return max(solve(0, n - 2), solve(1, n - 1));
}

public int rob(int[] nums) {
    int n = nums.length;
    if (n == 1) return nums[0];
    return Math.max(solve(nums, 0, n - 2), solve(nums, 1, n - 1));
}
private int solve(int[] nums, int first, int last) {
    Map<Integer, Integer> memo = new HashMap<>();
    return best(nums, memo, last, first);
}
private int best(int[] nums, Map<Integer, Integer> memo, int last, int i) {
    if (i > last) return 0;
    Integer known = memo.get(i);
    if (known != null) return known;
    int result = Math.max(nums[i] + best(nums, memo, last, i + 2), best(nums, memo, last, i + 1));
    memo.put(i, result);
    return result;
}

def rob(nums):
    n = len(nums)
    if n == 1: return nums[0]
    def solve(first, last):
        memo = {}
        def best(i):
            if i > last: return 0
            known = memo.get(i)
            if known is not None: return known
            result = max(nums[i] + best(i + 2), best(i + 1))
            memo[i] = result
            return result
        return best(first)
    return max(solve(0, n - 2), solve(1, n - 1))

function rob(nums: number[]): number {
  const n = nums.length;
  if (n === 1) return nums[0];
  const solve = (first: number, last: number): number => {
    const memo = new Map<number, number>();
    const best = (i: number): number => {
      if (i > last) return 0;
      const known = memo.get(i);
      if (known !== undefined) return known;
      const result = Math.max(nums[i] + best(i + 2), best(i + 1));
      memo.set(i, result);
      return result;
    };
    return best(first);
  };
  return Math.max(solve(0, n - 2), solve(1, n - 1));
}

int rob(vector<int>& nums) {
    int n = nums.size();
    if (n == 1) return nums[0];
    auto solve = [&](int first, int last) -> int {
        vector<int> dp(n + 2, 0);
        for (int i = last; i >= first; i--) {
            dp[i] = max(nums[i] + dp[i + 2], dp[i + 1]);
        }
        return dp[first];
    };
    return max(solve(0, n - 2), solve(1, n - 1));
}

public int rob(int[] nums) {
    int n = nums.length;
    if (n == 1) return nums[0];
    return Math.max(solve(nums, 0, n - 2), solve(nums, 1, n - 1));
}
private int solve(int[] nums, int first, int last) {
    int[] dp = new int[nums.length + 2];
    for (int i = last; i >= first; i--) {
        dp[i] = Math.max(nums[i] + dp[i + 2], dp[i + 1]);
    }
    return dp[first];
}

def rob(nums):
    n = len(nums)
    if n == 1: return nums[0]
    def solve(first, last):
        dp = [0] * (n + 2)
        for i in range(last, first - 1, -1):
            dp[i] = max(nums[i] + dp[i + 2], dp[i + 1])
        return dp[first]
    return max(solve(0, n - 2), solve(1, n - 1))

function rob(nums: number[]): number {
  const n = nums.length;
  if (n === 1) return nums[0];
  const solve = (first: number, last: number): number => {
    const dp = new Array<number>(n + 2).fill(0);
    for (let i = last; i >= first; i--) {
      dp[i] = Math.max(nums[i] + dp[i + 2], dp[i + 1]);
    }
    return dp[first];
  };
  return Math.max(solve(0, n - 2), solve(1, n - 1));
}

int rob(vector<int>& nums) {
    int n = nums.size();
    if (n == 1) return nums[0];
    auto solve = [&](int first, int last) -> int {
        int next1 = 0, next2 = 0;
        for (int i = last; i >= first; i--) {
            int cur = max(nums[i] + next2, next1);
            next2 = next1;
            next1 = cur;
        }
        return next1;
    };
    return max(solve(0, n - 2), solve(1, n - 1));
}

public int rob(int[] nums) {
    int n = nums.length;
    if (n == 1) return nums[0];
    return Math.max(solve(nums, 0, n - 2), solve(nums, 1, n - 1));
}
private int solve(int[] nums, int first, int last) {
    int next1 = 0, next2 = 0;
    for (int i = last; i >= first; i--) {
        int cur = Math.max(nums[i] + next2, next1);
        next2 = next1;
        next1 = cur;
    }
    return next1;
}

def rob(nums):
    n = len(nums)
    if n == 1: return nums[0]
    def solve(first, last):
        next1 = next2 = 0
        for i in range(last, first - 1, -1):
            cur = max(nums[i] + next2, next1)
            next2 = next1
            next1 = cur
        return next1
    return max(solve(0, n - 2), solve(1, n - 1))

function rob(nums: number[]): number {
  const n = nums.length;
  if (n === 1) return nums[0];
  const solve = (first: number, last: number): number => {
    let next1 = 0, next2 = 0;
    for (let i = last; i >= first; i--) {
      const cur = Math.max(nums[i] + next2, next1);
      next2 = next1;
      next1 = cur;
    }
    return next1;
  };
  return Math.max(solve(0, n - 2), solve(1, n - 1));
}