There is a street with n * 2 plots, where there are n plots on each side of the street. The plots on each side are numbered from 1 to n. On each plot, a house can be placed.
Return the number of ways houses can be placed such that no two houses are adjacent to each other on the same side of the street. Since the answer may be very large, return it modulo 109 + 7.
Note that if a house is placed on the ith plot on one side of the street, a house can also be placed on the ith plot on the other side of the street.
Example 1:
Input: n = 1 Output: 4 Explanation: Possible arrangements: 1. All plots are empty. 2. A house is placed on one side of the street. 3. A house is placed on the other side of the street. 4. Two houses are placed, one on each side of the street.
Example 2:
Input: n = 2 Output: 9 Explanation: The 9 possible arrangements are shown in the diagram above.
Constraints:
1 <= n <= 104Problem Overview: You are given n plots on each side of a street. Each plot can either contain a house or remain empty, but adjacent plots on the same side cannot both contain houses. The task is to count the total number of valid placement configurations across both sides of the street.
The key observation: the two sides of the street are independent. First compute the number of valid arrangements for a single row of n plots with no two adjacent houses. Then square the result to account for both sides.
Approach 1: Dynamic Programming with Fibonacci Relation (Time: O(n), Space: O(n) or O(1))
For a single side of the street, this becomes the classic problem of counting binary strings of length n with no consecutive 1s. Let dp[i] represent the number of valid ways to arrange houses in the first i plots. If the current plot is empty, any valid arrangement of i-1 plots works. If the current plot contains a house, the previous plot must be empty, so the count comes from i-2. This gives the recurrence dp[i] = dp[i-1] + dp[i-2]. The sequence is identical to Fibonacci numbers. After computing the result for one side, square it to account for both sides. Use modulo 1e9+7 to avoid overflow.
This approach is straightforward and efficient. You iterate once from 1 to n, updating two previous states. With state compression, the space drops from O(n) to O(1). This method is commonly used in dynamic programming problems where the current state depends on a small number of previous states.
Approach 2: Matrix Exponentiation (Time: O(log n), Space: O(1))
The Fibonacci recurrence can be represented as a matrix transformation. The relation F(n) = F(n-1) + F(n-2) can be expressed using the matrix [[1,1],[1,0]]. Raising this matrix to the power n allows you to compute the result in logarithmic time using fast exponentiation.
Matrix exponentiation repeatedly squares the transition matrix while reducing the exponent by half each step. This reduces the complexity from linear to logarithmic time. After computing the Fibonacci value for one street side, square the result to get the total configurations across both sides.
This technique appears frequently in problems involving linear recurrences and is a standard optimization when n becomes very large. It is closely related to topics like matrix exponentiation and mathematical recurrence transformations.
Recommended for interviews: The dynamic programming approach with the Fibonacci relation is what most interviewers expect. It shows that you recognize the adjacency constraint and convert it into a recurrence. Matrix exponentiation demonstrates deeper algorithmic knowledge but is typically discussed as an optimization after presenting the DP solution.
Identify the problem as a variation of the Fibonacci sequence solving adjacency constraints for house placement. Establish a dynamic programming relation where dp[i] defines the number of ways to arrange houses on i plots with no two adjacent.
Without losing generality, analyze one side of the street. For n plots, the problem becomes a classic non-adjacent placement problem, solvable by a Fibonacci-like approach. This leads to relation dp[i] = dp[i-1] + dp[i-2], since if the plot i is filled, plot i-1 can't be, and if plot i is not filled, it follows the i-1 arrangement.
Since both sides of the street are independent, compute the total ways considering both sides as the square of the computed dp[n] value modulo 10^9 + 7.
This C solution uses an iterative approach to calculate the number of arrangements using a Fibonacci-like sequence where prev and cur correspond to dp[i-2] and dp[i-1], respectively. The computation continues until the nth plot number, taking modulus 10^9+7 at every step to prevent overflow.
Time Complexity: O(n) - Iterates through n plots.
Space Complexity: O(1) - Uses constant space for calculations.
Another efficient method to solve this problem, especially for large values of n, is Matrix Exponentiation, which offers improved time complexity for Fibonacci-related sequence generation. The Fibonacci sequence or similar can be represented using matrix multiplication, allowing for efficient computation through exponentiation using binary methods.
This method uses matrix exponentiation to fast calculate the nth Fibonacci number, exploiting the property that Fibonacci sequences can be computed via matrix power with an initial base matrix. This reduces the problem of calculating dp[n] to logarithmic time via exponents.
C
C++
Java
Python
JavaScript
Time Complexity: O(log n) - Efficient due to matrix exponentiation
Space Complexity: O(1) apart from recursive call stack
Since the placement of houses on both sides of the street does not affect each other, we can consider the placement on one side only, and then square the number of ways for one side to get the final result modulo.
We define f[i] to represent the number of ways to place houses on the first i+1 plots, with the last plot having a house. We define g[i] to represent the number of ways to place houses on the first i+1 plots, with the last plot not having a house. Initially, f[0] = g[0] = 1.
When placing the (i+1)-th plot, there are two cases:
(i+1)-th plot has a house, then the i-th plot must not have a house, so the number of ways is f[i] = g[i-1];(i+1)-th plot does not have a house, then the i-th plot can either have a house or not, so the number of ways is g[i] = f[i-1] + g[i-1].Finally, we square f[n-1] + g[n-1] modulo to get the answer.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the street.
| Approach | Complexity |
|---|---|
| Dynamic Programming with Fibonacci Relation | Time Complexity: O(n) - Iterates through n plots. Space Complexity: O(1) - Uses constant space for calculations. |
| Matrix Exponentiation | Time Complexity: O(log n) - Efficient due to matrix exponentiation Space Complexity: O(1) apart from recursive call stack |
| Dynamic Programming | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Fibonacci Relation | O(n) | O(1) optimized | Best general solution. Simple recurrence and easy to implement in interviews. |
| Matrix Exponentiation | O(log n) | O(1) | Useful when n is extremely large or when optimizing Fibonacci-style recurrences. |
Weekly Contest 299 | Leetcode 2320 Count Number of Ways to Place Houses | DP | Fibonacci • Coding Decoded • 2,091 views views
Watch 9 more video solutions →Practice Count Number of Ways to Place Houses with our built-in code editor and test cases.
Practice on FleetCode