House Robber II (Circular Street)
Medium About 20 min Free, no account needed
The street is a circle now - the first and last houses are neighbors.
The brief
Same as House Robber, but the houses form a circle: the first and last houses are adjacent and cannot both be robbed.
The obvious approach branches rob-or-skip at every house, 2^n paths, and the hidden street has 200,000 houses, so it never finishes. The linear street had an O(n) answer; the question is what the wrap-around does to it. The visible tests include streets where the best linear plan robs both ends, which the circle forbids.
Starter code
using System;
public class Solution
{
// TODO: return the maximum loot on a circular street (first and last are adjacent).
public long RobCircle(int[] nums)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Dynamic programming
- Define subproblems and a recurrence, then reuse solved subproblems instead of recomputing them.
Do these first
Related katas
- Coin Change (Fewest Coins) Medium Free The fewest coins that make the amount, or -1.
- Coin Change II (Count the Ways) Medium Free How many coin combinations make the amount?
- Decode Ways Medium Free How many letter strings could this digit string encode?
- Longest Increasing Subsequence Medium Free Length of the longest strictly increasing subsequence - faster than the quadratic DP.