House Robber Problem | Maximum Sum of non-adjacent elements

In this blog post, we will discuss about how to find maximum sum of Non-Adjacent elements. Since House Robber Problem is a typical DP Problem asked by many product companies like Google, Facebook, Apple etc, let us discuss the problem and implement an acceptable solution for the same.

Prerequisites

• Basic knowledge on Subsequences.
• Recursion

House Robber Problem Statement

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.

Example 1:

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.

Example 2:

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

Constraints:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 400

Related Articles

• Binary Tree Traversals in Kotlin – PreOrder, InOrder and PostOrder Traversals
• Using Static Factory Methods – Learning Effective Java Item 1

Solution for House Robber Problem

Let us understand how we can get to a solution. The only way to think of how to find the maximum sum of non-adjacent elements is to get all the sums of possible subsequences with given constraint (non-adjacent).

If we think of how to get all the subsequences, we get the idea that we need to use Recursion.

Printing Subsequences

Basically we print subsequences by using Pick / Non-Pick strategy.

Recursion with Memoization Solution to solve House Robber Problem

Space and Time Complexities

Time Complexity: O(N) as we are using Memoization and storing all the overlapping values in an array. If we encounter the same value, instead of calculating, we’ll be fetching from this array.

Space Complexity: O(N) + O(N) -> Stack Space + Array Space

Tabulation Solution

Tabulation approach is basically Bottom-Up approach. We will go from 0th index to (n-1)th index.

Time and Space complexities

Time Complexity: O(N) for iterating through for loop

Space Complexity: O(N) for Array Space. Here we eliminated stack space in Tabulation approach.

Explaining these above two solutions works in most of the interviews. All the best for your next interview and subscribe us for more such amazing articles.