Sunday, June 23, 2024
HomeAlgorithmsHouse Robber Problem | Maximum Sum of non-adjacent elements

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

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

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

class Solution {
public int rob(int[] nums) {
int n = nums.length;
int[] dp = new int[n+1];
Arrays.fill(dp,-1);
return rec(n-1, nums, dp);
}
private int rec(int i, int[] nums, int[] dp) {
if(i == 0) return nums[i];
if(i<0) return 0;
if(dp[i] != -1) return dp[i];
int pick = nums[i] + rec(i-2, nums, dp);
int nonPick = rec(i-1, nums, dp);
return dp[i] = Math.max(pick,nonPick);
}
}

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.

class Solution {
public int rob(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
dp[0] = nums[0];
for(int i = 1; i< n;i++) {
int pick = nums[i];
if(i>1) pick += dp[i-2];
int nonPick = dp[i-1];
dp[i] = Math.max(pick, nonPick);
}
return dp[n-1];
}
}

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.

Vamsi Tallapudi
Vamsi Tallapudi
Architect Technology at Cognizant | Full Stack Engineer | Technical Blogger | AI Enthusiast

LEAVE A REPLY

Please enter your comment!
Please enter your name here

This site uses Akismet to reduce spam. Learn how your comment data is processed.

LATEST POSTS

Packages in Java

Hello World! Today's blog is about packages in java. Here, we will learn about what are packages and how we can use packages along with...
00:11:41

Check Array Formation Through Concatenation | Leetcode Problem 1640

In this video, we will explain Check Array Formation Through Concatenation, Leetcode's 1640th problem in 2 different approaches along with a coding solution. Problem statement You are given...

Binary Tree Traversals in Kotlin – PreOrder, InOrder and PostOrder Traversals

Binary Tree Traversals are most common Tree Problems in an Interview as well as Competitive Programming. They can be efficient while searching, inserting and deleting...

Next Greater node in a Linked List – Leetcode Problem #1019

In this article, we will discuss the solution for 1019th Problem from Leetcode - Next Greater Node In Linked List. Let us see the question in...

Follow us

1,358FansLike
10FollowersFollow
397SubscribersSubscribe

Most Popular