leetcode house robber incorrect output

Question

I was doing this leetcode question: https://leetcode.com/problems/house-robber/

The question is

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

With following example

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
             Total amount you can rob = 1 + 3 = 4.

I wrote the following code for this

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
  if (nums.length === 0) return 0
  let output = i = 0
  while (i < nums.length) {
    const currentHouse = nums[i]
    i = i + 2
    output += currentHouse
  }
  return output
};

console.log(rob([1, 2]));
console.log(rob([1, 2, 3, 1]));

but it fails for this particular

Input:
[1,2]

Output:
1
Expected:
2

I am not sure why the output should be 2 for the above test?

The output should be 2 because the robber can only rob one of the two houses in one night, so they should rob the house with the most money, and that is the house with 2, not the house with 1. — trincot
– trincot, Commented Oct 15, 2020 at 6:46
Since there are only 2 houses, you can only break into 1. The optimal house to break into this solution would be the second one, with 2 units of money, compared to the first house's 1. — OneStig
– OneStig, Commented Oct 15, 2020 at 6:47
Your function is just trying to avoid setting off the alarm, but it doesn't try to steal the most money it can. — Barmar
– Barmar, Commented Oct 15, 2020 at 6:52
As @Barmar says, it's not just about to avoid triggering the alarm, but also to steel the max amount of money. Further, you don't have to start with the first house. So the solution seems to start with the house with the most money, i.e to find the array index of the highest number and start from there... BUT consider rob( [1, 3, 3, 2]) = 5 or rob([1, 3, 5, 4, 1, 2]) = 9... — Kossi D. T. S.
– Kossi D. T. S., Commented Oct 15, 2020 at 7:18
You also don't have to do every other house. You can skip 2 houses if it will get you more money. This is a constraint optimization problem. — Barmar
– Barmar, Commented Oct 15, 2020 at 7:19

trincot · Accepted Answer · 2020-10-15 09:16:19Z

Your algorithm just takes the houses at even indexes without taking into account that you have different options.

For instance when there are 5 houses (numbered 0 to 4) you can consider the following alternatives:

rob house 0, 2 and 4
rob house 0 and 3
rob house 1 and 3
rob house 1 and 4

Each of these could be the optimal strategy for the robber... it all depends on the amounts of money in the houses. For instance:

When input is [1,1,1,1,1] then strategy 1 is optimal and your program produces the correct output (3)
When input is [2,1,1,3,1] then strategy 2 is optimal (5), while your program will output 4.
When input is [1,2,1,3,1] then strategy 3 is optimal (5), while your program will output 3.
When input is [1,3,1,1,2] then strategy 4 is optimal (5), while your program will output 4.

Once you realise you need to look at different patterns, you can see that sometimes you need skip a house even if it was not adjacent to a previously robbed house. It is also not guaranteed that robbing the first house is optimal. On the other hand, it is never optimal to skip 3 houses in row, as you then might as well rob the middle of those, as it is not adjacent to another robbed house.

You can have an algorithm that progressively adds a house to the problem, and keeps track what was the best for the two previous sub problems (so with 2 or 1 fewer houses).

We can then look at the situation where we rob the newly added house or not. If we rob it, we should add the money to the money we got from the problem with 2 fewer houses. If we don't rob it, we should just copy what we got from the problem with 1 fewer houses.

This is a so-called bottom up approach:

function rob(nums) {
    // Represent the optimal amount we get from a problem with fewer houses:
    let sumTwoHousesLess = 0;
    let sumOneHouseLess = 0;
    let sum = 0; // The amount for a problem without any houses.
    for (let money of nums) { // Add a house to the problem in each iteration
        // See what is best: rob this house or not:
        sum = Math.max(money + sumTwoHousesLess, sumOneHouseLess);
        // Shift the information we have, as we are about to go to the next house
        sumTwoHousesLess = sumOneHouseLess;
        sumOneHouseLess = sum;
    }
    return sum;
}

console.log(rob([1,2])); // 2
console.log(rob([1,1,1,1,1])); // 3
console.log(rob([2,1,1,3,1])); // 5
console.log(rob([1,2,1,3,1])); // 5
console.log(rob([1,3,1,1,2])); // 5

Could you give some feed-back? Did this answer your question?

Collectives™ on Stack Overflow

leetcode house robber incorrect output

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related