Solving House Robber problem on LeetCode (step-by-step approach)

During the Covid 19 pandemic in 2021, I had a look back at everything I’ve learned last 6 years of coding. And guest, I realized the world runs so fast and I need to do something to get me next level of a Software Engineer.

I started with new ideas, and new technologies to develop a side project but I always feel that something is lacking in my knowledge. Then, I decided to start the learning process again as a fresh Software Engineer. During the process, I will update some of my interest tasks or problems. Hope you enjoy my articles.

The problem is on Leetcode: https://leetcode.com/problems/house-robber/

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 systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

After reading the problem, the first idea in my brain is USE BRUTE FORCE NOW!!!! but it burn my computer, so I decided to find something easier, faster, and more familiar.

Read the problem again, I found the number of gold is always greater than Zero ( > 0). From this info, if I increase the number of houses on the street I will get more gold.

→ This gets me to think about the pattern of max gold I can rob.

To find the pattern of rob, I run some manual input.

Declare: array (size = n) is the number of gold in every house on street (base index 0)
* Start at the house index 0 -> the maximum gold I can rob is array[0] -> asign this to max[0]
* Run to house index 1 -> the maximum gold can rob is max[1] = max(array[0], array[1])
* Run to house index 2 -> max[2] = max(array[0], array[1], array[2], array[0] + array[2])

This is the point. How to simplify the max[2]? What is the pattern of max[2]?

Consider these 2 ideas:

* max[1] = max(array[0], array[1])
* array[0] + array[2] >= array[2] // (number of gold is > 0)
// --> max[2] = max(max[1], array[0] + array[2])
// --> max[2] = max(max[1], max[0] + array[2])

Retested with index = 3, 4, 5 … And bingo! I found the pattern of rob.

max[n] = max(max[n-2] + array[n], max[n-1])

After finding the pattern of rob, I try to implement it with Kotlin.

The linear approach is easy to implement as the code below.

fun linearRob(array: IntArray):Int{
    val intArray = IntArray(array.size) {
        -1
    }
    var max = 0
    for(i in array.indices) {
        val current = array[i]
        val last1 = if(i > 0) intArray[i-1] else 0
        val last2 = if(i > 1) intArray[i-2] else 0
        val curMax = max(last2 + current, last1)
        intArray[i] = curMax
        if (curMax > max){
            max = curMax
        }
    }
    return max
}

The code works well and I have no problem with it. But I think it can be easier to read and understand. So I rewrite it with a recursive approach.

// dp approach
fun dpRob(array: IntArray, tracker: MutableMap<Int, Int>, at: Int):Int {
    if(at < 0) return 0
    if(!tracker.containsKey(at)) {
        val back1 = dpRob(array, tracker, at - 1)
        val back2 = dpRob(array, tracker, at - 2)
        val value = max(back2 + array[at], back1)
        tracker[at] = value
    }
    return tracker.getOrDefault(at, 0)
}

What I’ve learned from this problem?

1. Always think & solve the problem before writing any lines of code. Try more examples to get insight from them.
2. The brute force approach is not really a bad idea. If it’s the only idea in your head, just do it. We can optimize it later. An idea is better than no idea. The good idea comes later.
3. The first article on Medium is hard, I hope you guys enjoy it and feel free to drop a comment or clap.

Happy coding!