Watch 10 video solutions for Count Number of Ways to Place Houses, a medium level problem involving Dynamic Programming. This walkthrough by Coding Decoded has 2,091 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |