[FIXED] leetcode house robber getting different output on ide vs leetcode

Issue

The following code gives correct answer on my IDE but gives wrong answer in leetcode output.

def rob(nums, current=0, memo={}):
    if current >= len(nums):
        return 0
    if current in memo:
        sum1 = memo[current]
    else:
        sum1 = nums[current] + rob(nums, current + 2)
        memo[current] = sum1
    
    if current + 1 >= len(nums):
        return sum1
    if current + 1 in memo:
        sum2 = memo[current + 1]
    else:
        sum2 = nums[current + 1] + rob(nums, current + 3)
        memo[current + 1] = sum2
    return max(sum1, sum2)

input: [2,7,9,3,1]

IDE output: 12 (correct answer)

leetcode output: 4 (wrong answer)

Why this is happening?

Solution

The problem is with memo={}. When you just run one test, it will work locally (and also on LeetCode when you run it on one particular input), but when you would run multiple calls of the function with different nums inputs, you would get unexpected results too.

memo is only assigned {} once, and is never reset by it. This dictionary is only created once, and that dictionary will serve as default value in a next call. If the function mutates that dictionary, then the next call (without memo argument) will get that mutated dictionary as initialisation value. This is how default parameter values work in Python.

You can solve it like this:

def rob(nums, current=0, memo=None):
    if memo is None:
        memo = {}
    # Rest of your code, but PASS the memo argument!
    if current >= len(nums):
        return 0
    if current in memo:
        sum1 = memo[current]
    else:
        sum1 = nums[current] + rob(nums, current + 2, memo)
        memo[current] = sum1
    
    if current + 1 >= len(nums):
        return sum1
    if current + 1 in memo:
        sum2 = memo[current + 1]
    else:
        sum2 = nums[current + 1] + rob(nums, current + 3, memo)
        memo[current + 1] = sum2
    return max(sum1, sum2)

Answered By - trincot