Big O Gym › Problem

Big O Practice: House Robber

Time and space complexity practice in Python and JavaScript. Concept tested: rolling DP with O(1) state.

def rob(nums):
    prev = curr = 0
    for x in nums:
        prev, curr = curr, max(curr, prev + x)
    return curr

Variables

  • n - length of the houses array

Explanation

One linear pass with two rolling DP values - **O(n)** time, **O(1)** space. The full DP table form is also O(n) space, but the rolling variables collapse it.

More Big O practice problems · Today's daily problem