# Count Number of Ways to Place Houses
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-number-of-ways-to-place-houses)
Canonical: https://scaleengineer.com/dsa/problems/count-number-of-ways-to-place-houses
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Companies:** [Nagarro](https://scaleengineer.com/companies/nagarro)
---
## Problem
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:**

![](https://assets.glich.co/dsa/count-number-of-ways-to-place-houses/image0.png) 

**Input:** n = 2
**Output:** 9
**Explanation:** The 9 possible arrangements are shown in the diagram above.

**Constraints:**

* `1 <= n <= 104`

# Approaches
## Top-Down Dynamic Programming (Memoization)
The core of the problem is to find the number of ways to arrange houses on a single line of `n` plots with no two houses being adjacent. The arrangements on the two sides of the street are independent, so if we find the number of ways for one side, let's say `W`, the total number of ways is `W * W`.

The number of ways for a single side follows the Fibonacci sequence. Let `ways(n)` be the number of ways for `n` plots. We can derive the recurrence `ways(n) = ways(n-1) + ways(n-2)`. This is because the last plot can either be empty (leaving `ways(n-1)` possibilities for the prefix) or have a house (which forces the second to last plot to be empty, leaving `ways(n-2)` possibilities).

This approach uses recursion with memoization (a top-down dynamic programming technique) to compute `ways(n)`. We store the result for each `n` in a memoization table to avoid redundant calculations, which would otherwise lead to an exponential time complexity.
**Time:** O(n) - Each state from `0` to `n` is computed only once due to memoization. · **Space:** O(n) - for the memoization array and the depth of the recursion stack.
**Pros:** Conceptually straightforward, as it directly translates the recurrence relation into code.; Efficient enough for the given constraints.
**Cons:** Uses O(n) extra space for the memoization table.; Recursive solutions have function call overhead, which can be slightly slower than an iterative approach.; For extremely large `n` (not the case here), it could lead to a stack overflow.
### Explanation
We define a recursive function, say `solve(k)`, that calculates the number of ways for `k` plots. To prevent re-calculating the same state multiple times, we use a memoization array, `memo`, initialized to a value indicating that the state has not been computed (e.g., 0).

The base cases for our recursion are `solve(0) = 1` and `solve(1) = 2`. For any other `k`, we first check if `memo[k]` has been computed. If it has, we return the stored value. Otherwise, we compute it using the recurrence `solve(k) = solve(k-1) + solve(k-2)`, store the result in `memo[k]`, and then return it. All additions are performed modulo `10^9 + 7`.

Finally, the main function calls this helper to get the number of ways for one side with `n` plots, and then squares this result for the final answer.

```java
class Solution {
    long MOD = 1_000_000_007;
    long[] memo;

    public int countHousePlacements(int n) {
        memo = new long[n + 1];
        long waysForOneSide = solve(n);
        return (int)((waysForOneSide * waysForOneSide) % MOD);
    }

    private long solve(int k) {
        if (k == 0) return 1;
        if (k == 1) return 2;
        if (memo[k] != 0) {
            return memo[k];
        }

        long result = (solve(k - 1) + solve(k - 2)) % MOD;
        memo[k] = result;
        return result;
    }
}
```
### Algorithm
1.  First, observe that the house placements on the two sides of the street are independent of each other. If there are `W` ways to place houses on one side, the total number of ways for the entire street is `W * W`.
2.  The problem now is to find the number of ways to place houses on a single row of `n` plots such that no two houses are adjacent. Let's call this `ways(n)`.
3.  This subproblem can be solved using dynamic programming. Let `dp[i]` be the number of valid ways for `i` plots.
4.  The recurrence relation is `dp[i] = dp[i-1] + dp[i-2]`. This is because for `i` plots, the `i`-th plot can either be empty (leaving `dp[i-1]` ways for the first `i-1` plots) or have a house. If the `i`-th plot has a house, the `(i-1)`-th plot must be empty, which means we are looking at valid arrangements for `i-2` plots, giving `dp[i-2]` ways.
5.  The base cases are `dp[0] = 1` (one way for zero plots: the empty arrangement) and `dp[1] = 2` (two ways for one plot: empty or a house).
6.  We can implement this using a top-down recursive approach with a memoization table to store the results of `dp[i]` to avoid re-computation.
7.  Create a memoization array `memo` of size `n+1`.
8.  Implement a recursive function `solve(k)` that returns `dp[k]`. Inside the function, check the memo table before computing recursively.
9.  The main function calls `solve(n)` to get the ways for one side, squares it, and returns the result modulo `10^9 + 7`.

## Bottom-Up Dynamic Programming
This approach also solves the problem by calculating the number of ways for a single side, `ways(n)`, which follows the Fibonacci-like recurrence `ways(n) = ways(n-1) + ways(n-2)`. However, instead of a top-down recursive solution, it uses a bottom-up iterative method.

We build the solution from the ground up. We know the answers for the smallest subproblems (`n=0` and `n=1`) and use them to compute the answer for `n=2`, then use those to compute for `n=3`, and so on, until we reach `n`. This is done by iterating and filling a DP array.
**Time:** O(n) - A single loop runs from 2 to `n`. · **Space:** O(n) - for the DP array.
**Pros:** Avoids recursion, eliminating function call overhead and the risk of stack overflow.; Generally slightly faster in practice than the memoized recursive version.; Easy to understand and implement.
**Cons:** Uses O(n) extra space, which is not optimal.
### Explanation
We create a DP array, `dp`, of size `n+1`. `dp[i]` will store the number of ways to place houses on `i` plots. We initialize the base cases: `dp[0] = 1` (for an empty set of plots, there's one way: do nothing) and `dp[1] = 2` (for one plot, it can be empty or have a house).

Then, we loop from `i = 2` up to `n`. In each step, we calculate `dp[i]` by summing the previous two values, `dp[i-1]` and `dp[i-2]`, taking the result modulo `10^9 + 7`. This directly implements the recurrence relation in an iterative fashion.

The final value for one side is `dp[n]`. We square this and take the modulo to get the answer for both sides of the street.

```java
class Solution {
    public int countHousePlacements(int n) {
        long MOD = 1_000_000_007;
        if (n == 0) return 1;

        long[] dp = new long[n + 1];
        dp[0] = 1; // Base case: 1 way for 0 plots
        dp[1] = 2; // Base case: 2 ways for 1 plot

        for (int i = 2; i <= n; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
        }

        long waysForOneSide = dp[n];
        return (int)((waysForOneSide * waysForOneSide) % MOD);
    }
}
```
### Algorithm
1.  As with the previous approach, the problem reduces to finding `ways(n)`, the number of arrangements for a single side, and squaring it.
2.  The recurrence `ways(n) = ways(n-1) + ways(n-2)` is used.
3.  Instead of recursion, we use an iterative approach (bottom-up DP).
4.  Create a DP array, `dp`, of size `n+1`.
5.  Initialize the base cases: `dp[0] = 1` and `dp[1] = 2`.
6.  Iterate from `i = 2` to `n`, filling the `dp` array using the formula `dp[i] = (dp[i-1] + dp[i-2]) % MOD`.
7.  After the loop, `dp[n]` will hold the value for `ways(n)`.
8.  Calculate `(dp[n] * dp[n]) % MOD` for the final answer.

## Space-Optimized Dynamic Programming
This approach is an optimization of the bottom-up DP solution. We observe that to calculate the number of ways for `n` plots, we only need the results for `n-1` and `n-2`. Storing the entire history in a DP array is unnecessary.

We can achieve the same result using only a constant amount of space by keeping track of just the last two values in the sequence. We iterate from 2 to `n`, and in each step, we calculate the new value, then update our variables to discard the oldest value and keep the two most recent ones for the next iteration.
**Time:** O(n) - A single loop runs `n-1` times. · **Space:** O(1) - We only use a few variables to store the intermediate results.
**Pros:** Optimal space complexity of O(1).; Maintains the efficient O(n) time complexity.; Very practical and efficient for the given constraints.
**Cons:** The logic might be slightly less intuitive at first glance compared to the direct DP array approach.
### Explanation
We can track the number of valid arrangements based on what the last plot contains. Let `house` be the number of ways where the last plot has a house, and `empty` be the number of ways where it's empty.

For `n=1`, `house = 1` and `empty = 1`.

Now, we iterate from `i = 2` to `n`. To find the values for `i` plots:
- An arrangement of `i` plots ending in a house must have had an empty plot at `i-1`. So, `new_house` for `i` is equal to the `empty` count for `i-1`.
- An arrangement of `i` plots ending with an empty plot could have had either a house or an empty plot at `i-1`. So, `new_empty` for `i` is the sum of `house` and `empty` for `i-1`.

After the loop, the total ways for one side is `house + empty`. We square this and take the modulo.

```java
class Solution {
    public int countHousePlacements(int n) {
        long MOD = 1_000_000_007;

        // Ways for one side with i plots
        long house = 1; // Arrangements ending with a house for i=1
        long empty = 1; // Arrangements ending with an empty plot for i=1

        for (int i = 2; i <= n; i++) {
            long new_house = empty;
            long new_empty = (house + empty) % MOD;
            house = new_house;
            empty = new_empty;
        }

        long totalForOneSide = (house + empty) % MOD;
        return (int)((totalForOneSide * totalForOneSide) % MOD);
    }
}
```
### Algorithm
1.  The recurrence relation `ways(i) = ways(i-1) + ways(i-2)` shows that to compute the current state, we only need the previous two states.
2.  Instead of a full DP array, we can use a few variables to keep track of the necessary previous values.
3.  Let's track the number of ways for `i` plots that end with a house (`house`) and that end with an empty plot (`empty`).
4.  Initialize for `i=1`: `house = 1`, `empty = 1`.
5.  Iterate from `i = 2` to `n`.
6.  In each iteration, calculate the new values for `i` plots based on the values for `i-1` plots:
    *   `new_house = empty` (A house can only be placed after an empty plot).
    *   `new_empty = (empty + house) % MOD` (An empty plot can follow either a house or an empty plot).
7.  Update `house = new_house` and `empty = new_empty`.
8.  After the loop, the total ways for one side is `(house + empty) % MOD`.
9.  Square this total and take the modulo for the final answer.

# Solutions
### CSharp

```csharp
public class Solution {
    public int CountHousePlacements(int n) {
        const int mod = (int) 1 e9 + 7;
        int[] f = new int[n];
        int[] g = new int[n];
        f[0] = g[0] = 1;
        for (int i = 1; i < n; ++i) {
            f[i] = g[i - 1];
            g[i] = (f[i - 1] + g[i - 1]) % mod;
        }
        long v = (f[n - 1] + g[n - 1]) % mod;
        return (int)(v * v % mod);
    }
}
```

### Java

```java
class Solution {
public
  int countHousePlacements(int n) {
    final int mod = (int)1 e9 + 7;
    int[] f = new int[n];
    int[] g = new int[n];
    f[0] = 1;
    g[0] = 1;
    for (int i = 1; i < n; ++i) {
      f[i] = g[i - 1];
      g[i] = (f[i - 1] + g[i - 1]) % mod;
    }
    long v = (f[n - 1] + g[n - 1]) % mod;
    return (int)(v * v % mod);
  }
}

```

### CPP

```cpp
class Solution {
public:
  int countHousePlacements(int n) {
    const int mod = 1e9 + 7;
    int f[n], g[n];
    f[0] = g[0] = 1;
    for (int i = 1; i < n; ++i) {
      f[i] = g[i - 1];
      g[i] = (f[i - 1] + g[i - 1]) % mod;
    }
    long v = f[n - 1] + g[n - 1];
    return v * v % mod;
  }
};

```

### Python

```python
class Solution:
    def countHousePlacements(self, n: int) -> int: mod = 10 ** 9 + 7 f = [1] * n g = [1] * n for i in range(1, n): f[i] = g[i - 1] g[i] = (f[i - 1] + g[i - 1]) % mod v = f[- 1] + g[- 1] return v * v % mod

```