225. House Robber II

Why this mechanism works

A legal circular selection cannot contain both endpoints. Therefore it belongs to at least one of two linear cases: exclude the last house, or exclude the first. Solve each range using the previous kata's take/skip recurrence and choose the larger result. A singleton needs special handling because both ranges would otherwise be empty.

State and boundaries

linear(left,right) returns the optimum for the half-open noncircular range. The two calls cover all legal circular selections.

Protocol

1. Handle zero and one house.
2. Solve [0,n-1) with rolling take/skip state.
3. Solve [1,n) the same way.
4. Return the larger result.

Visualization

[2,3,2] around a circle
exclude last -> [2,3] best 3
exclude first -> [3,2] best 3
choosing both 2s is forbidden

Python implementation

def rob_circle(nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    def linear(left, right):
        previous = current = 0
        for i in range(left, right):
            previous, current = current, max(current, previous + nums[i])
        return current
    return max(linear(0, len(nums) - 1), linear(1, len(nums)))

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 rob_circle: if not nums:
nums=[2, 3, 2]

L7 linear: previous = current = 0
left=0; right=2; previous=0; current=0; nums=[2, 3, 2]

L8 linear: for i in range(left, right):
left=0; right=2; previous=0; current=0; nums=[2, 3, 2]; i=0

L9 linear: previous, current = current, max(current, previous + nums[i])
left=0; right=2; previous=0; current=2; nums=[2, 3, 2]; i=0

L8 linear: for i in range(left, right):
left=0; right=2; previous=0; current=2; nums=[2, 3, 2]; i=1

L9 linear: previous, current = current, max(current, previous + nums[i])
left=0; right=2; previous=2; current=3; nums=[2, 3, 2]; i=1

L7 linear: previous = current = 0
left=1; right=3; previous=0; current=0; nums=[2, 3, 2]

L8 linear: for i in range(left, right):
left=1; right=3; previous=0; current=0; nums=[2, 3, 2]; i=1

L9 linear: previous, current = current, max(current, previous + nums[i])
left=1; right=3; previous=0; current=3; nums=[2, 3, 2]; i=1

L8 linear: for i in range(left, right):
left=1; right=3; previous=0; current=3; nums=[2, 3, 2]; i=2

L9 linear: previous, current = current, max(current, previous + nums[i])
left=1; right=3; previous=3; current=3; nums=[2, 3, 2]; i=2

L2 rob_circle: if not nums:
nums=[1, 2, 3, 1]

L7 linear: previous = current = 0
left=0; right=3; previous=0; current=0; nums=[1, 2, 3, 1]

L8 linear: for i in range(left, right):
left=0; right=3; previous=0; current=0; nums=[1, 2, 3, 1]; i=0

L9 linear: previous, current = current, max(current, previous + nums[i])
left=0; right=3; previous=0; current=1; nums=[1, 2, 3, 1]; i=0

L8 linear: for i in range(left, right):
left=0; right=3; previous=0; current=1; nums=[1, 2, 3, 1]; i=1

L9 linear: previous, current = current, max(current, previous + nums[i])
left=0; right=3; previous=1; current=2; nums=[1, 2, 3, 1]; i=1

L8 linear: for i in range(left, right):
left=0; right=3; previous=1; current=2; nums=[1, 2, 3, 1]; i=2

L9 linear: previous, current = current, max(current, previous + nums[i])
left=0; right=3; previous=2; current=4; nums=[1, 2, 3, 1]; i=2

... 3 intermediate state changes omitted ...

L8 linear: for i in range(left, right):
left=1; right=4; previous=0; current=2; nums=[1, 2, 3, 1]; i=2

L9 linear: previous, current = current, max(current, previous + nums[i])
left=1; right=4; previous=2; current=3; nums=[1, 2, 3, 1]; i=2

L8 linear: for i in range(left, right):
left=1; right=4; previous=2; current=3; nums=[1, 2, 3, 1]; i=3

L9 linear: previous, current = current, max(current, previous + nums[i])
left=1; right=4; previous=3; current=3; nums=[1, 2, 3, 1]; i=3

Why the solution is correct

Every circular solution excludes at least one endpoint and is therefore legal in one of the two ranges. Conversely, every nonadjacent selection inside either range is legal on the circle because the excluded endpoint breaks the wraparound conflict. Taking the larger linear optimum is thus exact.

Time and space

O(n) time over two scans and O(1) auxiliary state; index ranges avoid allocating slices.

Common mistakes

Running the linear algorithm once can select both endpoints. Treating a singleton as two mutually adjacent distinct houses wrongly removes its value.

Reasoning card

Transfer exercise

Return a selected index set from the winning linear case, translating its indices back to the original circle.