Description
I would like to contribute an optimized and efficient C++ solution for the problem House Robber (LeetCode Problem 198).
Plan of Contribution
• Implement all three approaches in a structured and well-commented manner.
• Add test cases for validation.
• Ensure readability and clarity in code.
Approaches & Complexity Analysis
1. Recursion + Memoization
• Time Complexity: O(n)
• Space Complexity: O(n) (DP array + recursion stack)
2. Tabulation (Bottom-Up DP)
• Time Complexity: O(n)
• Space Complexity: O(n) (DP array)
3. Space Optimized DP (Final Solution)
• Time Complexity: O(n)
• Space Complexity: O(1) (only two variables used)
Example Output
For input: [2,7,9,3,1]
The output will be: 12
Do let me know if this contribution works for the repository, and if there are any formatting or placement rules I should follow.
Looking forward for your response
Thanks,
Sayan (Github: @singhsayan)
Description
I would like to contribute an optimized and efficient C++ solution for the problem House Robber (LeetCode Problem 198).
Plan of Contribution
• Implement all three approaches in a structured and well-commented manner.
• Add test cases for validation.
• Ensure readability and clarity in code.
Approaches & Complexity Analysis
1. Recursion + Memoization
• Time Complexity: O(n)
• Space Complexity: O(n) (DP array + recursion stack)
2. Tabulation (Bottom-Up DP)
• Time Complexity: O(n)
• Space Complexity: O(n) (DP array)
3. Space Optimized DP (Final Solution)
• Time Complexity: O(n)
• Space Complexity: O(1) (only two variables used)
Example Output
For input: [2,7,9,3,1]
The output will be: 12
Do let me know if this contribution works for the repository, and if there are any formatting or placement rules I should follow.
Looking forward for your response
Thanks,
Sayan (Github: @singhsayan)