Home » Interview coding problems/challenges

# House Robber

In this article, we are going to see **how to solve the house robber problem which is a famous dynamic problem to start with**? This has been also featured in Amazon interview rounds.

Submitted by Radib Kar, on January 28, 2019

**Problem statement:**

A professional robber is planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping him 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 he can rob tonight **without alerting the police**.

**Solution**

**Example**

Input: [1,2,3,1] Output: 4 Explanation: Option 1: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount he can rob = 1 + 3 = 4. Option 2: Rob house 2 (money = 2) and then rob house 4 (money = 1). Total amount he can rob = 2 + 1 = 3 So, option 1 maximizes the money stolen.

**Algorithm:**

The problem can be cut down to sub-problem of finding whether to rob from i^{th} house or not.

Let f(i)=amount of money stolen after robbing house i

Now, in case of taking decision whether to rob from **i ^{th}** house or not, it completely depends on where the money maximizes. Since, adjacent houses are connected, the robber can't rob two adjacent house. Either he can rob from

**(i-1)**house or he can rob from

^{th}**i**house after robbing from

^{th}**(i-2)**house. To maximize the money simply find which results in maximum amount. In terms of recursive relation we can write,

^{th}f(i)=maximum(f(i-2)+money of ith house,f(i-1))

This recursive relation ultimately yields to the maximum amount that can be robbed.

We can form our DP matrix and convert the recursive relation in memorization.

**Pre-requisite:**

A 1D array where mone stashed in houses are stored. Let the array to be **money**

**Steps:**

1. Bases case: IF (n==0) Return 0; IF (n==1) Return money[0]; 2. Initialize DP matrix int house[n]; // DP matrix //initialize all elements with their respective money for(int i=0;i<n;i++) house[i]=money[i]; 3. IF there is only one house, then simply rob the money. house[0]=money[0]; 4. IF there is two house rob from the house having maximum amount house[1]=(money[0]>money[1])?money[0]:money[1]; 5. Formulate the recursive function: for(int i=2;i<n;i++){ //for more houses house[i]=max(house[i]+house[i-2],house[i-1]); } //house[i-2]= f(i-2) // as updated by DP matrix // house[i-2]= f(i-2) // as updated by DP matrix // house[i]( on R.H.S) = money of ith house // as not still updated by DP matrix // house[i] (on L.H.S) = f(i) // as it's going to be updated by DP matrix 6. Return house[n-1]

**Example with explanation:**

Let's solve an example using the algorithm: No of houses: 6 Money stashed at houses: 4, 2, 2, 10, 4, 2 Initially DP matrix 4 (0th) | 2 (1st) | 2(2nd) | 10 (3rd) | 4 (4th) | 2 (5th) After step -3 & step - 4: 4 (0th) | 4 (1st) | 2(2nd) | 10 (3rd) | 4 (4th) | 2(5th) At step-5: House index starts from 0Iteration 0:house[2]=max(house[2]+house[0],house[1]); house[2]=6 // house[2]+house[0]=6 &house[1]=4 that means rob at house 0 & then at house 2 4 (0th) | 4 (1st) | 6(2nd) | 10 (3rd) | 4 (4th) | 2 (5th)Iteration 1:house[3]=max(house[3]+house[1],house[2]); house[3]=14 // house[3]+house[1]=14&house[2]=6 that means rob at house 1 & then at house 3 (decision changed) 4 (0th) | 4 (1st) | 6(2nd) | 14 (3rd) | 4 (4th) | 2 (5th)Iteration 2:house[4]=max(house[4]+house[2],house[3]); house[4]=14 // house[4]+house[2]=10&house[3]=14 that means rob at house 1& then at house 3 (no change in last decision) 4 (0th) | 4 (1st) | 6(2nd) | 14 (3rd) | 10 (4th) | 2 (5th)Iteration 3:house[5]=max(house[5]+house[3],house[4]); house[5]=16 // house[5]+house[3]=16&house[4]=10 that means rob at house 1 & then at house 3 & then at house 5(final) 4 (0th) | 4 (1st) | 6(2nd) | 14 (3rd) | 10 (4th) | 16 (5th)

That gives the maximum amount that can be robbed without breaking the security.

**C++ Implementation:**

#include <bits/stdc++.h> using namespace std; int max(int x,int y) {return (x>y)? x:y;} int rob(vector<int>& money) { int n=money.size(); //base cases if(n==0) return 0; if(n==1) return money[0]; int house[n]; //initialize DP matrix for(int i=0;i<n;i++) house[i]=money[i]; house[0]=money[0]; house[1]=(money[0]>money[1])?money[0]:money[1]; //Evaluate the recursive formula for(int i=2;i<n;i++){ house[i]=max(house[i]+house[i-2],house[i-1]); } //return max amount can be robbed return house[n-1]; } int main(){ int n,m; cout<<"enter no of houses\n"; cin>>n; vector<int> money; cout<<"enter respective money's of houses\n"; for(int i=0;i<n;i++){ cin>>m; money.push_back(m); } cout<<"maximum amount that can be robbed: "<<rob(money)<<endl; return 0; }

**Output**

First run: enter no of houses 4 enter respective money's of houses 1 2 3 1 maximum amount that can be robbed: 4 Second run: enter no of houses 6 enter respective money's of houses 4 2 2 10 4 2 maximum amount that can be robbed: 16

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.