Count Number of Ways to Place Houses

Problem Description

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 10^9 + 7.

Key Insights

• Each side of the street can be treated independently when placing houses.
• If a house is placed on the i-th plot, the (i+1)-th plot cannot have a house.
• The problem can be solved using dynamic programming to keep track of valid arrangements.
• The number of ways to arrange houses can be computed using combinatorial logic (Fibonacci-like sequence).

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

We can define a dynamic programming approach where we maintain two variables to keep track of the number of ways to place houses on one side of the street. Let a be the number of ways to place houses without restrictions, and b be the number of ways to place houses such that the last plot is empty. The relationship can be derived as:

• When the last plot is empty, we can either place a house on the previous plot or leave it empty.
• The state transitions can be defined as:
  • a = b + 1 (to account for the empty case)
  • b = a (if we place a house on the current plot, we can only rely on b for the previous plot)

The total number of ways for both sides is then total_ways = (a + b) * (a + b), as both sides are independent.

Code Solutions