House Robber Ii

                                            
class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size() == 1) {
            return nums[0];
        } 
        
        return max(robHelper(nums, 0, nums.size() - 2), robHelper(nums, 1, nums.size() - 1));
    }
    
    int robHelper(vector<int>& nums, int start, int end) {
        int prevMax = 0;
        int currMax = 0;
        
        for (int i = start; i <= end; i++) {
            int temp = currMax;
            currMax = max(prevMax + nums[i], currMax);
            prevMax = temp;
        }
        
        return currMax;
    }
};

                                            
class Solution {
    public int rob(int[] nums) {
        if(nums.length == 1){
            return nums[0];
        }
        return Math.max(robRange(nums, 0, nums.length - 2), robRange(nums, 1, nums.length - 1));
    }
    
    private int robRange(int[] nums, int start, int end){
        int rob1 = 0;
        int rob2 = 0;
        for(int i = start; i <= end; i++){
            int temp = Math.max(nums[i] + rob1, rob2);
            rob1 = rob2;
            rob2 = temp;
        }
        return rob2;
    }
}

                                            
class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        def rob_range(nums, start, end):
            rob_next, rob_curr = 0, 0
            for i in range(start, end):
                rob_next, rob_curr = max(rob_next, rob_curr), rob_next + nums[i]
            return max(rob_next, rob_curr)
        
        if len(nums) == 1:
            return nums[0]
        
        return max(rob_range(nums, 0, len(nums)-1), rob_range(nums, 1, len(nums)))

                                            
int rob(int* nums, int numsSize) {
    if (numsSize == 1) {
        return nums[0];
    }
    
    int rob1 = robHelper(nums, 0, numsSize - 2);
    int rob2 = robHelper(nums, 1, numsSize - 1);
    
    return rob1 > rob2 ? rob1 : rob2;
}

int robHelper(int* nums, int start, int end) {
    int prev1 = 0;
    int prev2 = 0;
    
    for (int i = start; i <= end; i++) {
        int temp = prev1;
        prev1 = fmax(prev2 + nums[i], prev1);
        prev2 = temp;
    }
    
    return prev1;
}

                                            
public class Solution {
    public int Rob(int[] nums) {
        if (nums.Length == 1) {
            return nums[0];
        }
        
        return Math.Max(RobHelper(nums, 0, nums.Length - 2), RobHelper(nums, 1, nums.Length - 1));
    }
    
    private int RobHelper(int[] nums, int start, int end) {
        int prevMax = 0;
        int currMax = 0;
        
        for (int i = start; i <= end; i++) {
            int temp = currMax;
            currMax = Math.Max(prevMax + nums[i], currMax);
            prevMax = temp;
        }
        
        return currMax;
    }
}

                                            
/**
 * @param {number[]} nums
 * @return {number}
 */
const rob = (nums) => {
    if (nums.length === 1) return nums[0];
    
    const robRange = (start, end) => {
        let prev1 = 0, prev2 = 0;
        for (let i = start; i <= end; i++) {
            const current = Math.max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = current;
        }
        return prev1;
    };
    
    return Math.max(robRange(0, nums.length - 2), robRange(1, nums.length - 1));
};

                                            
function rob(nums: number[]): number {
    const n = nums.length;
    if (n === 1) return nums[0];
  
    const robHelper = (start: number, end: number): number => {
        let prevMax = 0;
        let currMax = 0;
        for (let i = start; i <= end; i++) {
            const temp = currMax;
            currMax = Math.max(currMax, prevMax + nums[i]);
            prevMax = temp;
        }
        return currMax;
    };
  
    return Math.max(robHelper(0, n - 2), robHelper(1, n - 1));
};

                                            
class Solution {
    /**
     * @param Integer[] $nums
     */
    function rob($nums) {
        $n = count($nums);
        if ($n == 1) {
            return $nums[0];
        }
        
        return max($this->robRange($nums, 0, $n - 2), $this->robRange($nums, 1, $n - 1));
    }
    
    function robRange($nums, $start, $end) {
        $dp1 = 0;
        $dp2 = 0;
        
        for ($i = $start; $i <= $end; $i++) {
            $temp = $dp1;
            $dp1 = max($dp2 + $nums[$i], $dp1);
            $dp2 = $temp;
        }
        
        return max($dp1, $dp2);
    }
}

                                            
class Solution {
    func rob(_ nums: [Int]) -> Int {
        func robHelper(_ nums: [Int]) -> Int {
            var dp = Array(repeating: 0, count: nums.count)
            
            if nums.count == 1 {
                return nums[0]
            }
            
            dp[0] = nums[0]
            dp[1] = max(nums[0], nums[1])
            
            for i in 2..<nums.count {
                dp[i] = max(dp[i-1], dp[i-2] + nums[i])
            }
            
            return dp[nums.count - 1]
        }
        
        if nums.count == 1 {
            return nums[0]
        }
        
        return max(robHelper(Array(nums[0..<nums.count-1])), robHelper(Array(nums[1..<nums.count])))
    }
}

                                            
class Solution {
    fun rob(nums: IntArray): Int {
        if (nums.size == 1) {
            return nums[0]
        }
        
        return Math.max(robHelper(nums, 0, nums.size - 2), robHelper(nums, 1, nums.size - 1))
    }
    
    fun robHelper(nums: IntArray, start: Int, end: Int): Int {
        var prevMax = 0
        var currentMax = 0
        
        for (i in start..end) {
            val temp = currentMax
            currentMax = Math.max(prevMax + nums[i], currentMax)
            prevMax = temp
        }
        
        return currentMax
    }
}

                                            
class Solution {
  int rob(List<int> nums) {
    if (nums.length == 1) {
      return nums[0];
    }
    
    int rob1 = robRange(nums.sublist(0, nums.length - 1));
    int rob2 = robRange(nums.sublist(1));
    
    return rob1 > rob2 ? rob1 : rob2;
  }
  
  int robRange(List<int> nums) {
    int previousMax = 0;
    int currentMax = 0;
    
    for (int num in nums) {
      int temp = currentMax;
      currentMax = currentMax > previousMax + num ? currentMax : previousMax + num;
      previousMax = temp;
    }
    
    return currentMax;
  }
}

                                            
func rob(nums []int) int {
    if len(nums) == 1 {
        return nums[0]
    }
    return max(robHelper(nums[:len(nums)-1]), robHelper(nums[1:]))
}

func robHelper(nums []int) int {
    if len(nums) == 1 {
        return nums[0]
    }
    prevMax, currMax := 0, 0
    for _, num := range nums {
        temp := currMax
        currMax = max(prevMax+num, currMax)
        prevMax = temp
    }
    return currMax
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

                                            
# @param {Integer[]} nums
# @return {Integer}
def rob(nums)
    return 0 if nums.empty?
    return nums[0] if nums.length == 1
    return [nums[0], nums[1]].max if nums.length == 2
    
    def rob_range(nums, start, finish)
        prev_max = curr_max = 0
        for i in start..finish
            temp = curr_max
            curr_max = [prev_max + nums[i], curr_max].max
            prev_max = temp
        end
        curr_max
    end
    
    return [rob_range(nums, 0, nums.length - 2), rob_range(nums, 1, nums.length - 1)].max
end

                                            
object Solution {
  def rob(nums: Array[Int]): Int = {
    def robRange(nums: Array[Int], start: Int, end: Int): Int = {
      var rob1 = 0
      var rob2 = 0
      var currentRob = 0

      for (i <- start to end) {
        currentRob = Math.max(rob1 + nums(i), rob2)
        rob1 = rob2
        rob2 = currentRob
      }

      return currentRob
    }

    if (nums.length == 1) {
      return nums(0)
    } else {
      return Math.max(robRange(nums, 0, nums.length - 2), robRange(nums, 1, nums.length - 1))
    }
  }
}

                                            
impl Solution {
    pub fn rob(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        
        if n == 0 {
            return 0;
        } else if n == 1 {
            return nums[0];
        }
        
        fn rob_helper(nums: &[i32]) -> i32 {
            let mut prev_max = 0;
            let mut curr_max = 0;
            
            for &num in nums {
                let temp = curr_max;
                curr_max = curr_max.max(prev_max + num);
                prev_max = temp;
            }
            
            return curr_max;
        }
        
        return rob_helper(&nums[0..n-1]).max(rob_helper(&nums[1..n]));
    }
}

                                            
(define/contract (rob nums)
  (-> (listof exact-integer?) exact-integer?)
  
  (define (robber nums)
    (define (robber-helper start end)
      (let loop ((i start) (prev 0) (curr 0))
        (cond
          ((= i end) curr)
          (else (loop (+ i 1) curr (max (+ (list-ref nums i) prev) curr)))
          )
        )
      )
    (if (null? nums) 0
        (if (< (length nums) 2) (apply max nums)
            (max (robber-helper 0 (- (length nums) 1))
                 (robber-helper 1 (length nums)))
            )
      )
    )
  
  (robber nums)
  )

                                            
-spec rob(Nums :: [integer()]) -> integer().
rob(Nums) ->
    Length = length(Nums),
    case Length of
        0 -> 0;
        1 -> hd(Nums);
        _ -> Max1 = rob_helper(lists:sublist(Nums, 1, Length - 1)),
             Max2 = rob_helper(lists:sublist(Nums, 2, Length)),
             lists:max([Max1, Max2])
    end.

rob_helper(Nums) ->
    rob_helper(Nums, 0, 0).

rob_helper([], Prev, Curr) ->
    lists:max([Prev, Curr]);
rob_helper([H | T], Prev2, Prev1) ->
    rob_helper(T, Prev1, lists:max([Prev1, H + Prev2])).

To solve this coding challenge, you actually need to figure out a way to maximize the amount of money you can rob without alerting the police. The crux of the problem is that the houses are arranged in a circle, and you cannot rob two adjacent houses, which complicates things since the first and last houses are also adjacent.

Explanation

The problem can be divided into two sub-problems to handle the circular nature of the houses:

Consider robbing from the first house to the second-to-last house.
Consider robbing from the second house to the last house.

By solving these two sub-problems separately, you can take the maximum of the two as your final answer because these two sub-problems ensure that the first and last houses are never robbed together.

Detailed steps are as follows:

Check if the length of
nums

is 1 :

If there is only one house, the maximum amount of money that can be robbed is simply the value in that house.

Define a helper function
rob_range

:

The helper function
rob_range

calculates the maximum amount of money that can be robbed within a specific range of houses (from index
start

to index
end-1

).
Use dynamic programming principles where you maintain two variables: one for the current maximum amount if you skip the current house (
rob_next

), and another for the current value if you decide to rob the current house (
rob_curr

).

Compute the maximum money for two scenarios :

First scenario: Rob houses from the first to the second-to-last (index 0 to
len(nums)-2

).
Second scenario: Rob houses from the second to the last (index 1 to
len(nums)-1

).

Return the maximum of these two values .

Here's the pseudocode for this approach with detailed comments:

                                            
# Function to calculate maximum amount of money that can be robbed 
# in a straight line given a range of houses
def rob_range(nums, start, end):
rob_next = 0  # Initialize maximum money if next house is skipped
rob_curr = 0  # Initialize maximum money if current house is robbed

# Iterate through the houses from start to end-1
for i in range(start, end):
# Temporarily store the current rob_next value
temp = rob_next

# Update rob_next to be the maximum of rob_next and rob_curr
# rob_next now holds the maximum value if the current house is skipped
rob_next = max(rob_next, rob_curr)

# Update rob_curr to add the current house's value to temp
# rob_curr now holds the maximum value if this house is robbed
rob_curr = temp + nums[i]

# Return the maximum value between rob_next and rob_curr
return max(rob_next, rob_curr)

# Main function to calculate the maximum amount of money that can be robbed
def rob(nums):
# If there's only one house, just return the value of that house
if length(nums) == 1:
return nums[0]

# Calculate max money robbing from first house to second-to-last house
max_money_case_1 = rob_range(nums, 0, length(nums) - 1)

# Calculate max money robbing from second house to last house
max_money_case_2 = rob_range(nums, 1, length(nums))

# Return the maximum money between the two cases
return max(max_money_case_1, max_money_case_2)

Step-by-Step Explanation

Check Edge Case :

If there is only one house, directly return its value since that's the only option.

Helper Function
rob_range

:

Initialize two variables
rob_next

and
rob_curr

to keep track of the maximum money robbed by choosing to skip or rob the current house, respectively.
Loop from the
start

index to one less than the
end

index.
In each iteration, update
rob_next

to be the maximum value between
rob_next

and
rob_curr

.
Update
rob_curr

by adding the value of the current house to the previously stored
rob_next

(before it gets updated).
Return the maximum value between
rob_next

and
rob_curr

.

Consider Two Scenarios :

Call the
rob_range

function for the range from the first house to the second-to-last house.
Call the
rob_range

function for the range from the second house to the last house.

Return Result :

Return the maximum money robbed between the two scenarios. This will ensure that the solution includes all possible non-adjacent houses and accounts for the circular nature of the problem.

By following these steps and logic, you can solve the House Robber II problem efficiently.