Leetcode 2320: Count Number of Ways to Place Houses
Given a street with two rows of plots, each containing n plots, find the number of ways houses can be placed such that no two houses are adjacent on the same side of the street. Return the result modulo 10^9 + 7.
Problem
Approach
Steps
Complexity
Input: The input consists of an integer n, representing the number of plots on each side of the street.
Example: n = 1
Constraints:
• 1 <= n <= 10^4
Output: Return the number of valid ways to place houses modulo 10^9 + 7.
Example: For n = 1, the output is 4.
Constraints:
• The result should be returned modulo 10^9 + 7.
Goal: To calculate the number of ways to place houses, we need to ensure that houses are not adjacent on the same side of the street. The result depends on valid placement configurations for both sides.
Steps:
• 1. Use dynamic programming to calculate the number of valid configurations for each side of the street.
• 2. Multiply the valid configurations for each side and return the result modulo 10^9 + 7.
Goal: The value of n is constrained between 1 and 10^4, and the result must be computed modulo 10^9 + 7.
Steps:
• 1 <= n <= 10^4
Assumptions:
• The street has exactly two sides, and both sides have n plots.
• Input: n = 1
• Explanation: For n = 1, the possible configurations are: no house, one house on the first side, one house on the second side, and one house on both sides. Hence, the total number of valid configurations is 4.
• Input: n = 2
• Explanation: For n = 2, the number of valid configurations is calculated by considering the valid placement of houses on each side and multiplying them together, resulting in 9 possible configurations.
Approach: We will use dynamic programming to calculate the number of valid ways to place houses on both sides of the street, ensuring no two houses are adjacent on the same side.
Observations:
• The problem can be broken down into calculating the number of valid ways to place houses on each side of the street.
• Dynamic programming is a good fit for this problem, as it allows us to compute the number of valid configurations efficiently.
• The problem can be solved by calculating the valid configurations for one side and then considering the placements on both sides simultaneously.
Steps:
• 1. Define a recursive function to calculate the number of valid placements on one side of the street.
• 2. Use dynamic programming to avoid redundant calculations and store intermediate results.
• 3. Multiply the results for both sides and return the final answer modulo 10^9 + 7.
Empty Inputs:
• There are no empty inputs since n will always be at least 1.
Large Inputs:
• For large values of n (up to 10^4), the solution should efficiently compute the result without running into performance issues.
Special Values:
• When n is small (e.g., n = 1), the number of valid placements can be easily verified manually.
Constraints:
• The solution should be efficient enough to handle the upper bound of n = 10^4.
class Solution {
long long mod = 1000000007;
public:
typedef long long ll;
vector<vector<int>> dp;
int countHousePlacements(int n) {
dp.resize(n + 1, vector<int> (2, -1));
ll res = ( rec(n, 0) + rec(n, 1) ) % mod;
return (res * res ) % mod;
}
int rec(int n, bool filled) {
if(n == 1) return 1;
if(dp[n][filled] != -1)
return dp[n][filled];
if(filled) return dp[n][filled] = rec(n - 1, !filled);
else return dp[n][filled] = ( rec(n - 1, filled) + rec(n - 1, !filled) ) % mod;
}
1 : Class Declaration
class Solution {
Define the `Solution` class which will contain the necessary methods to solve the problem.
2 : Mod Constant
long long mod = 1000000007;
Declare a constant `mod` to store the value 1000000007, which will be used for modular arithmetic to avoid overflow during calculations.
3 : Public Access Specifier
public:
Declare the following methods and variables as public so they can be accessed from outside the class.
4 : Typedef
typedef long long ll;
Create a typedef `ll` for `long long` to simplify the code and improve readability.
5 : DP Vector Declaration
vector<vector<int>> dp;
Declare a 2D vector `dp` to store results of subproblems. The dimensions of `dp` are based on the number of plots `n` and whether the last plot is filled.
6 : Main Function Declaration
int countHousePlacements(int n) {
Declare the `countHousePlacements` method that takes an integer `n` (the number of plots) as input and returns the number of ways to place houses.
7 : DP Resizing
dp.resize(n + 1, vector<int> (2, -1));
Resize the DP vector `dp` to store results for each plot `n` and each possible state (filled or not filled). Initialize all entries to -1 (indicating that they have not been calculated yet).
8 : Recursive Call
ll res = ( rec(n, 0) + rec(n, 1) ) % mod;
Make recursive calls to `rec` for both filled and not filled states at plot `n`. The results are summed up and taken modulo `mod`.
9 : Final Result
return (res * res ) % mod;
Return the final result, which is the square of `res` modulo `mod`, as the number of valid house placements.
10 : Recursive Function Declaration
int rec(int n, bool filled) {
Declare the recursive method `rec`, which computes the number of valid placements for `n` plots with the last plot either filled or not.
11 : Base Case
if(n == 1) return 1;
If there is only one plot, return 1, as there is exactly one way to place a house (either fill the plot or leave it empty).
12 : Memoization Check
if(dp[n][filled] != -1)
Check if the result for this subproblem has already been computed (memoization). If so, return the stored result.
13 : Memoized Result
return dp[n][filled];
Return the memoized result for the current subproblem.
14 : Recursion for Filled Plot
if(filled) return dp[n][filled] = rec(n - 1, !filled);
If the last plot is filled, recursively calculate the result for the previous plot with the opposite state (not filled).
15 : Recursion for Unfilled Plot
else return dp[n][filled] = ( rec(n - 1, filled) + rec(n - 1, !filled) ) % mod;
If the last plot is not filled, recursively calculate the result for both filled and unfilled states for the previous plot, and sum the results modulo `mod`.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n) since we calculate the number of valid placements using dynamic programming, iterating through each plot.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) due to the storage required for the dynamic programming table.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus