MediumDynamic programming

House Robber

Q: Why not just compare the sum of the even positions with the sum of the odd positions?

Because the best choice can skip two values in a row. For [7, 1, 2, 9] the even positions give 7 + 2 = 9 and the odd ones 1 + 9 = 10, but 7 + 9 = 16 beats both. The recurrence considers every gap length, which the alternating shortcut does not.

Q: Can I use functools.cache for the memoised version?

Yes: decorate a nested best(i) with @cache and drop the dictionary. On Python versions before 3.12 the cache wrapper itself counts towards the recursion limit as well, so the reachable depth can be lower than with the plain dictionary. At 400 values both versions are fine.

Q: What changes if the values sit in a circle, so the first and last are neighbours?

Run the two-variable loop twice, once on nums[1:] and once on nums[:-1], and return the larger result; a single value is its own answer. Either the first value or the last one is left out of every valid choice, and each run covers one of those cases.

You get an array of non-negative integers nums. Choose any set of positions, as long as no two chosen positions sit next to each other in the array, and return the largest possible sum of the values at the chosen positions. Think of a row of lockers along a corridor, each holding some coins, with an alarm that goes off when two neighbouring lockers are opened.

You may skip as many positions in a row as you like, so the best choice is not always every other value. Choosing nothing is allowed and sums to 0, so an empty array returns 0. Return only the sum, not the positions.

Examples

Input

nums = [2, 9, 3, 11, 4]

Output20WhyTake 9 and 11 (positions 1 and 3). The values at the even positions only give 2 + 3 + 4 = 9.

Input

nums = [7, 1, 2, 9]

Output16Why7 + 9 = 16 skips two positions in a row; neither 7 + 2 nor 1 + 9 does as well.

Constraints

Size: 0 ≤ nums.length ≤ 400
Values: 0 ≤ nums[i] ≤ 10,000
Answer: The sum always fits a signed 32-bit integer (at most 2,000,000).
Bound: The length stops at 400 so that a memoised recursion, one call deep per value, stays inside the default recursion limit of every language here.
Time limit: 10 s per run, all cases

Run your code 2 more times to open the solutions. The idea sticks better after an attempt.

3 reference approaches in Python, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: memoised recursion over positions

O(n) time · O(n) space

Let best(i) be the largest sum from the first i values. The last of them is either skipped, leaving best(i - 1), or taken, which rules out its neighbour and leaves best(i - 2) + nums[i - 1]. Written straight down, that recursion branches twice per call and grows exponentially; a dictionary of finished answers makes each i cost one visit. The recursion still goes n calls deep, which is why the length stops at 400 here, under Python's default limit of 1,000 frames.

def rob(nums: list[int]) -> int:
    memo: dict[int, int] = {}  # i -> best sum from the first i values

    def best(i: int) -> int:
        if i <= 0:
            return 0
        if i not in memo:
            memo[i] = max(best(i - 1), best(i - 2) + nums[i - 1])
        return memo[i]

    return best(len(nums))

2 · Bottom-up: fill a table of prefix answers

O(n) time · O(n) space

The same rule, filled from the left instead of asked from the right. table[i] holds the best sum from the first i values, so table[0] is 0 and table[1] is nums[0]. Every later entry reads the two before it, which are already final, and there is no recursion depth to worry about.

def rob(nums: list[int]) -> int:
    if not nums:
        return 0
    table = [0] * (len(nums) + 1)  # table[i] = best sum from the first i values
    table[1] = nums[0]
    for i in range(2, len(nums) + 1):
        table[i] = max(table[i - 1], table[i - 2] + nums[i - 1])
    return table[-1]

3 · Two variables: keep only the last two answers

O(n) time · O(1) space

recommended

Each table entry needs only the two before it, so keep just those: prev is the best sum one value back and curr the best so far. The tuple assignment prev, curr = curr, max(curr, prev + n) evaluates the right side before either name changes. An empty array never enters the loop and returns the starting 0.

def rob(nums: list[int]) -> int:
    prev, curr = 0, 0  # best sums ending one value back and at the current value
    for n in nums:
        prev, curr = curr, max(curr, prev + n)
    return curr

3 reference approaches in JavaScript, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: memoised recursion over positions

O(n) time · O(n) space

best(i) is the largest sum from the first i values: skip the last one and keep best(i - 1), or take it and add it to best(i - 2). Without a cache the two branches grow exponentially, so a Map stores every finished answer and each i is computed once. The check is memo.has(i), not a truthiness test, because a stored answer of 0 is a real answer.

function rob(nums) {
  const memo = new Map(); // i -> best sum from the first i values
  function best(i) {
    if (i <= 0) return 0;
    if (memo.has(i)) return memo.get(i);
    const value = Math.max(best(i - 1), best(i - 2) + nums[i - 1]);
    memo.set(i, value);
    return value;
  }
  return best(nums.length);
}

2 · Bottom-up: fill a table of prefix answers

O(n) time · O(n) space

Fill the answers from the left. new Array(n + 1).fill(0) makes a table where table[i] is the best sum from the first i values; table[1] is the first value, and every later entry reads the two before it. No recursion, so the length of the array is never a stack concern.

function rob(nums) {
  if (nums.length === 0) return 0;
  const table = new Array(nums.length + 1).fill(0); // table[i] = best sum from the first i values
  table[1] = nums[0];
  for (let i = 2; i <= nums.length; i++) {
    table[i] = Math.max(table[i - 1], table[i - 2] + nums[i - 1]);
  }
  return table[nums.length];
}

3 · Two variables: keep only the last two answers

O(n) time · O(1) space

recommended

Only the last two table entries are ever read, so two variables do the job. [prev, curr] = [curr, Math.max(curr, prev + n)] builds the right-hand array from the old values before destructuring it, the JavaScript version of a simultaneous assignment. An empty array skips the loop and returns 0.

function rob(nums) {
  let prev = 0; // best sum one value back
  let curr = 0; // best sum so far
  for (const n of nums) {
    [prev, curr] = [curr, Math.max(curr, prev + n)];
  }
  return curr;
}

3 reference approaches in TypeScript, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: memoised recursion over positions

O(n) time · O(n) space

best(i) is the largest sum from the first i values: either the last one is skipped, giving best(i - 1), or taken, giving best(i - 2) + nums[i - 1]. A Map<number, number> keeps each finished answer, so the two branches no longer multiply and every i is solved once.

function rob(nums: number[]): number {
  const memo = new Map<number, number>(); // i -> best sum from the first i values
  const best = (i: number): number => {
    if (i <= 0) return 0;
    const cached = memo.get(i);
    if (cached !== undefined) return cached;
    const value = Math.max(best(i - 1), best(i - 2) + nums[i - 1]);
    memo.set(i, value);
    return value;
  };
  return best(nums.length);
}

2 · Bottom-up: fill a table of prefix answers

O(n) time · O(n) space

The same recurrence filled from the left. table[i] is the best sum from the first i values, starting from table[0] = 0 and table[1] = nums[0]; each later entry reads two finished ones. The typed number[] table makes a stray undefined a compile-time question rather than a silent NaN.

function rob(nums: number[]): number {
  if (nums.length === 0) return 0;
  const table: number[] = new Array(nums.length + 1).fill(0); // table[i] = best sum from the first i values
  table[1] = nums[0];
  for (let i = 2; i <= nums.length; i++) {
    table[i] = Math.max(table[i - 1], table[i - 2] + nums[i - 1]);
  }
  return table[nums.length];
}

3 · Two variables: keep only the last two answers

O(n) time · O(1) space

recommended

Only the last two entries matter, so two numbers replace the table. Each step computes the new best before moving curr into prev, which keeps a value from being added to its own neighbour. An empty array returns the starting 0.

function rob(nums: number[]): number {
  let prev = 0; // best sum one value back
  let curr = 0; // best sum so far
  for (const n of nums) {
    const next = Math.max(curr, prev + n);
    prev = curr;
    curr = next;
  }
  return curr;
}

3 reference approaches in Java, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: memoised recursion over positions

O(n) time · O(n) space

best(nums, i, memo) returns the largest sum from the first i values: skip the last one and keep best(i - 1), or take it on top of best(i - 2). The cache is an Integer[], so an entry that was never computed is null and a real answer of 0 still counts as cached. With it, each i is solved once instead of exponentially often.

import java.util.*;

public class Main {
    static int rob(int[] nums) {
        Integer[] memo = new Integer[nums.length + 1]; // memo[i] = best sum from the first i values
        return best(nums, nums.length, memo);
    }

    static int best(int[] nums, int i, Integer[] memo) {
        if (i <= 0) return 0;
        if (memo[i] == null) {
            memo[i] = Math.max(best(nums, i - 1, memo), best(nums, i - 2, memo) + nums[i - 1]);
        }
        return memo[i];
    }
}

2 · Bottom-up: fill a table of prefix answers

O(n) time · O(n) space

The same rule filled from the left in a plain int[], which Java zero-fills, so table[0] is already 0. Set table[1] to the first value and let every later entry read the two before it. No recursion and no boxing.

import java.util.*;

public class Main {
    static int rob(int[] nums) {
        if (nums.length == 0) return 0;
        int[] table = new int[nums.length + 1]; // table[i] = best sum from the first i values
        table[1] = nums[0];
        for (int i = 2; i <= nums.length; i++) {
            table[i] = Math.max(table[i - 1], table[i - 2] + nums[i - 1]);
        }
        return table[nums.length];
    }
}

3 · Two variables: keep only the last two answers

O(n) time · O(1) space

recommended

Only the last two table entries are read, so two int locals replace the array. The new best goes into a temporary first; assigning prev = curr before computing it would let a value be added to its own neighbour.

import java.util.*;

public class Main {
    static int rob(int[] nums) {
        int prev = 0; // best sum one value back
        int curr = 0; // best sum so far
        for (int n : nums) {
            int next = Math.max(curr, prev + n);
            prev = curr;
            curr = next;
        }
        return curr;
    }
}

3 reference approaches in Go, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: memoised recursion over positions

O(n) time · O(n) space

best(i) is the largest sum from the first i values: skip the last and keep best(i-1), or take it on top of best(i-2). A recursive closure in Go must be declared with var before it is assigned, so it can refer to itself. The cache is a slice filled with -1, safe because every real answer is at least 0, and it turns the exponential branching into one visit per i.

package main

func rob(nums []int) int {
	memo := make([]int, len(nums)+1) // memo[i] = best sum from the first i values
	for i := range memo {
		memo[i] = -1
	}
	var best func(i int) int
	best = func(i int) int {
		if i <= 0 {
			return 0
		}
		if memo[i] < 0 {
			memo[i] = max(best(i-1), best(i-2)+nums[i-1])
		}
		return memo[i]
	}
	return best(len(nums))
}

2 · Bottom-up: fill a table of prefix answers

O(n) time · O(n) space

The same rule filled from the left. make([]int, n+1) zeroes every entry, so table[0] is already 0; table[1] takes the first value and each later entry reads two finished ones. The built-in max (Go 1.21 and later) keeps the line short.

package main

func rob(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	table := make([]int, len(nums)+1) // table[i] = best sum from the first i values
	table[1] = nums[0]
	for i := 2; i <= len(nums); i++ {
		table[i] = max(table[i-1], table[i-2]+nums[i-1])
	}
	return table[len(nums)]
}

3 · Two variables: keep only the last two answers

O(n) time · O(1) space

recommended

Only the last two answers are ever read, so keep two integers. Go's tuple assignment prev, curr = curr, max(curr, prev+n) evaluates the whole right side first, so no temporary is needed. A nil or empty slice skips the loop and returns 0.

package main

func rob(nums []int) int {
	prev, curr := 0, 0 // best sums one value back and so far
	for _, n := range nums {
		prev, curr = curr, max(curr, prev+n)
	}
	return curr
}

3 reference approaches in C#, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: memoised recursion over positions

O(n) time · O(n) space

Best(nums, i, memo) is the largest sum from the first i values: skip the last and keep Best(i - 1), or take it on top of Best(i - 2). The cache is an int?[], so an entry that was never computed is null and a real 0 still counts. Each i is then solved once instead of exponentially often.

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    public static int Rob(int[] nums)
    {
        var memo = new int?[nums.Length + 1]; // memo[i] = best sum from the first i values
        return Best(nums, nums.Length, memo);
    }

    static int Best(int[] nums, int i, int?[] memo)
    {
        if (i <= 0) return 0;
        memo[i] ??= Math.Max(Best(nums, i - 1, memo), Best(nums, i - 2, memo) + nums[i - 1]);
        return memo[i].Value;
    }
}

2 · Bottom-up: fill a table of prefix answers

O(n) time · O(n) space

The same rule filled from the left. A new int[] is zeroed, so table[0] is already 0; table[1] takes the first value and every later entry reads the two before it. No recursion and no nullable values.

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    public static int Rob(int[] nums)
    {
        if (nums.Length == 0) return 0;
        var table = new int[nums.Length + 1]; // table[i] = best sum from the first i values
        table[1] = nums[0];
        for (int i = 2; i <= nums.Length; i++)
        {
            table[i] = Math.Max(table[i - 1], table[i - 2] + nums[i - 1]);
        }
        return table[nums.Length];
    }
}

3 · Two variables: keep only the last two answers

O(n) time · O(1) space

recommended

Only the last two answers are read, so two locals replace the table. The tuple assignment (prev, curr) = (curr, Math.Max(curr, prev + n)) evaluates the right side before assigning either variable. An empty array skips the loop and returns 0.

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    public static int Rob(int[] nums)
    {
        int prev = 0, curr = 0; // best sums one value back and so far
        foreach (int n in nums)
        {
            (prev, curr) = (curr, Math.Max(curr, prev + n));
        }
        return curr;
    }
}

3 reference approaches in C++, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: memoised recursion over positions

O(n) time · O(n) space

best(nums, i, memo) is the largest sum from the first i values: skip the last and keep best(i - 1), or take it on top of best(i - 2). The cache is a vector<int> filled with -1, safe because every real answer is at least 0, and both the input and the cache go by reference so no call copies them.

#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    int rob(vector<int>& nums) {
        vector<int> memo(nums.size() + 1, -1); // memo[i] = best sum from the first i values
        return best(nums, (int)nums.size(), memo);
    }

    int best(vector<int>& nums, int i, vector<int>& memo) {
        if (i <= 0) return 0;
        if (memo[i] < 0) {
            memo[i] = max(best(nums, i - 1, memo), best(nums, i - 2, memo) + nums[i - 1]);
        }
        return memo[i];
    }
};

2 · Bottom-up: fill a table of prefix answers

O(n) time · O(n) space

The same rule filled from the left. vector<int> table(n + 1, 0) sets table[0] to 0; table[1] takes the first value and each later entry reads two finished ones. The early return guards nums[0] on an empty vector.

#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = (int)nums.size();
        if (n == 0) return 0;
        vector<int> table(n + 1, 0); // table[i] = best sum from the first i values
        table[1] = nums[0];
        for (int i = 2; i <= n; i++) {
            table[i] = max(table[i - 1], table[i - 2] + nums[i - 1]);
        }
        return table[n];
    }
};

3 · Two variables: keep only the last two answers

O(n) time · O(1) space

recommended

Only the last two answers are read, so two ints replace the table. The new best goes into next before prev moves up; updating prev first would let a value be added to its own neighbour. An empty vector returns 0.

#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    int rob(vector<int>& nums) {
        int prev = 0, curr = 0; // best sums one value back and so far
        for (int n : nums) {
            int next = max(curr, prev + n);
            prev = curr;
            curr = next;
        }
        return curr;
    }
};

3 reference approaches in C, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: memoised recursion over positions

O(n) time · O(n) space

best(i) is the largest sum from the first i values: skip the last one and keep best(i - 1), or take it on top of best(i - 2). A static helper carries the array and a malloc'ed cache filled with -1, a safe "not computed" mark because every real answer is at least 0. The cache is freed before returning.

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

static int maxInt(int a, int b) { return a > b ? a : b; }

/* best sum from the first i values; memo[i] == -1 means not computed yet */
static int best(const int* nums, int i, int* memo) {
    if (i <= 0) return 0;
    if (memo[i] == -1) {
        memo[i] = maxInt(best(nums, i - 1, memo), best(nums, i - 2, memo) + nums[i - 1]);
    }
    return memo[i];
}

int rob(int* nums, int numsSize) {
    int* memo = malloc((numsSize + 1) * sizeof *memo);
    for (int i = 0; i <= numsSize; i++) memo[i] = -1;
    int answer = best(nums, numsSize, memo);
    free(memo);
    return answer;
}

2 · Bottom-up: fill a table of prefix answers

O(n) time · O(n) space

The same rule filled from the left. calloc zeroes the table, so table[0] is already 0; set table[1] to the first value and let every later entry read the two before it. The size check comes first: with an empty array nums may be NULL, and reading nums[0] would crash.

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

int rob(int* nums, int numsSize) {
    if (numsSize == 0) return 0;
    int* table = calloc(numsSize + 1, sizeof *table); /* table[i] = best sum from the first i values */
    table[1] = nums[0];
    for (int i = 2; i <= numsSize; i++) {
        int take = table[i - 2] + nums[i - 1];
        table[i] = take > table[i - 1] ? take : table[i - 1];
    }
    int answer = table[numsSize];
    free(table);
    return answer;
}

3 · Two variables: keep only the last two answers

O(n) time · O(1) space

recommended

Only the last two table entries are ever read, so two int locals replace the array and nothing is allocated. Compute the new best into next before shifting prev; an empty array never enters the loop, never touches nums and returns 0.

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

int rob(int* nums, int numsSize) {
    int prev = 0; /* best sum one value back */
    int curr = 0; /* best sum so far */
    for (int i = 0; i < numsSize; i++) {
        int next = prev + nums[i] > curr ? prev + nums[i] : curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

3 reference approaches in Kotlin, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: memoised recursion over positions

O(n) time · O(n) space

A local fun best(i: Int) returns the largest sum from the first i values: skip the last one and keep best(i - 1), or take it on top of best(i - 2). It closes over an IntArray(nums.size + 1) { -1 } cache; -1 marks an entry not computed yet, safe because every answer is at least 0.

class Solution {
    fun rob(nums: IntArray): Int {
        val memo = IntArray(nums.size + 1) { -1 } // memo[i] = best sum from the first i values

        fun best(i: Int): Int {
            if (i <= 0) return 0
            if (memo[i] == -1) {
                memo[i] = maxOf(best(i - 1), best(i - 2) + nums[i - 1])
            }
            return memo[i]
        }

        return best(nums.size)
    }
}

2 · Bottom-up: fill a table of prefix answers

O(n) time · O(n) space

The same rule filled from the left. IntArray(n + 1) starts at zeros, so table[0] is already 0; set table[1] to the first value and loop for (i in 2..n), each entry reading the two before it. The empty check comes first so nums[0] is never read on an empty array.

class Solution {
    fun rob(nums: IntArray): Int {
        if (nums.isEmpty()) return 0
        val n = nums.size
        val table = IntArray(n + 1) // table[i] = best sum from the first i values
        table[1] = nums[0]
        for (i in 2..n) {
            table[i] = maxOf(table[i - 1], table[i - 2] + nums[i - 1])
        }
        return table[n]
    }
}

3 · Two variables: keep only the last two answers

O(n) time · O(1) space

recommended

Only the last two entries are read, so two vars replace the table. Compute the new best into a val before shifting prev, so a value is never added to its own neighbour. An empty array skips the loop and returns 0.

class Solution {
    fun rob(nums: IntArray): Int {
        var prev = 0 // best sum one value back
        var curr = 0 // best sum so far
        for (n in nums) {
            val next = maxOf(curr, prev + n)
            prev = curr
            curr = next
        }
        return curr
    }
}

3 reference approaches in Rust, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: memoised recursion over positions

O(n) time · O(n) space

best(nums, i, memo) returns the largest sum from the first i values: skip the last one and keep best(i - 1), or take it on top of best(i - 2). Closures cannot recurse in Rust, so it is an associated function that borrows the slice and a &mut Vec<Option<i32>> cache, where None means not computed. i is a usize, so the base case is i == 0 and i == 1, never a negative index.

impl Solution {
    pub fn rob(nums: Vec<i32>) -> i32 {
        let mut memo = vec![None; nums.len() + 1]; // memo[i] = best sum from the first i values
        Self::best(&nums, nums.len(), &mut memo)
    }

    fn best(nums: &[i32], i: usize, memo: &mut Vec<Option<i32>>) -> i32 {
        if i == 0 {
            return 0;
        }
        if i == 1 {
            return nums[0];
        }
        if let Some(v) = memo[i] {
            return v;
        }
        let v = Self::best(nums, i - 1, memo).max(Self::best(nums, i - 2, memo) + nums[i - 1]);
        memo[i] = Some(v);
        v
    }
}

2 · Bottom-up: fill a table of prefix answers

O(n) time · O(n) space

The same rule filled from the left in a vec![0; n + 1], so table[0] is already 0. Set table[1] to the first value and let every later entry read the two before it. The empty check comes first; indexing nums[0] on an empty Vec would panic.

impl Solution {
    pub fn rob(nums: Vec<i32>) -> i32 {
        if nums.is_empty() {
            return 0;
        }
        let n = nums.len();
        let mut table = vec![0; n + 1]; // table[i] = best sum from the first i values
        table[1] = nums[0];
        for i in 2..=n {
            table[i] = table[i - 1].max(table[i - 2] + nums[i - 1]);
        }
        table[n]
    }
}

3 · Two variables: keep only the last two answers

O(n) time · O(1) space

recommended

Only the last two entries are ever read, so carry them as a tuple through fold: each step turns (prev, curr) into (curr, curr.max(prev + n)), built from the old values. An empty Vec returns the starting (0, 0), and .1 picks the best sum.

impl Solution {
    pub fn rob(nums: Vec<i32>) -> i32 {
        // (best sum one value back, best sum so far)
        nums.iter()
            .fold((0, 0), |(prev, curr), &n| (curr, curr.max(prev + n)))
            .1
    }
}

3 reference approaches in Swift, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: memoised recursion over positions

O(n) time · O(n) space

A nested func best(_ i: Int) returns the largest sum from the first i values: skip the last one and keep best(i - 1), or take it on top of best(i - 2). It captures a local var memo = [Int](repeating: -1, count: nums.count + 1), where -1 marks an entry not computed yet; every real answer is at least 0, so the mark is never ambiguous.

class Solution {
    func rob(_ nums: [Int]) -> Int {
        var memo = [Int](repeating: -1, count: nums.count + 1) // memo[i] = best sum from the first i values

        func best(_ i: Int) -> Int {
            guard i > 0 else { return 0 }
            if memo[i] == -1 {
                memo[i] = max(best(i - 1), best(i - 2) + nums[i - 1])
            }
            return memo[i]
        }

        return best(nums.count)
    }
}

2 · Bottom-up: fill a table of prefix answers

O(n) time · O(n) space

The same rule filled from the left. The guard returns 0 for an empty array, since nums[0] would trap and 2...n with n below 2 is an invalid range. Then table[1] is the first value and every later entry reads the two before it.

class Solution {
    func rob(_ nums: [Int]) -> Int {
        guard !nums.isEmpty else { return 0 }
        let n = nums.count
        var table = [Int](repeating: 0, count: n + 1) // table[i] = best sum from the first i values
        table[1] = nums[0]
        var i = 2
        while i <= n {
            table[i] = max(table[i - 1], table[i - 2] + nums[i - 1])
            i += 1
        }
        return table[n]
    }
}

3 · Two variables: keep only the last two answers

O(n) time · O(1) space

recommended

Only the last two entries are ever read, so two vars replace the table. The tuple assignment (prev, curr) = (curr, max(curr, prev + n)) builds the right side from the old values before either changes. An empty array skips the loop and returns 0.

class Solution {
    func rob(_ nums: [Int]) -> Int {
        var prev = 0 // best sum one value back
        var curr = 0 // best sum so far
        for n in nums {
            (prev, curr) = (curr, max(curr, prev + n))
        }
        return curr
    }
}

3 reference approaches in PHP, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: memoised recursion over positions

O(n) time · O(n) space

best($nums, $i, $memo) returns the largest sum from the first $i values: skip the last one and keep best($i - 1), or take it on top of best($i - 2). The cache is passed as array &$memo; without the & each call would get its own copy and the stored answers would be lost. isset tells a computed entry from a missing one, so a real answer of 0 still counts.

<?php

class Solution {
    /**
     * @param int[] $nums
     * @return int
     */
    function rob(array $nums): int {
        $memo = []; // $memo[$i] = best sum from the first $i values
        return $this->best($nums, count($nums), $memo);
    }

    private function best(array $nums, int $i, array &$memo): int {
        if ($i <= 0) {
            return 0;
        }
        if (!isset($memo[$i])) {
            $memo[$i] = max($this->best($nums, $i - 1, $memo), $this->best($nums, $i - 2, $memo) + $nums[$i - 1]);
        }
        return $memo[$i];
    }
}

2 · Bottom-up: fill a table of prefix answers

O(n) time · O(n) space

The same rule filled from the left. array_fill(0, $n + 1, 0) makes the table with $table[0] already 0; set $table[1] to the first value and let every later entry read the two before it. The empty check comes first, since $nums[0] on an empty array raises an "Undefined array key" warning.

<?php

class Solution {
    /**
     * @param int[] $nums
     * @return int
     */
    function rob(array $nums): int {
        $n = count($nums);
        if ($n === 0) {
            return 0;
        }
        $table = array_fill(0, $n + 1, 0); // $table[$i] = best sum from the first $i values
        $table[1] = $nums[0];
        for ($i = 2; $i <= $n; $i++) {
            $table[$i] = max($table[$i - 1], $table[$i - 2] + $nums[$i - 1]);
        }
        return $table[$n];
    }
}

3 · Two variables: keep only the last two answers

O(n) time · O(1) space

recommended

Only the last two entries are ever read, so two variables replace the table. The list assignment [$prev, $curr] = [$curr, max($curr, $prev + $n)]; builds the right-hand array from the old values before either variable changes. An empty array skips the loop and returns 0.

<?php

class Solution {
    /**
     * @param int[] $nums
     * @return int
     */
    function rob(array $nums): int {
        $prev = 0; // best sum one value back
        $curr = 0; // best sum so far
        foreach ($nums as $n) {
            [$prev, $curr] = [$curr, max($curr, $prev + $n)];
        }
        return $curr;
    }
}

3 reference approaches in Dart, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: memoised recursion over positions

O(n) time · O(n) space

A local function best(i) returns the largest sum from the first i values: skip the last one and keep best(i - 1), or take it on top of best(i - 2). It closes over List<int>.filled(n + 1, -1), where -1 marks an entry not computed yet, safe because every answer is at least 0. Dart local functions can call themselves by name.

import 'dart:math';

class Solution {
  int rob(List<int> nums) {
    final memo = List<int>.filled(nums.length + 1, -1); // memo[i] = best sum from the first i values

    int best(int i) {
      if (i <= 0) return 0;
      if (memo[i] == -1) {
        memo[i] = max(best(i - 1), best(i - 2) + nums[i - 1]);
      }
      return memo[i];
    }

    return best(nums.length);
  }
}

2 · Bottom-up: fill a table of prefix answers

O(n) time · O(n) space

The same rule filled from the left. List<int>.filled(n + 1, 0) gives a fixed-length table with table[0] already 0; set table[1] to the first value and let every later entry read the two before it. The empty check comes first, since nums[0] on an empty list throws a RangeError.

import 'dart:math';

class Solution {
  int rob(List<int> nums) {
    if (nums.isEmpty) return 0;
    final n = nums.length;
    final table = List<int>.filled(n + 1, 0); // table[i] = best sum from the first i values
    table[1] = nums[0];
    for (var i = 2; i <= n; i++) {
      table[i] = max(table[i - 1], table[i - 2] + nums[i - 1]);
    }
    return table[n];
  }
}

3 · Two variables: keep only the last two answers

O(n) time · O(1) space

recommended

Only the last two entries are ever read, so two variables replace the table. Compute the new best into next before shifting prev, so a value is never added to its own neighbour. An empty list skips the loop and returns 0.

import 'dart:math';

class Solution {
  int rob(List<int> nums) {
    var prev = 0; // best sum one value back
    var curr = 0; // best sum so far
    for (final n in nums) {
      final next = max(curr, prev + n);
      prev = curr;
      curr = next;
    }
    return curr;
  }
}

3 reference approaches in Scala, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: memoised recursion over positions

O(n) time · O(n) space

A local def best(i: Int) returns the largest sum from the first i values: skip the last one and keep best(i - 1), or take it on top of best(i - 2). It closes over Array.fill(nums.length + 1)(-1), where -1 marks an entry not computed yet, safe because every answer is at least 0. The body is one if expression, so no return is needed.

object Solution {
  def rob(nums: Array[Int]): Int = {
    val memo = Array.fill(nums.length + 1)(-1) // memo(i) = best sum from the first i values

    def best(i: Int): Int =
      if (i <= 0) 0
      else {
        if (memo(i) == -1) memo(i) = math.max(best(i - 1), best(i - 2) + nums(i - 1))
        memo(i)
      }

    best(nums.length)
  }
}

2 · Bottom-up: fill a table of prefix answers

O(n) time · O(n) space

The same rule filled from the left. new Array[Int](n + 1) starts at zeros, so table(0) is already 0; set table(1) to the first value and let every later entry read the two before it. An empty array returns 0 from the outer if before nums(0) is read, and 2 to n is simply empty when n is 1.

object Solution {
  def rob(nums: Array[Int]): Int =
    if (nums.isEmpty) 0
    else {
      val n = nums.length
      val table = new Array[Int](n + 1) // table(i) = best sum from the first i values
      table(1) = nums(0)
      for (i <- 2 to n) table(i) = math.max(table(i - 1), table(i - 2) + nums(i - 1))
      table(n)
    }
}

3 · Two variables: keep only the last two answers

O(n) time · O(1) space

recommended

Only the last two entries are ever read, so carry them as a pair through foldLeft: each step turns (prev, curr) into (curr, math.max(curr, prev + n)), built from the old values. An empty array returns the starting (0, 0), and ._2 picks the best sum.

object Solution {
  def rob(nums: Array[Int]): Int =
    // (best sum one value back, best sum so far)
    nums.foldLeft((0, 0)) { case ((prev, curr), n) =>
      (curr, math.max(curr, prev + n))
    }._2
}

FAQ for Python

Why not just compare the sum of the even positions with the sum of the odd positions?

Because the best choice can skip two values in a row. For [7, 1, 2, 9] the even positions give 7 + 2 = 9 and the odd ones 1 + 9 = 10, but 7 + 9 = 16 beats both. The recurrence considers every gap length, which the alternating shortcut does not.

Can I use functools.cache for the memoised version?

Yes: decorate a nested best(i) with @cache and drop the dictionary. On Python versions before 3.12 the cache wrapper itself counts towards the recursion limit as well, so the reachable depth can be lower than with the plain dictionary. At 400 values both versions are fine.

How do I also return which positions were chosen?

Keep the full table from the bottom-up version, then walk it backwards: at i, if table[i] == table[i - 1] the value at i - 1 was skipped, so step to i - 1; otherwise it was taken, so record i - 1 and step to i - 2. Reverse the recorded list at the end.

What changes if the values sit in a circle, so the first and last are neighbours?

Run the two-variable loop twice, once on nums[1:] and once on nums[:-1], and return the larger result; a single value is its own answer. Either the first value or the last one is left out of every valid choice, and each run covers one of those cases.

Does the order of the tuple assignment matter?

Only in that both sides must be read from the old values, which a tuple assignment guarantees. Writing prev = curr and then curr = max(curr, prev + n) on two lines would compute curr + n from the overwritten prev, which lets two neighbouring values both count.

Keep going

Word Break34 / 40 · Dynamic programming · Medium

Try House Robber in JavaScript (House Robber in JavaScript), TypeScript (House Robber in TypeScript), Java (House Robber in Java), Go (House Robber in Go), C# (House Robber in C#), C++ (House Robber in C++), C (House Robber in C), Kotlin (House Robber in Kotlin), Rust (House Robber in Rust), Swift (House Robber in Swift), PHP (House Robber in PHP), Ruby (House Robber in Ruby), Dart (House Robber in Dart) or Scala (House Robber in Scala) instead.

rob.py

Python 3.14

Not run yet

+ 7 hidden

Input

nums = [2, 9, 3, 11, 4]

Expected

Take 9 and 11 (positions 1 and 3). The values at the even positions only give 2 + 3 + 4 = 9.