Workspace Code & DSA
Learning pathsPricingA
← DSA problem library

DSA-128 · FOCUSED PRACTICE

House Robber

Intermediate · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 9863 deterministic checks. Learner drafts are not executed.

Understand the problem

nums[i] is the nonnegative money in house i on a straight street. Choose any subset of houses with no two neighboring indices and return the maximum total money. You may choose no houses.

  • nums is a non-null int[] with 0 through 100,000 entries, all nonnegative and allowed up to Integer.MAX_VALUE. Null throws NullPointerException. Negative entries or excessive length throw IllegalArgumentException after read-only validation.
  • Adjacency means consecutive indices, independent of equal values. The street is linear: its first and last houses are not neighbors unless their indices are consecutive. Return 0 for an empty street; a single house can be selected.
  • Return the exact maximum as long without modifying nums or returning selected indices. Equal-optimum subsets need no tie rule because this API returns a number. Empty selection is legal. The recursive baseline is educational and only verified on bounded small arrays.

Examples

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

    Indices 0,2,4 give 2+9+1=12. The largest single house is not a complete optimum.

  2. Input: nums=[2,1,1,2]
    Output: 4

    Take both endpoints. Selecting the first locally large house and then the next available one need not be optimal.

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

    Take indices 0 and 2. The best prefix does not have to include its last house.

  4. Input: nums=[2147483647,0,2147483647]
    Output: 4294967294

    Nonadjacent endpoint values sum beyond int and require long arithmetic.

Before you start

  • Include/exclude decisions and adjacency constraints
  • Prefix optima, empty selection, and long sums

Recognize the structure

A decision at the final house either excludes it, preserving the previous prefix optimum, or includes it, forcing its immediate predecessor out. All compatible earlier choices are summarized by the optimum two prefixes back. This is a maximum-weight independent set on a path. A prefix state is enough; storing every chosen subset repeats work, and a local largest-house rule does not preserve the best compatible total.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

No unsaved text changes · 115/20,000 characters

Self-review

Use the checklist to test your explanation. Checks apply to this visit.

Try before revealing

Hint 1

Divide feasible subsets according to whether they contain the final house.

Hint 2

If you take index i, which prefix remains compatible? If you skip it, which prefix remains?

Hint 3

Compute max(previousOne, previousTwo+nums[i]) using the old registers, then shift.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Enumerate take or skip from the next undecided index

At index i, either skip to i+1 or take nums[i] and continue at i+2. Return zero past the array. The branches enumerate all feasible subsets without needing a used array. Different prefixes repeatedly request the same suffix, so the recursion performs exponential work; O(2^n) is a safe upper bound with O(n+1) live call-stack depth. Cast nums[i] to long before adding a recursive result. A separate test oracle enumerates bit masks, rejects adjacent selected bits, and sums valid subsets; it does not use this recursive recurrence. Large tests exercise only the iterative reference.

Improve the baseline

Use prefix length rather than a last-picked flag

Let B(k) be the greatest total available using only the first k houses, with indices 0..k−1. B(0)=0. To write the first transition uniformly, the two initial registers represent the empty history before any house. A value of zero is valid, not an unreachable sentinel, because choosing nothing is always allowed.

Partition feasible subsets by the current house

For index i, every valid subset either omits i or includes it. Omission gives B(i). Inclusion forbids i−1 and gives nums[i]+B(i−1), interpreting an empty earlier prefix as zero at i=0. Thus B(i+1)=max(skip,take). This is a prefix optimum, not the best total that must end at i; the latter would have different semantics.

Compare complete alternatives

For [2,7,9,3,1], the conceptual prefix sequence is [0,2,7,11,11,12]. At index 3, take=7+3=10 loses to skip=11, so the optimum keeps a subset ending earlier. At index 4, take=11+1=12 wins. No choice commits a physical subset; each state summarizes all feasible prefixes.

Compress and preserve old meanings

Before processing i, previousOne=B(i), and previousTwo=B(max(0,i−1)). Compute take=previousTwo+nums[i] and skip=previousOne. Only after next=max(skip,take) is known, assign previousTwo=previousOne and previousOne=next. Shifting first would let the take candidate combine adjacent houses.

Keep value and witness concerns separate

The rolling number does not encode a unique chosen subset. Ties are harmless for the numeric answer but matter if indices must be reconstructed. Full prefix history and a deterministic tie decision can recover a witness. With n≤100000 and nonnegative int money, the loose n×Integer.MAX_VALUE bound is safely inside long, including both intermediate candidates.

Why it is correct

Empty prefix

No houses yields exactly zero, attained by the empty selection. The initialized zero registers make the first take and skip candidates valid. Nonnegative input guarantees no negative optimum, though allowing an empty set would also handle signed money with adjusted numeric bounds.

Exhaustive include/exclude partition

For a feasible subset of the first i+1 houses, omitting i limits its value to B(i). Including i excludes i−1 and limits its earlier part to B(i−1), so its total is at most nums[i]+B(i−1). Conversely an optimal subset from either predecessor can realize its candidate without violating adjacency. The larger candidate is exactly B(i+1).

Loop invariant and return

Initially both relevant empty-prefix optima are zero. Assuming the old registers describe their prefixes, the two candidates and delayed shift preserve the invariant. The loop advances once per index and ends with previousOne=B(n). Validation and all loops are finite, input entries are read-only, and long arithmetic covers every possible sum under the contract.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.Objects;

public final class Solution {
    private Solution() {}
    private static void validate(int[] nums) {
        Objects.requireNonNull(nums, "nums");
        if (nums.length > 100_000) throw new IllegalArgumentException("too many houses");
        for (int value : nums) if (value < 0) throw new IllegalArgumentException("negative money");
    }
    public static long rob(int[] nums) {
        validate(nums);
        long previousTwo = 0, previousOne = 0;
        for (int index = 0; index < nums.length; index++) {
            long take = previousTwo + nums[index];
            long skip = previousOne;
            long next = Math.max(skip, take);
            previousTwo = previousOne;
            previousOne = next;
        }
        return previousOne;
    }
    // Baseline: include/exclude enumeration. Small inputs only.
    public static long baseline(int[] nums) {
        validate(nums);
        return enumerate(nums, 0);
    }
    private static long enumerate(int[] nums, int index) {
        if (index >= nums.length) return 0;
        return Math.max(enumerate(nums, index + 1), (long) nums[index] + enumerate(nums, index + 2));
    }
}

Read the meaningful blocks

Validate values as well as shape

Null, length, and every negative value are checked before optimization. Values may equal Integer.MAX_VALUE, so int arithmetic is unsuitable even when each individual house is valid.

Name take and skip using the old frontier

take reads only the two-back optimum plus the current int promoted to long; skip reads the one-back optimum. These are alternatives, not amounts to add together. Keeping them distinct helps review the adjacency argument.

Shift after computing the maximum

previousTwo becomes the old previousOne and previousOne becomes next. Returning previousOne after all indices yields the maximum for the whole street. Empty input naturally returns the initialized zero.

Complexity

Validation and one pass of constant-work transitions cost O(n+1) time. The reference stores a constant number of long values: O(1) auxiliary space, with one long output. The walkthrough table is a conceptual history and is not allocated by the Java method.

The take/skip baseline has O(2^n) upper-bound time and O(n+1) call-stack depth. A memoized recursive solution uses O(n) cache and stack, while a full bottom-up table uses O(n) storage and makes witness reconstruction straightforward. None of these choices changes the number of houses in the input.

Exact-state walkthroughs

Reveal normal and boundary traces

Skip and take can win at different houses

Input: [2,7,9,3,1] · Maximum linear nonadjacent total: 12

Step 1 of 14: Validate the complete input before any base-case result.

Bounds, null, and value rules belong to the API. These displayed fixtures satisfy the contract; no caller input is changed.

House Robber — compare take and skip prefixes

Phase: validated.

B(k+1) = max(B(k), B(max(0,k−1)) + nums[index])

The complete input satisfies the documented contract. The next step establishes base states before any transition.

Original house indices and money — index identity determines adjacency.

  • 0: 2available in this pass
  • 1: 7available in this pass
  • 2: 9available in this pass
  • 3: 3available in this pass
  • 4: 1available in this pass

Input entries stay unchanged. Candidate and commit steps separate reading the old frontier from updating it. Full state tables and the equivalent static walkthrough appear below.

State after this step
VariableValue
input[2,7,9,3,1]
phase"validated"
caseResults[]
See the affected Java block
 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     private Solution() {}
 5     private static void validate(int[] nums) {
 6         Objects.requireNonNull(nums, "nums");
 7         if (nums.length > 100_000) throw new IllegalArgumentException("too many houses");
 8         for (int value : nums) if (value < 0) throw new IllegalArgumentException("negative money");
 9     }
10     public static long rob(int[] nums) {
11         validate(nums);
12         long previousTwo = 0, previousOne = 0;
13         for (int index = 0; index < nums.length; index++) {
14             long take = previousTwo + nums[index];
15             long skip = previousOne;
16             long next = Math.max(skip, take);
17             previousTwo = previousOne;
18             previousOne = next;
19         }
20         return previousOne;
21     }
22     // Baseline: include/exclude enumeration. Small inputs only.
23     public static long baseline(int[] nums) {
24         validate(nums);
25         return enumerate(nums, 0);
26     }
27     private static long enumerate(int[] nums, int index) {
28         if (index >= nums.length) return 0;
29         return Math.max(enumerate(nums, index + 1), (long) nums[index] + enumerate(nums, index + 2));
30     }
31 }
32

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace
  1. Validate the complete input before any base-case result.

    Bounds, null, and value rules belong to the API. These displayed fixtures satisfy the contract; no caller input is changed.

    input
    [2,7,9,3,1]
    phase
    "validated"
    caseResults
    []
  2. Reset an empty prefix for this half-open path range.

    Only original indices start..end−1 belong to this pass. Prefix length zero has optimum zero. Both registers reset independently of all earlier passes.

    input
    [2,7,9,3,1]
    phase
    "range-start"
    caseResults
    []
    start
    0
    end
    5
    caseLabel
    "Whole linear street"
    table
    [0,null,null,null,null,null]
    previousTwo
    0
    previousOne
    0
    position
    -1
  3. Compare taking this house with skipping it.

    take uses the two-back prefix and this house; skip uses the one-back prefix. A prefix optimum need not include its last house. Both candidates use the old pair.

    input
    [2,7,9,3,1]
    phase
    "candidate"
    caseResults
    []
    start
    0
    end
    5
    caseLabel
    "Whole linear street"
    table
    [0,null,null,null,null,null]
    previousTwo
    0
    previousOne
    0
    position
    0
    two
    2
    one
    0
    next
    2
  4. Commit the best prefix before advancing to the next house.

    The two live registers now describe the previous and current prefix lengths relative to this range. The full table shown here is explanatory history; Java uses constant workspace.

    input
    [2,7,9,3,1]
    phase
    "commit"
    caseResults
    []
    start
    0
    end
    5
    caseLabel
    "Whole linear street"
    table
    [0,2,null,null,null,null]
    previousTwo
    0
    previousOne
    2
    position
    0
    two
    2
    one
    0
    next
    2
  5. Compare taking this house with skipping it.

    take uses the two-back prefix and this house; skip uses the one-back prefix. A prefix optimum need not include its last house. Both candidates use the old pair.

    input
    [2,7,9,3,1]
    phase
    "candidate"
    caseResults
    []
    start
    0
    end
    5
    caseLabel
    "Whole linear street"
    table
    [0,2,null,null,null,null]
    previousTwo
    0
    previousOne
    2
    position
    1
    two
    7
    one
    2
    next
    7
  6. Commit the best prefix before advancing to the next house.

    The two live registers now describe the previous and current prefix lengths relative to this range. The full table shown here is explanatory history; Java uses constant workspace.

    input
    [2,7,9,3,1]
    phase
    "commit"
    caseResults
    []
    start
    0
    end
    5
    caseLabel
    "Whole linear street"
    table
    [0,2,7,null,null,null]
    previousTwo
    2
    previousOne
    7
    position
    1
    two
    7
    one
    2
    next
    7
  7. Compare taking this house with skipping it.

    take uses the two-back prefix and this house; skip uses the one-back prefix. A prefix optimum need not include its last house. Both candidates use the old pair.

    input
    [2,7,9,3,1]
    phase
    "candidate"
    caseResults
    []
    start
    0
    end
    5
    caseLabel
    "Whole linear street"
    table
    [0,2,7,null,null,null]
    previousTwo
    2
    previousOne
    7
    position
    2
    two
    11
    one
    7
    next
    11
  8. Commit the best prefix before advancing to the next house.

    The two live registers now describe the previous and current prefix lengths relative to this range. The full table shown here is explanatory history; Java uses constant workspace.

    input
    [2,7,9,3,1]
    phase
    "commit"
    caseResults
    []
    start
    0
    end
    5
    caseLabel
    "Whole linear street"
    table
    [0,2,7,11,null,null]
    previousTwo
    7
    previousOne
    11
    position
    2
    two
    11
    one
    7
    next
    11
  9. Compare taking this house with skipping it.

    take uses the two-back prefix and this house; skip uses the one-back prefix. A prefix optimum need not include its last house. Both candidates use the old pair.

    input
    [2,7,9,3,1]
    phase
    "candidate"
    caseResults
    []
    start
    0
    end
    5
    caseLabel
    "Whole linear street"
    table
    [0,2,7,11,null,null]
    previousTwo
    7
    previousOne
    11
    position
    3
    two
    10
    one
    11
    next
    11
  10. Commit the best prefix before advancing to the next house.

    The two live registers now describe the previous and current prefix lengths relative to this range. The full table shown here is explanatory history; Java uses constant workspace.

    input
    [2,7,9,3,1]
    phase
    "commit"
    caseResults
    []
    start
    0
    end
    5
    caseLabel
    "Whole linear street"
    table
    [0,2,7,11,11,null]
    previousTwo
    11
    previousOne
    11
    position
    3
    two
    10
    one
    11
    next
    11
  11. Compare taking this house with skipping it.

    take uses the two-back prefix and this house; skip uses the one-back prefix. A prefix optimum need not include its last house. Both candidates use the old pair.

    input
    [2,7,9,3,1]
    phase
    "candidate"
    caseResults
    []
    start
    0
    end
    5
    caseLabel
    "Whole linear street"
    table
    [0,2,7,11,11,null]
    previousTwo
    11
    previousOne
    11
    position
    4
    two
    12
    one
    11
    next
    12
  12. Commit the best prefix before advancing to the next house.

    The two live registers now describe the previous and current prefix lengths relative to this range. The full table shown here is explanatory history; Java uses constant workspace.

    input
    [2,7,9,3,1]
    phase
    "commit"
    caseResults
    []
    start
    0
    end
    5
    caseLabel
    "Whole linear street"
    table
    [0,2,7,11,11,12]
    previousTwo
    11
    previousOne
    12
    position
    4
    two
    12
    one
    11
    next
    12
  13. Finish this complete path range.

    The pass has evaluated every house in its range. Its scalar optimum is feasible on that path; source indices and values remain unchanged.

    input
    [2,7,9,3,1]
    phase
    "range-complete"
    caseResults
    [{"caseLabel":"Whole linear street","start":0,"end":5,"value":12}]
    start
    0
    end
    5
    caseLabel
    "Whole linear street"
    table
    [0,2,7,11,11,12]
    previousTwo
    11
    previousOne
    12
    position
    4
    answer
    12
  14. Return the exact value required by the contract.

    Teaching tables and saved candidate values explain the dependency frontier; they are excluded from the Java reference’s constant auxiliary storage.

    result
    12

Empty street

Input: [] · Maximum linear nonadjacent total: 0

Step 1 of 4: Validate the complete input before any base-case result.

Bounds, null, and value rules belong to the API. These displayed fixtures satisfy the contract; no caller input is changed.

House Robber — compare take and skip prefixes

Phase: validated.

B(k+1) = max(B(k), B(max(0,k−1)) + nums[index])

The complete input satisfies the documented contract. The next step establishes base states before any transition.

Original house indices and money — index identity determines adjacency.

No entries.

Input entries stay unchanged. Candidate and commit steps separate reading the old frontier from updating it. Full state tables and the equivalent static walkthrough appear below.

State after this step
VariableValue
input[]
phase"validated"
caseResults[]
See the affected Java block
 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     private Solution() {}
 5     private static void validate(int[] nums) {
 6         Objects.requireNonNull(nums, "nums");
 7         if (nums.length > 100_000) throw new IllegalArgumentException("too many houses");
 8         for (int value : nums) if (value < 0) throw new IllegalArgumentException("negative money");
 9     }
10     public static long rob(int[] nums) {
11         validate(nums);
12         long previousTwo = 0, previousOne = 0;
13         for (int index = 0; index < nums.length; index++) {
14             long take = previousTwo + nums[index];
15             long skip = previousOne;
16             long next = Math.max(skip, take);
17             previousTwo = previousOne;
18             previousOne = next;
19         }
20         return previousOne;
21     }
22     // Baseline: include/exclude enumeration. Small inputs only.
23     public static long baseline(int[] nums) {
24         validate(nums);
25         return enumerate(nums, 0);
26     }
27     private static long enumerate(int[] nums, int index) {
28         if (index >= nums.length) return 0;
29         return Math.max(enumerate(nums, index + 1), (long) nums[index] + enumerate(nums, index + 2));
30     }
31 }
32

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace
  1. Validate the complete input before any base-case result.

    Bounds, null, and value rules belong to the API. These displayed fixtures satisfy the contract; no caller input is changed.

    input
    []
    phase
    "validated"
    caseResults
    []
  2. Reset an empty prefix for this half-open path range.

    Only original indices start..end−1 belong to this pass. Prefix length zero has optimum zero. Both registers reset independently of all earlier passes.

    input
    []
    phase
    "range-start"
    caseResults
    []
    start
    0
    end
    0
    caseLabel
    "Whole linear street"
    table
    [0]
    previousTwo
    0
    previousOne
    0
    position
    -1
  3. Finish this complete path range.

    The pass has evaluated every house in its range. Its scalar optimum is feasible on that path; source indices and values remain unchanged.

    input
    []
    phase
    "range-complete"
    caseResults
    [{"caseLabel":"Whole linear street","start":0,"end":0,"value":0}]
    start
    0
    end
    0
    caseLabel
    "Whole linear street"
    table
    [0]
    previousTwo
    0
    previousOne
    0
    position
    -1
    answer
    0
  4. Return the exact value required by the contract.

    Teaching tables and saved candidate values explain the dependency frontier; they are excluded from the Java reference’s constant auxiliary storage.

    result
    0

One house

Input: [7] · Maximum linear nonadjacent total: 7

Step 1 of 6: Validate the complete input before any base-case result.

Bounds, null, and value rules belong to the API. These displayed fixtures satisfy the contract; no caller input is changed.

House Robber — compare take and skip prefixes

Phase: validated.

B(k+1) = max(B(k), B(max(0,k−1)) + nums[index])

The complete input satisfies the documented contract. The next step establishes base states before any transition.

Original house indices and money — index identity determines adjacency.

  • 0: 7available in this pass

Input entries stay unchanged. Candidate and commit steps separate reading the old frontier from updating it. Full state tables and the equivalent static walkthrough appear below.

State after this step
VariableValue
input[7]
phase"validated"
caseResults[]
See the affected Java block
 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     private Solution() {}
 5     private static void validate(int[] nums) {
 6         Objects.requireNonNull(nums, "nums");
 7         if (nums.length > 100_000) throw new IllegalArgumentException("too many houses");
 8         for (int value : nums) if (value < 0) throw new IllegalArgumentException("negative money");
 9     }
10     public static long rob(int[] nums) {
11         validate(nums);
12         long previousTwo = 0, previousOne = 0;
13         for (int index = 0; index < nums.length; index++) {
14             long take = previousTwo + nums[index];
15             long skip = previousOne;
16             long next = Math.max(skip, take);
17             previousTwo = previousOne;
18             previousOne = next;
19         }
20         return previousOne;
21     }
22     // Baseline: include/exclude enumeration. Small inputs only.
23     public static long baseline(int[] nums) {
24         validate(nums);
25         return enumerate(nums, 0);
26     }
27     private static long enumerate(int[] nums, int index) {
28         if (index >= nums.length) return 0;
29         return Math.max(enumerate(nums, index + 1), (long) nums[index] + enumerate(nums, index + 2));
30     }
31 }
32

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace
  1. Validate the complete input before any base-case result.

    Bounds, null, and value rules belong to the API. These displayed fixtures satisfy the contract; no caller input is changed.

    input
    [7]
    phase
    "validated"
    caseResults
    []
  2. Reset an empty prefix for this half-open path range.

    Only original indices start..end−1 belong to this pass. Prefix length zero has optimum zero. Both registers reset independently of all earlier passes.

    input
    [7]
    phase
    "range-start"
    caseResults
    []
    start
    0
    end
    1
    caseLabel
    "Whole linear street"
    table
    [0,null]
    previousTwo
    0
    previousOne
    0
    position
    -1
  3. Compare taking this house with skipping it.

    take uses the two-back prefix and this house; skip uses the one-back prefix. A prefix optimum need not include its last house. Both candidates use the old pair.

    input
    [7]
    phase
    "candidate"
    caseResults
    []
    start
    0
    end
    1
    caseLabel
    "Whole linear street"
    table
    [0,null]
    previousTwo
    0
    previousOne
    0
    position
    0
    two
    7
    one
    0
    next
    7
  4. Commit the best prefix before advancing to the next house.

    The two live registers now describe the previous and current prefix lengths relative to this range. The full table shown here is explanatory history; Java uses constant workspace.

    input
    [7]
    phase
    "commit"
    caseResults
    []
    start
    0
    end
    1
    caseLabel
    "Whole linear street"
    table
    [0,7]
    previousTwo
    0
    previousOne
    7
    position
    0
    two
    7
    one
    0
    next
    7
  5. Finish this complete path range.

    The pass has evaluated every house in its range. Its scalar optimum is feasible on that path; source indices and values remain unchanged.

    input
    [7]
    phase
    "range-complete"
    caseResults
    [{"caseLabel":"Whole linear street","start":0,"end":1,"value":7}]
    start
    0
    end
    1
    caseLabel
    "Whole linear street"
    table
    [0,7]
    previousTwo
    0
    previousOne
    7
    position
    0
    answer
    7
  6. Return the exact value required by the contract.

    Teaching tables and saved candidate values explain the dependency frontier; they are excluded from the Java reference’s constant auxiliary storage.

    result
    7

Long total across a gap

Input: [2147483647,0,2147483647] · Maximum linear nonadjacent total: 4294967294

Step 1 of 10: Validate the complete input before any base-case result.

Bounds, null, and value rules belong to the API. These displayed fixtures satisfy the contract; no caller input is changed.

House Robber — compare take and skip prefixes

Phase: validated.

B(k+1) = max(B(k), B(max(0,k−1)) + nums[index])

The complete input satisfies the documented contract. The next step establishes base states before any transition.

Original house indices and money — index identity determines adjacency.

  • 0: 2147483647available in this pass
  • 1: 0available in this pass
  • 2: 2147483647available in this pass

Input entries stay unchanged. Candidate and commit steps separate reading the old frontier from updating it. Full state tables and the equivalent static walkthrough appear below.

State after this step
VariableValue
input[2147483647,0,2147483647]
phase"validated"
caseResults[]
See the affected Java block
 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     private Solution() {}
 5     private static void validate(int[] nums) {
 6         Objects.requireNonNull(nums, "nums");
 7         if (nums.length > 100_000) throw new IllegalArgumentException("too many houses");
 8         for (int value : nums) if (value < 0) throw new IllegalArgumentException("negative money");
 9     }
10     public static long rob(int[] nums) {
11         validate(nums);
12         long previousTwo = 0, previousOne = 0;
13         for (int index = 0; index < nums.length; index++) {
14             long take = previousTwo + nums[index];
15             long skip = previousOne;
16             long next = Math.max(skip, take);
17             previousTwo = previousOne;
18             previousOne = next;
19         }
20         return previousOne;
21     }
22     // Baseline: include/exclude enumeration. Small inputs only.
23     public static long baseline(int[] nums) {
24         validate(nums);
25         return enumerate(nums, 0);
26     }
27     private static long enumerate(int[] nums, int index) {
28         if (index >= nums.length) return 0;
29         return Math.max(enumerate(nums, index + 1), (long) nums[index] + enumerate(nums, index + 2));
30     }
31 }
32

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace
  1. Validate the complete input before any base-case result.

    Bounds, null, and value rules belong to the API. These displayed fixtures satisfy the contract; no caller input is changed.

    input
    [2147483647,0,2147483647]
    phase
    "validated"
    caseResults
    []
  2. Reset an empty prefix for this half-open path range.

    Only original indices start..end−1 belong to this pass. Prefix length zero has optimum zero. Both registers reset independently of all earlier passes.

    input
    [2147483647,0,2147483647]
    phase
    "range-start"
    caseResults
    []
    start
    0
    end
    3
    caseLabel
    "Whole linear street"
    table
    [0,null,null,null]
    previousTwo
    0
    previousOne
    0
    position
    -1
  3. Compare taking this house with skipping it.

    take uses the two-back prefix and this house; skip uses the one-back prefix. A prefix optimum need not include its last house. Both candidates use the old pair.

    input
    [2147483647,0,2147483647]
    phase
    "candidate"
    caseResults
    []
    start
    0
    end
    3
    caseLabel
    "Whole linear street"
    table
    [0,null,null,null]
    previousTwo
    0
    previousOne
    0
    position
    0
    two
    2147483647
    one
    0
    next
    2147483647
  4. Commit the best prefix before advancing to the next house.

    The two live registers now describe the previous and current prefix lengths relative to this range. The full table shown here is explanatory history; Java uses constant workspace.

    input
    [2147483647,0,2147483647]
    phase
    "commit"
    caseResults
    []
    start
    0
    end
    3
    caseLabel
    "Whole linear street"
    table
    [0,2147483647,null,null]
    previousTwo
    0
    previousOne
    2147483647
    position
    0
    two
    2147483647
    one
    0
    next
    2147483647
  5. Compare taking this house with skipping it.

    take uses the two-back prefix and this house; skip uses the one-back prefix. A prefix optimum need not include its last house. Both candidates use the old pair.

    input
    [2147483647,0,2147483647]
    phase
    "candidate"
    caseResults
    []
    start
    0
    end
    3
    caseLabel
    "Whole linear street"
    table
    [0,2147483647,null,null]
    previousTwo
    0
    previousOne
    2147483647
    position
    1
    two
    0
    one
    2147483647
    next
    2147483647
  6. Commit the best prefix before advancing to the next house.

    The two live registers now describe the previous and current prefix lengths relative to this range. The full table shown here is explanatory history; Java uses constant workspace.

    input
    [2147483647,0,2147483647]
    phase
    "commit"
    caseResults
    []
    start
    0
    end
    3
    caseLabel
    "Whole linear street"
    table
    [0,2147483647,2147483647,null]
    previousTwo
    2147483647
    previousOne
    2147483647
    position
    1
    two
    0
    one
    2147483647
    next
    2147483647
  7. Compare taking this house with skipping it.

    take uses the two-back prefix and this house; skip uses the one-back prefix. A prefix optimum need not include its last house. Both candidates use the old pair.

    input
    [2147483647,0,2147483647]
    phase
    "candidate"
    caseResults
    []
    start
    0
    end
    3
    caseLabel
    "Whole linear street"
    table
    [0,2147483647,2147483647,null]
    previousTwo
    2147483647
    previousOne
    2147483647
    position
    2
    two
    4294967294
    one
    2147483647
    next
    4294967294
  8. Commit the best prefix before advancing to the next house.

    The two live registers now describe the previous and current prefix lengths relative to this range. The full table shown here is explanatory history; Java uses constant workspace.

    input
    [2147483647,0,2147483647]
    phase
    "commit"
    caseResults
    []
    start
    0
    end
    3
    caseLabel
    "Whole linear street"
    table
    [0,2147483647,2147483647,4294967294]
    previousTwo
    2147483647
    previousOne
    4294967294
    position
    2
    two
    4294967294
    one
    2147483647
    next
    4294967294
  9. Finish this complete path range.

    The pass has evaluated every house in its range. Its scalar optimum is feasible on that path; source indices and values remain unchanged.

    input
    [2147483647,0,2147483647]
    phase
    "range-complete"
    caseResults
    [{"caseLabel":"Whole linear street","start":0,"end":3,"value":4294967294}]
    start
    0
    end
    3
    caseLabel
    "Whole linear street"
    table
    [0,2147483647,2147483647,4294967294]
    previousTwo
    2147483647
    previousOne
    4294967294
    position
    2
    answer
    4294967294
  10. Return the exact value required by the contract.

    Teaching tables and saved candidate values explain the dependency frontier; they are excluded from the Java reference’s constant auxiliary storage.

    result
    4294967294

Mixed parity optimum

Input: [10,1,1,10] · Maximum linear nonadjacent total: 20

Step 1 of 12: Validate the complete input before any base-case result.

Bounds, null, and value rules belong to the API. These displayed fixtures satisfy the contract; no caller input is changed.

House Robber — compare take and skip prefixes

Phase: validated.

B(k+1) = max(B(k), B(max(0,k−1)) + nums[index])

The complete input satisfies the documented contract. The next step establishes base states before any transition.

Original house indices and money — index identity determines adjacency.

  • 0: 10available in this pass
  • 1: 1available in this pass
  • 2: 1available in this pass
  • 3: 10available in this pass

Input entries stay unchanged. Candidate and commit steps separate reading the old frontier from updating it. Full state tables and the equivalent static walkthrough appear below.

State after this step
VariableValue
input[10,1,1,10]
phase"validated"
caseResults[]
See the affected Java block
 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     private Solution() {}
 5     private static void validate(int[] nums) {
 6         Objects.requireNonNull(nums, "nums");
 7         if (nums.length > 100_000) throw new IllegalArgumentException("too many houses");
 8         for (int value : nums) if (value < 0) throw new IllegalArgumentException("negative money");
 9     }
10     public static long rob(int[] nums) {
11         validate(nums);
12         long previousTwo = 0, previousOne = 0;
13         for (int index = 0; index < nums.length; index++) {
14             long take = previousTwo + nums[index];
15             long skip = previousOne;
16             long next = Math.max(skip, take);
17             previousTwo = previousOne;
18             previousOne = next;
19         }
20         return previousOne;
21     }
22     // Baseline: include/exclude enumeration. Small inputs only.
23     public static long baseline(int[] nums) {
24         validate(nums);
25         return enumerate(nums, 0);
26     }
27     private static long enumerate(int[] nums, int index) {
28         if (index >= nums.length) return 0;
29         return Math.max(enumerate(nums, index + 1), (long) nums[index] + enumerate(nums, index + 2));
30     }
31 }
32

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace
  1. Validate the complete input before any base-case result.

    Bounds, null, and value rules belong to the API. These displayed fixtures satisfy the contract; no caller input is changed.

    input
    [10,1,1,10]
    phase
    "validated"
    caseResults
    []
  2. Reset an empty prefix for this half-open path range.

    Only original indices start..end−1 belong to this pass. Prefix length zero has optimum zero. Both registers reset independently of all earlier passes.

    input
    [10,1,1,10]
    phase
    "range-start"
    caseResults
    []
    start
    0
    end
    4
    caseLabel
    "Whole linear street"
    table
    [0,null,null,null,null]
    previousTwo
    0
    previousOne
    0
    position
    -1
  3. Compare taking this house with skipping it.

    take uses the two-back prefix and this house; skip uses the one-back prefix. A prefix optimum need not include its last house. Both candidates use the old pair.

    input
    [10,1,1,10]
    phase
    "candidate"
    caseResults
    []
    start
    0
    end
    4
    caseLabel
    "Whole linear street"
    table
    [0,null,null,null,null]
    previousTwo
    0
    previousOne
    0
    position
    0
    two
    10
    one
    0
    next
    10
  4. Commit the best prefix before advancing to the next house.

    The two live registers now describe the previous and current prefix lengths relative to this range. The full table shown here is explanatory history; Java uses constant workspace.

    input
    [10,1,1,10]
    phase
    "commit"
    caseResults
    []
    start
    0
    end
    4
    caseLabel
    "Whole linear street"
    table
    [0,10,null,null,null]
    previousTwo
    0
    previousOne
    10
    position
    0
    two
    10
    one
    0
    next
    10
  5. Compare taking this house with skipping it.

    take uses the two-back prefix and this house; skip uses the one-back prefix. A prefix optimum need not include its last house. Both candidates use the old pair.

    input
    [10,1,1,10]
    phase
    "candidate"
    caseResults
    []
    start
    0
    end
    4
    caseLabel
    "Whole linear street"
    table
    [0,10,null,null,null]
    previousTwo
    0
    previousOne
    10
    position
    1
    two
    1
    one
    10
    next
    10
  6. Commit the best prefix before advancing to the next house.

    The two live registers now describe the previous and current prefix lengths relative to this range. The full table shown here is explanatory history; Java uses constant workspace.

    input
    [10,1,1,10]
    phase
    "commit"
    caseResults
    []
    start
    0
    end
    4
    caseLabel
    "Whole linear street"
    table
    [0,10,10,null,null]
    previousTwo
    10
    previousOne
    10
    position
    1
    two
    1
    one
    10
    next
    10
  7. Compare taking this house with skipping it.

    take uses the two-back prefix and this house; skip uses the one-back prefix. A prefix optimum need not include its last house. Both candidates use the old pair.

    input
    [10,1,1,10]
    phase
    "candidate"
    caseResults
    []
    start
    0
    end
    4
    caseLabel
    "Whole linear street"
    table
    [0,10,10,null,null]
    previousTwo
    10
    previousOne
    10
    position
    2
    two
    11
    one
    10
    next
    11
  8. Commit the best prefix before advancing to the next house.

    The two live registers now describe the previous and current prefix lengths relative to this range. The full table shown here is explanatory history; Java uses constant workspace.

    input
    [10,1,1,10]
    phase
    "commit"
    caseResults
    []
    start
    0
    end
    4
    caseLabel
    "Whole linear street"
    table
    [0,10,10,11,null]
    previousTwo
    10
    previousOne
    11
    position
    2
    two
    11
    one
    10
    next
    11
  9. Compare taking this house with skipping it.

    take uses the two-back prefix and this house; skip uses the one-back prefix. A prefix optimum need not include its last house. Both candidates use the old pair.

    input
    [10,1,1,10]
    phase
    "candidate"
    caseResults
    []
    start
    0
    end
    4
    caseLabel
    "Whole linear street"
    table
    [0,10,10,11,null]
    previousTwo
    10
    previousOne
    11
    position
    3
    two
    20
    one
    11
    next
    20
  10. Commit the best prefix before advancing to the next house.

    The two live registers now describe the previous and current prefix lengths relative to this range. The full table shown here is explanatory history; Java uses constant workspace.

    input
    [10,1,1,10]
    phase
    "commit"
    caseResults
    []
    start
    0
    end
    4
    caseLabel
    "Whole linear street"
    table
    [0,10,10,11,20]
    previousTwo
    11
    previousOne
    20
    position
    3
    two
    20
    one
    11
    next
    20
  11. Finish this complete path range.

    The pass has evaluated every house in its range. Its scalar optimum is feasible on that path; source indices and values remain unchanged.

    input
    [10,1,1,10]
    phase
    "range-complete"
    caseResults
    [{"caseLabel":"Whole linear street","start":0,"end":4,"value":20}]
    start
    0
    end
    4
    caseLabel
    "Whole linear street"
    table
    [0,10,10,11,20]
    previousTwo
    11
    previousOne
    20
    position
    3
    answer
    20
  12. Return the exact value required by the contract.

    Teaching tables and saved candidate values explain the dependency frontier; they are excluded from the Java reference’s constant auxiliary storage.

    result
    20

Test the contract

  1. Input: nums=[]
    Output: 0

    Empty selection.

  2. Input: nums=[7]
    Output: 7

    One available house.

  3. Input: nums=[2,3]
    Output: 3

    Adjacent houses cannot both contribute.

  4. Input: nums=[0,0,0]
    Output: 0

    Many subsets share the same numeric optimum.

  5. Input: nums=[10,1,1,10]
    Output: 20

    Mixed-parity endpoint optimum.

  6. Input: nums=[-1]
    Output: IllegalArgumentException

    The reference enforces its nonnegative contract.

Common mistakes and counterexamples

Take the larger house in each adjacent pair

Counterexample: [2,7,9,3,1] cannot be solved by independently selecting pair winners; pair boundaries can conflict.

Compare optimal compatible prefixes, rather than making independent local pair decisions.

Always choose all even or all odd positions

Counterexample: [10,1,1,10] has optimum 20 at indices 0 and 3, mixing parity.

The independent subset can switch parity after a sufficiently large gap.

Update previousTwo before calculating take

Counterexample: [2,3] could become 5 by combining the first optimum with its adjacent house.

Compute both candidates from the old frontier and then commit the pair.

Use a mandatory-current or int state

Counterexample: [2,1] has optimum 2 even though the last house is omitted; [MAX,0,MAX] exceeds int.

Define a prefix optimum allowing omission and calculate sums with long registers.

Follow-ups

Return selected house indices.

Keep an O(n) prefix table, backtrack from n, and choose skip or take according to the recurrence. Define a deterministic tie preference; choosing skip on equality gives one valid optimum but not necessarily the lexicographically smallest index vector. Reverse recovered indices and verify adjacency and sum.

Forbid selecting houses within distance d.

Taking index i reads the optimum prefix ending before i−d, while skipping reads the previous prefix. Clamp missing prefixes to zero. A full table costs O(n) space; a ring buffer of the required dependency distance can reduce live history. Specify whether d=0 allows all distinct houses.

Count the number of maximum-value subsets as well as their value.

Store an optimum and a count per prefix. If take and skip values differ, keep the winning count; on equality, add counts because inclusion and omission of i are disjoint. Zero-valued houses create real multiplicity. State a BigInteger or modular counting policy even if maximum sums still fit long.

Related foundations

Keep practicing

Return to the lesson

AceYourInterviews · 2026-10-17 · Original teaching content and implementations authored for AceYourInterviews. Familiar interview problem names describe standard algorithmic tasks; no company-frequency or platform-difficulty claims are made.