Data Structure & Algorithms
  • 🖌️Unlocking the Power of Algorithms with C#
  • Data Structure
    • Data Structure
    • Big O
    • Array
    • Linked Lists
    • Stacks
    • Queues
    • Hash Tables
    • Trees
    • Graphs
    • Heap Sort
    • ParkingLot Algorithm
    • LRU cache
    • Priority Queue
  • Algorithms
    • Algorithm
    • Recursion
    • Sorting
    • Searching
    • Dynamic Programming
  • Problems
    • Array
      • Two Sum
      • Two Sum II - Input Array Is Sorted
      • Contains Duplicate
      • Maximum Subarray
      • House Robber
      • Move Zeroes
      • Rotate Array
      • Plus One
      • Find number of subarrays with even length
      • Find number of subarrays with even sum
      • Find Missing Element
      • Reduce Array Size to The Half
      • Remove Duplicates
      • Merge Sorted Arrays
      • Arrays Intersection
      • 3Sum
      • Trapping Rain Water
      • Maximum sum of a subarray
      • Longest Subarray
      • Subarray Sum Equals K
      • Container With Most Water
      • Missing Number
      • Roman to Integer
      • First Missing Positive
      • Unique Integers That Sum Up To 0
      • Integer to Roman
      • Flatten
    • String
      • Check if two strings are permutation of each other
      • String Compression
      • Palindrome Permutation
      • Determine if a string has all Unique Characters
      • One Away
      • Longest Substring Without Repeating Characters
      • Valid Palindrome
      • Valid Palindrome II
      • Backspace String Compare
      • First Unique Character in a String
      • Is Subsequence
      • URLify a given string
      • String has same characters at same position
      • Number of Ways to Split a String
      • Check whether two Strings are anagram of each other
      • Print last `n` lines of a big file or big string.
      • Multiply Strings
    • Matrix
      • Search a 2D Matrix
      • Search a 2D Matrix II
      • Rotate Matrix
      • Spiral Matrix
      • Set Matrix Zeroes
    • Bit Manipulation
      • Sum of Two Integers
      • Reverse Number
      • Reverse Number II
      • Binary Bits Count
      • Binary Bits Count II
    • Stack
      • Valid Parentheses
      • Balance or not expression
      • Decode String
    • Tree
      • Binary Tree Inorder Traversal
      • Binary Tree Preorder Traversal
      • Binary Tree Postorder Traversal
      • Binary Tree Level Order Traversal
      • Binary Tree Return All Root-To-Leaf Paths
      • Binary Tree Height-Balanced
      • Valid Binary Search Tree
      • Binary Tree Sum of all left leaves.
    • Linked List
      • Linked List Delete Middle Node
      • Merge Sorted Linked List
      • Reverse Linked List
      • Remove Duplicates from Sorted List
      • Remove Duplicates from Unsorted List
      • Linked List Cycle
    • Graph
      • The Number Of Islands
      • Number of Closed Islands
      • Max Area of Island
      • Rotting Oranges
      • Number of Provinces
      • Course Schedule
      • Surrounded Regions
      • Snakes and Ladders
      • Widest Path Without Trees
      • Knight Probability in Chessboard
      • Possible moves of knight
      • Check Knight Tour Configuration
      • Steps by Knight
      • Network Delay Time
    • Greedy
      • Best Time to Buy and Sell Stock
      • Best Time to Buy and Sell Stock II
      • Smallest Subset Array
      • Jump Game
    • Backtracking
      • Towers of Hanoi
      • Subsets
      • Combination Sum
      • Sudoku Solver
      • Word Search
    • Heap
      • Kth Largest Element in an Array
      • Top K Frequent Elements
    • Sorting
      • Order Colors String
    • Recursion
      • Number To Text
      • Divide Number
Powered by GitBook
On this page
  1. Problems
  2. Array

House Robber

Array, Dynamic Programming

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

Solutions

The key insight to solve this problem is to realize that the robber has two options at each house: rob it or skip it.

  1. Rob it: If the robber decides to rob a house, they can't rob the previous house because of the connected security systems. So, the maximum amount of money they can get is the money in the current house plus the maximum money they can get from robbing the houses before the previous house.

  2. Skip it: If the robber decides to skip a house, they can rob the next house. So, the maximum amount of money they can get is the maximum money they can get from robbing the previous house.

At each house, the robber will make the decision that gives them the most money. They will continue this process for all the houses along the street. In the end, the maximum amount of money the robber can rob is the maximum money they can get from the last house.

This problem can be solved using different techniques like dynamic programming, brute force, etc., but the core idea remains the same.

Approach – Brute Force Technique

The brute force approach involves generating all possible combinations of non-adjacent houses to rob and calculating the total amount of money for each combination.

Steps

  1. Base Case: If i < 0, it means we have considered all houses, so we return 0. This is the base case for our recursion.

  2. Recursive Case: For i >= 0 (i.e., there are still houses that we haven't considered), we have two options:

    • Rob the current house: If we rob the current house (nums[i]), we can't rob the previous house (nums[i - 1]), but we can rob the house before that (nums[i - 2]). So, we make a recursive call to Rob(nums, i - 2) and add nums[i].

    • Skip the current house: If we skip the current house, we can rob the previous house. So, we make a recursive call to Rob(nums, i - 1).

  3. Return the Maximum: We return the maximum of the two options, which represents the maximum amount of money that can be robbed considering the first i houses.

public class Solution
{
    public int Rob(int[] nums)
    {
        return Rob(nums, nums.Length - 1);
    }
    int Rob(int[] nums, int i)
    {
        if (i < 0)
        {
            return 0;
        }
        return Math.Max(Rob(nums, i - 2) + nums[i], Rob(nums, i - 1));
    }

}

Complexity

  • Time Complexity: O(2^n)

  • Auxiliary Space: O(1)

Approach – Dynamic Programming Technique

The optimized approach uses dynamic programming to store the maximum amount of money that can be robbed up to each house.

Steps

Sure, I'd be happy to explain the steps of this algorithm. This is an implementation of a solution to the house robber problem using dynamic programming. The goal is to find the maximum amount of money that can be robbed from non-adjacent houses.

Here are the steps:

  1. Initialize: Set sum and prevSum to 0. sum will keep track of the maximum amount of money that can be robbed up to the current house, while prevSum will keep track of the maximum amount of money that can be robbed up to the previous house.

  2. Iterate through the array: For each element in the array (index i from 0 to nums.Length - 1), do the following:

    • Store the current sum in a temporary variable temp.

    • Update sum to be the maximum of the sum of the current house's money and the maximum money from the previous house (prevSum + nums[i]), and the current sum. This step essentially says, "consider the current house's money plus the maximum money from the house before the previous house, or keep the maximum money from the previous house."

    • Update prevSum to be the value of temp (which is the old sum). This step moves the sum from the current house to the next house.

  3. Return the result: After going through all the houses, return sum which now contains the maximum amount of money that can be robbed.

public class Solution {
    public int Rob(int[] nums) {
        
        int sum=0;
        int prevSum=0;
        for(int i=0;i<nums.Length;i++){
            int temp =sum;
            sum= Math.Max(prevSum+nums[i],sum);
            prevSum=temp;
        }
        return sum;
    }
}

Complexity

  • Time Complexity: O(n)

  • Auxiliary Space: O(1)

PreviousMaximum SubarrayNextMove Zeroes

Last updated 1 year ago