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 <= 104The key observation in #2320 Count Number of Ways to Place Houses is that houses cannot be placed on adjacent plots on the same side of the street. This creates a classic dynamic programming pattern similar to the Fibonacci sequence.
First, consider only one side of the street. For each plot, you can either place a house or leave it empty. However, if you place a house, the previous plot must be empty. This leads to a recurrence where the number of valid arrangements for i plots depends on the results for i-1 and i-2.
After computing the valid arrangements for a single side, note that the two sides of the street are independent. Therefore, the total number of valid configurations is the square of the single-side count. Since values can grow large, calculations are performed using modulo arithmetic.
This dynamic programming approach runs in O(n) time and can be optimized to O(1) space by storing only the last two states.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming (Fibonacci-style) | O(n) | O(n) |
| Optimized DP with constant variables | O(n) | O(1) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Try coming up with a DP solution for one side of the street.
The DP for one side of the street will bear resemblance to the Fibonacci sequence.
The number of different arrangements on both side of the street is the same.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, problems like this are common in interviews because they test understanding of dynamic programming and recurrence relations. Variations of Fibonacci-style DP frequently appear in technical interviews.
The configurations on the left and right sides of the street are independent. After calculating the valid arrangements for one side, multiplying the count by itself accounts for all combinations across both sides.
A simple dynamic programming array or even two variables is sufficient. Since each state depends only on the previous two values, the space can be optimized to constant space.
The optimal approach uses dynamic programming with a Fibonacci-style recurrence. You compute the number of valid arrangements for one side of the street and then square the result because the two sides are independent.