House Robber

Last Updated : 27 Jan, 2026

Given an array arr[] where each element shows the amount of money in a row of houses built in a line. A robber wants to steal money, but cannot rob two houses adjacent to each other because it will set off an alarm.
Find the maximum money the robber can steal without robbing two adjacent houses.

Examples:

Input: arr[] = [6, 7, 1, 3, 8, 2, 4]
Output: 19
Explanation: The thief will steal from house 1, 3, 5 and 7, total money = 6 + 1 + 8 + 4 = 19.

Input: arr[] = [5, 3, 4, 11, 2]
Output: 16
Explanation: Thief will steal from house 1 and 4, total money = 5 + 11 = 16.

Try it on GfG Practice

Table of Content

[Naive Approach] Using Recursion- O(2^n) Time and O(n) Space
[Better Approach] Using Memoization - O(n) Time and O(n) Space
[Expected Approach 1] Using Tabulation - O(n) Time and O(n) Space
[Expected Approach 2] Space-Optimized DP - O(n) Time and O(1) Space

[Naive Approach] Using Recursion- O(2^n) Time and O(n) Space

The idea is to explore all the possibilities for each house using Recursion. We can start from the last house and for each house, we have two choices:
Rob the current house and skip the house just before it.
Skip the current house and move to the next house.

Recursion-Tree-for-House-Robber

C++

//Driver Code Starts
#include <iostream>
#include <vector>
using namespace std;
//Driver Code Ends


// Calculate the maximum stolen value recursively
int findMaxSumRec(vector<int> &arr, int n) {
	
    // If no houses are left, return 0.
    if (n <= 0)  return 0;
  
  	// If only 1 house is left, rob it. 
    if (n == 1)  return arr[0];

    // Two Choices: Rob the nth house and do not rob the nth house 
    int pick = arr[n - 1] + findMaxSumRec(arr, n - 2);
    int notPick = findMaxSumRec(arr, n - 1);

    // Return the max of two choices
    return max(pick, notPick);
}

// Function to calculate the maximum stolen value
int findMaxSum(vector<int>&arr) {
    int n = arr.size();
    
    // Call the recursive function for n houses
  	return findMaxSumRec(arr, n);
}


//Driver Code Starts
int main() {
    vector<int> arr = {6, 7, 1, 3, 8, 2, 4};
    cout << findMaxSum(arr);
    return 0;
}

//Driver Code Ends

C

//Driver Code Starts
#include <stdio.h>
//Driver Code Ends


// Calculate the maximum stolen value recursively
int findMaxSumRec(int arr[], int n) {
	
    // If no houses are left, return 0.
    if (n <= 0)  return 0;
  
  	// If only 1 house is left, rob it. 
    if (n == 1)  return arr[0];

    // Two Choices: Rob the nth house and do not rob the nth house 
    int pick = arr[n - 1] + findMaxSumRec(arr, n - 2);
    int notPick = findMaxSumRec(arr, n - 1);

    // Return the max of two choices
    return (pick > notPick) ? pick : notPick;
}

// Function to calculate the maximum stolen value
int findMaxSum(int arr[], int n) {
    
    // Call the recursive function for n houses
  	return findMaxSumRec(arr, n);
}


//Driver Code Starts
int main() {
    int arr[] = {6, 7, 1, 3, 8, 2, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("%d", findMaxSum(arr, n));
    return 0;
}

//Driver Code Ends

Java

//Driver Code Starts

class GFG {
//Driver Code Ends


    // Calculate the maximum stolen value recursively
    static int findMaxSumRec(int[] arr, int n) {
        
        // If no houses are left, return 0.
        if (n <= 0)  return 0;
      
        // If only 1 house is left, rob it. 
        if (n == 1)  return arr[0];

        // Two Choices: Rob the nth house and do not rob the nth house 
        int pick = arr[n - 1] + findMaxSumRec(arr, n - 2);
        int notPick = findMaxSumRec(arr, n - 1);

        // Return the max of two choices
        return Math.max(pick, notPick);
    }

    // Function to calculate the maximum stolen value
    static int findMaxSum(int[] arr) {
        int n = arr.length;
        
        // Call the recursive function for n houses
        return findMaxSumRec(arr, n);
    }


//Driver Code Starts
    public static void main(String[] args) {
        int[] arr = {6, 7, 1, 3, 8, 2, 4};
        System.out.println(findMaxSum(arr));
    }
}

//Driver Code Ends

Python

# Calculate the maximum stolen value recursively
def findMaxSumRec(arr, n):
	
    # If no houses are left, return 0.
    if n <= 0:
        return 0
  
  	# If only 1 house is left, rob it. 
    if n == 1:
        return arr[0]

    # Two Choices: Rob the nth house and do not rob the nth house 
    pick = arr[n - 1] + findMaxSumRec(arr, n - 2)
    notPick = findMaxSumRec(arr, n - 1)

    # Return the max of two choices
    return max(pick, notPick)

# Function to calculate the maximum stolen value
def findMaxSum(arr):
    n = len(arr)
    
    # Call the recursive function for n houses
    return findMaxSumRec(arr, n)


if __name__ == "__main__":
#Driver Code Starts
    arr = [6, 7, 1, 3, 8, 2, 4]
    print(findMaxSum(arr))

#Driver Code Ends

C#

//Driver Code Starts
using System;

class GFG {
//Driver Code Ends


    // Calculate the maximum stolen value recursively
    static int findMaxSumRec(int[] arr, int n) {
	
        // If no houses are left, return 0.
        if (n <= 0)  return 0;
  
      	// If only 1 house is left, rob it. 
        if (n == 1)  return arr[0];

        // Two Choices: Rob the nth house and do not rob the nth house 
        int pick = arr[n - 1] + findMaxSumRec(arr, n - 2);
        int notPick = findMaxSumRec(arr, n - 1);

        // Return the max of two choices
        return Math.Max(pick, notPick);
    }

    // Function to calculate the maximum stolen value
    static int findMaxSum(int[] arr) {
        int n = arr.Length;
        
        // Call the recursive function for n houses
      	return findMaxSumRec(arr, n);
    }


//Driver Code Starts
    static void Main() {
        int[] arr = {6, 7, 1, 3, 8, 2, 4};
        Console.WriteLine(findMaxSum(arr));
    }
}

//Driver Code Ends

JavaScript

// Calculate the maximum stolen value recursively
function findMaxSumRec(arr, n) {
	
    // If no houses are left, return 0.
    if (n <= 0)  return 0;
  
  	// If only 1 house is left, rob it. 
    if (n === 1)  return arr[0];

    // Two Choices: Rob the nth house and do not rob the nth house 
    let pick = arr[n - 1] + findMaxSumRec(arr, n - 2);
    let notPick = findMaxSumRec(arr, n - 1);

    // Return the max of two choices
    return Math.max(pick, notPick);
}

// Function to calculate the maximum stolen value
function findMaxSum(arr) {
    let n = arr.length;
    
    // Call the recursive function for n houses
  	return findMaxSumRec(arr, n);
}


let arr = [6, 7, 1, 3, 8, 2, 4];
//Driver Code Starts
console.log(findMaxSum(arr));

//Driver Code Ends

Output

[Better Approach] Using Memoization - O(n) Time and O(n) Space

In the recursive approach, many subproblems are solved multiple times because the same states are revisited again and again - this leads to overlapping subproblems and increases the time complexity.
We can optimize the recursive solution by using a memoization array of size (n + 1). Here, memo[i] represents the maximum amount of money that can be stolen from the first i houses.

In the recursive approach, only one parameter - the number of houses changes during each recursive call. Since the range of this parameter is from 0 to n, we can store and reuse previously computed results for each state to avoid redundant calculations.

C++

//Driver Code Starts
#include <iostream>
#include <vector>
using namespace std;
//Driver Code Ends


int findMaxSumRec( vector<int>& arr, int n, vector<int>& memo) {
  
    if (n <= 0) return 0;
    if (n == 1) return arr[0];

    // Check if the result is already computed
    if (memo[n] != -1) return memo[n];

    int pick = arr[n - 1] + findMaxSumRec(arr, n - 2, memo);
    int notPick = findMaxSumRec(arr, n - 1, memo);

    // Store the max of two choices in the memo array and return it
    memo[n] = max(pick, notPick);
    return memo[n];
}

int findMaxSum(vector<int>& arr) {
    int n = arr.size();
  
    // Initialize memo array with -1
    vector<int> memo(n + 1, -1); 
    return findMaxSumRec(arr, n, memo);
}


//Driver Code Starts
int main() {
    vector<int>arr = {6, 7, 1, 3, 8, 2, 4};
    cout << findMaxSum(arr);
    return 0;
}

//Driver Code Ends

C

//Driver Code Starts
#include <stdio.h>
//Driver Code Ends


// Calculate the maximum stolen value recursively with memoization
int findMaxSumRec(int arr[], int n, int memo[]) {
  
    if (n <= 0) return 0;
    if (n == 1) return arr[0];

    // Check if the result is already computed
    if (memo[n] != -1) return memo[n];

    int pick = arr[n - 1] + findMaxSumRec(arr, n - 2, memo);
    int notPick = findMaxSumRec(arr, n - 1, memo);

    // Store the max of two choices in the memo array and return it
    memo[n] = (pick > notPick) ? pick : notPick;
    return memo[n];
}

int findMaxSum(int arr[], int n) {
  
    // Initialize memo array with -1
    int memo[n + 1];
    for (int i = 0; i <= n; i++) memo[i] = -1;

    return findMaxSumRec(arr, n, memo);
}


//Driver Code Starts
int main() {
    int arr[] = {6, 7, 1, 3, 8, 2, 4};
    int n = sizeof(arr)/sizeof(arr[0]);
    printf("%d", findMaxSum(arr, n));
    return 0;
}

//Driver Code Ends

Java

//Driver Code Starts
import java.util.Arrays;

class GFG {
//Driver Code Ends


    static int findMaxSumRec(int[] arr, int n, int[] memo) {
  
        if (n <= 0) return 0;
        if (n == 1) return arr[0];

        // Check if the result is already computed
        if (memo[n] != -1) return memo[n];

        int pick = arr[n - 1] + findMaxSumRec(arr, n - 2, memo);
        int notPick = findMaxSumRec(arr, n - 1, memo);

        // Store the max of two choices in the memo array and return it
        memo[n] = Math.max(pick, notPick);
        return memo[n];
    }

    static int findMaxSum(int[] arr) {
        int n = arr.length;
  
        // Initialize memo array with -1
        int[] memo = new int[n + 1];
        Arrays.fill(memo, -1);
        return findMaxSumRec(arr, n, memo);
    }


//Driver Code Starts
    public static void main(String[] args) {
        int[] arr = {6, 7, 1, 3, 8, 2, 4};
        System.out.println(findMaxSum(arr));
    }
}

//Driver Code Ends

Python

# Calculate the maximum stolen value recursively with memoization
def findMaxSumRec(arr, n, memo):
  
    if n <= 0:
        return 0
    if n == 1:
        return arr[0]

    # Check if the result is already computed
    if memo[n] != -1:
        return memo[n]

    pick = arr[n - 1] + findMaxSumRec(arr, n - 2, memo)
    notPick = findMaxSumRec(arr, n - 1, memo)

    # Store the max of two choices in the memo array and return it
    memo[n] = max(pick, notPick)
    return memo[n]


# Function to calculate the maximum stolen value
def findMaxSum(arr):
    n = len(arr)
  
    # Initialize memo array with -1
    memo = [-1] * (n + 1)
    return findMaxSumRec(arr, n, memo)



#Driver Code Starts
if __name__ == "__main__":
    arr = [6, 7, 1, 3, 8, 2, 4]
    print(findMaxSum(arr))

#Driver Code Ends

C#

//Driver Code Starts
using System;

class GFG {
//Driver Code Ends


    static int findMaxSumRec(int[] arr, int n, int[] memo) {
  
        if (n <= 0) return 0;
        if (n == 1) return arr[0];

        // Check if the result is already computed
        if (memo[n] != -1) return memo[n];

        int pick = arr[n - 1] + findMaxSumRec(arr, n - 2, memo);
        int notPick = findMaxSumRec(arr, n - 1, memo);

        // Store the max of two choices in the memo array and return it
        memo[n] = Math.Max(pick, notPick);
        return memo[n];
    }

    static int findMaxSum(int[] arr) {
        int n = arr.Length;
  
        // Initialize memo array with -1
        int[] memo = new int[n + 1];
        for (int i = 0; i <= n; i++) memo[i] = -1;
        return findMaxSumRec(arr, n, memo);
    }


//Driver Code Starts
    static void Main() {
        int[] arr = {6, 7, 1, 3, 8, 2, 4};
        Console.WriteLine(findMaxSum(arr));
    }
}

//Driver Code Ends

JavaScript

function findMaxSumRec(arr, n, memo) {
  
    if (n <= 0) return 0;
    if (n === 1) return arr[0];

    // Check if the result is already computed
    if (memo[n] !== -1) return memo[n];

    let pick = arr[n - 1] + findMaxSumRec(arr, n - 2, memo);
    let notPick = findMaxSumRec(arr, n - 1, memo);

    // Store the max of two choices in the memo array and return it
    memo[n] = Math.max(pick, notPick);
    return memo[n];
}

function findMaxSum(arr) {
    let n = arr.length;
  
    // Initialize memo array with -1
    let memo = new Array(n + 1).fill(-1);
    return findMaxSumRec(arr, n, memo);
}

//Driver Code
//Driver Code Starts
let arr = [6, 7, 1, 3, 8, 2, 4];
console.log(findMaxSum(arr));

//Driver Code Ends

Output

[Expected Approach 1] Using Tabulation - O(n) Time and O(n) Space

In this approach, we build the solution iteratively from the ground up, starting with the smallest subproblems. We first define the base cases, and then gradually compute the answers for larger problems using the results of previously solved smaller ones.
Here, we create a dp[] array where dp[i] represents the maximum amount of money that can be stolen from the first i houses.

Initially,

we set dp[0] = 0 because if there are no houses, no money can be stolen.
we set dp[1] = arr[0] because if there is only one house, the thief will steal from that house.

Then, we iterate through the remaining houses and fill the dp[] array using this formula:

if the thief decides to rob the current house (i), then they must skip the previous house (i−1) in that case- arr[i] + dp[i−2].
If the thief skips the current house, then the total will simply be the maximum money till the previous house → dp[i−1].
so the answer will be the maximum of both dp[i]=max(arr[i]+dp[i−2], dp[i−1])

C++

//Driver Code Starts
#include <iostream>
#include <vector>
using namespace std;
//Driver Code Ends


int findMaxSum(vector<int>& arr) {
    int n = arr.size();
  
    // Create a dp array to store the maximum loot at each house
    vector<int> dp(n+1, 0);

    // Base cases
    dp[0] = 0;
    dp[1] = arr[0];

    // Fill the dp array using the bottom-up approach
    for (int i = 2; i <= n; i++) 
        dp[i] = max(arr[i - 1] + dp[i - 2], dp[i - 1]);

    return dp[n];
}


//Driver Code Starts
int main() {
    vector<int>arr = {6, 7, 1, 3, 8, 2, 4};
    cout << findMaxSum(arr) << endl;
    return 0;
}
//Driver Code Ends

C

//Driver Code Starts
#include <stdio.h>
//Driver Code Ends


// Function to calculate the maximum stolen value
int findMaxSum(int arr[], int n) {
  
    // Create a dp array to store the maximum loot at each house
    int dp[n + 1];

    // Base cases
    dp[0] = 0;
    dp[1] = arr[0];

    // Fill the dp array using the bottom-up approach
    for (int i = 2; i <= n; i++) 
        dp[i] = (arr[i - 1] + dp[i - 2] > dp[i - 1]) ? 
                 (arr[i - 1] + dp[i - 2]) : dp[i - 1];

    return dp[n];
}


//Driver Code Starts
int main() {
    int arr[] = {6, 7, 1, 3, 8, 2, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("%d
", findMaxSum(arr, n));
    return 0;
}

//Driver Code Ends

Java

//Driver Code Starts

class GFG {
//Driver Code Ends


    static int findMaxSum(int[] arr) {
        int n = arr.length;
  
        // Create a dp array to store the maximum loot at each house
        int[] dp = new int[n + 1];

        // Base cases
        dp[0] = 0;
        dp[1] = arr[0];

        // Fill the dp array using the bottom-up approach
        for (int i = 2; i <= n; i++)
            dp[i] = Math.max(arr[i - 1] + dp[i - 2], dp[i - 1]);

        return dp[n];
    }


//Driver Code Starts
    public static void main(String[] args) {
        int[] arr = {6, 7, 1, 3, 8, 2, 4};
        System.out.println(findMaxSum(arr));
    }
}

//Driver Code Ends

Python

def findMaxSum(arr):
    n = len(arr)
  
    # Create a dp array to store the maximum loot at each house
    dp = [0] * (n + 1)

    # Base cases
    dp[0] = 0
    dp[1] = arr[0]

    # Fill the dp array using the bottom-up approach
    for i in range(2, n + 1):
        dp[i] = max(arr[i - 1] + dp[i - 2], dp[i - 1])

    return dp[n]


if __name__ == "__main__":
#Driver Code Starts
    arr = [6, 7, 1, 3, 8, 2, 4]
    print(findMaxSum(arr))

#Driver Code Ends

C#

//Driver Code Starts
using System;
//Driver Code Ends


class GFG {

    static int findMaxSum(int[] arr) {
        int n = arr.Length;
  
        // Create a dp array to store the maximum loot at each house
        int[] dp = new int[n + 1];

        // Base cases
        dp[0] = 0;
        dp[1] = arr[0];

        // Fill the dp array using the bottom-up approach
        for (int i = 2; i <= n; i++)
            dp[i] = Math.Max(arr[i - 1] + dp[i - 2], dp[i - 1]);

        return dp[n];
    }


//Driver Code Starts
    static void Main() {
        int[] arr = {6, 7, 1, 3, 8, 2, 4};
        Console.WriteLine(findMaxSum(arr));
    }
}

//Driver Code Ends

JavaScript

function findMaxSum(arr) {
    let n = arr.length;
  
    // Create a dp array to store the maximum loot at each house
    let dp = new Array(n + 1).fill(0);

    // Base cases
    dp[0] = 0;
    dp[1] = arr[0];

    // Fill the dp array using the bottom-up approach
    for (let i = 2; i <= n; i++) 
        dp[i] = Math.max(arr[i - 1] + dp[i - 2], dp[i - 1]);

    return dp[n];
}

//Driver Code
//Driver Code Starts
let arr = [6, 7, 1, 3, 8, 2, 4];
console.log(findMaxSum(arr));

//Driver Code Ends

Output

[Expected Approach 2] Space-Optimized DP - O(n) Time and O(1) Space

On observing the dp[] array in the previous approach, it can be seen that the answer at the current index depends only on the last two values. In other words, dp[i] depends only on dp[i - 1] and dp[i - 2]. So, instead of storing the result in an array, we can simply use two variables to store the last and second last result.

C++

//Driver Code Starts
#include <iostream>
#include <vector>
using namespace std;
//Driver Code Ends


int findMaxSum(vector<int> &arr) {
    int n = arr.size();

    if (n == 0)
        return 0;
    if (n == 1)
        return arr[0];

    // Set previous 2 values
    int secondLast = 0, last = arr[0];

    // Compute current value using previous two values
    // The final current value would be our result
    int res;
    for (int i = 1; i < n; i++) {
        res = max(arr[i] + secondLast, last);
        secondLast = last;
        last = res;
    }
    return res;
}


//Driver Code Starts
int main() {
    vector<int> arr = {6, 7, 1, 3, 8, 2, 4};
    cout << findMaxSum(arr) << endl;
    return 0;
}
//Driver Code Ends

C

//Driver Code Starts
#include <stdio.h>
//Driver Code Ends


int findMaxSum(int arr[], int n) {

    if (n == 0)
        return 0;
    if (n == 1)
        return arr[0];

    // Set previous 2 values
    int secondLast = 0, last = arr[0];

    // Compute current value using previous two values
    // The final current value would be our result
    int res;
    for (int i = 1; i < n; i++) {
        res = (arr[i] + secondLast > last) ? (arr[i] + secondLast) : last;
        secondLast = last;
        last = res;
    }
    return res;
}


//Driver Code Starts
int main() {
    int arr[] = {6, 7, 1, 3, 8, 2, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("%d
", findMaxSum(arr, n));
    return 0;
}

//Driver Code Ends

Java

//Driver Code Starts
class GFG {
//Driver Code Ends


    static int findMaxSum(int[] arr) {
        int n = arr.length;

        if (n == 0)
            return 0;
        if (n == 1)
            return arr[0];

        // Set previous 2 values
        int secondLast = 0, last = arr[0];

        // Compute current value using previous two values
        // The final current value would be our result
        int res = 0;
        for (int i = 1; i < n; i++) {
            res = Math.max(arr[i] + secondLast, last);
            secondLast = last;
            last = res;
        }
        return res;
    }


//Driver Code Starts
    public static void main(String[] args) {
        int[] arr = {6, 7, 1, 3, 8, 2, 4};
        System.out.println(findMaxSum(arr));
    }
}

//Driver Code Ends

Python

def findMaxSum(arr):
    n = len(arr)

    if n == 0:
        return 0
    if n == 1:
        return arr[0]

    # Set previous 2 values
    secondLast, last = 0, arr[0]

    # Compute current value using previous two values
    # The final current value would be our result
    for i in range(1, n):
        res = max(arr[i] + secondLast, last)
        secondLast = last
        last = res
    return res


if __name__ == "__main__":
#Driver Code Starts
    arr = [6, 7, 1, 3, 8, 2, 4]
    print(findMaxSum(arr))

#Driver Code Ends

C#

//Driver Code Starts
using System;

class GFG {
//Driver Code Ends


    static int findMaxSum(int[] arr) {
        int n = arr.Length;

        if (n == 0)
            return 0;
        if (n == 1)
            return arr[0];

        // Set previous 2 values
        int secondLast = 0, last = arr[0];

        // Compute current value using previous two values
        // The final current value would be our result
        int res = 0;
        for (int i = 1; i < n; i++) {
            res = Math.Max(arr[i] + secondLast, last);
            secondLast = last;
            last = res;
        }
        return res;
    }


//Driver Code Starts
    static void Main() {
        int[] arr = {6, 7, 1, 3, 8, 2, 4};
        Console.WriteLine(findMaxSum(arr));
    }
}

//Driver Code Ends

JavaScript

function findMaxSum(arr) {
    let n = arr.length;

    if (n === 0)
        return 0;
    if (n === 1)
        return arr[0];

    // Set previous 2 values
    let secondLast = 0, last = arr[0];

    // Compute current value using previous two values
    // The final current value would be our result
    let res;
    for (let i = 1; i < n; i++) {
        res = Math.max(arr[i] + secondLast, last);
        secondLast = last;
        last = res;
    }
    return res;
}

//Driver Code
//Driver Code Starts
let arr = [6, 7, 1, 3, 8, 2, 4];
console.log(findMaxSum(arr));

//Driver Code Ends

Output

Comment

Article Tags:

Dynamic Programming

Explore

DSA Fundamentals

Data Structures

Algorithms

Advanced

Interview Preparation

Practice Problem