LeetCode 2320 - Count Number of Ways to Place Houses

LeetCode Problem 2320

Difficulty: 🟡 Medium
Topics: Dynamic Programming

Solution

Problem Understanding

The problem presents a street with n plots on each side, for a total of 2 * n plots. The goal is to count the number of ways to place houses on these plots such that no two houses are adjacent on the same side of the street. Placing houses on opposite sides of the street at the same index is allowed and does not violate the adjacency rule.

The input is a single integer n, representing the number of plots on one side of the street. The output is the total number of valid house placement configurations modulo 1_000_000_007, due to potential large numbers.

Constraints indicate 1 <= n <= 10^4, which means a brute-force approach that generates all possible arrangements (which would be exponential in size) is infeasible. Edge cases include very small n values like 1 or very large values like 10^4. A correct solution must handle these efficiently.

Approaches

Brute Force

A brute-force approach would attempt to generate all possible placements for n plots on each side, then filter out invalid configurations where houses are adjacent. For one side, there are 2^n possibilities, and for both sides, there are (2^n)^2 = 4^n total configurations. Checking adjacency for each configuration is linear in n. This approach is correct but infeasible because n can be as large as 10^4, making 4^n astronomically large.

Optimal Approach

The key insight is that the two sides of the street are independent. If we first compute the number of valid arrangements on one side, the total number of arrangements for the street is the square of that number, since the other side can independently have any valid configuration.

Counting arrangements on one side reduces to a classical dynamic programming problem: "count the number of ways to place houses on a line with no two adjacent houses." Let dp[i] be the number of ways to arrange houses on i plots. The recurrence is:

dp[i] = dp[i-1] + dp[i-2]

This recurrence works because for the ith plot, we either leave it empty (dp[i-1] ways) or place a house there (dp[i-2] ways because the previous plot must be empty). Base cases are dp[0] = 1 (no plots) and dp[1] = 2 (empty or one house).

Finally, the total number of configurations is dp[n] * dp[n] % MOD.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(4^n)	O(2^n)	Generates all placements and filters invalid ones, infeasible for large n
Optimal	O(n)	O(1)	DP computes valid arrangements for one side, then squares result

Algorithm Walkthrough

1. Define a constant MOD = 10^9 + 7 to handle large numbers.
2. Initialize two variables prev2 = 1 and prev1 = 2, representing dp[0] and dp[1] respectively. These store the number of ways to place houses on 0 and 1 plots.
3. Iterate i from 2 to n. For each i, compute the number of arrangements for i plots as current = (prev1 + prev2) % MOD. This implements the Fibonacci-style recurrence.
4. Update prev2 to prev1 and prev1 to current for the next iteration. After the loop, prev1 contains dp[n].
5. Compute the total number of arrangements for both sides as (prev1 * prev1) % MOD.
6. Return the result.

Why it works: The DP recurrence correctly counts arrangements on a single side by considering the two possibilities for each plot. Squaring the result is valid because the two sides are independent. Modular arithmetic ensures numbers do not overflow.

Python Solution

class Solution:
    def countHousePlacements(self, n: int) -> int:
        MOD = 10**9 + 7
        if n == 0:
            return 1
        
        prev2, prev1 = 1, 2  # dp[0] = 1, dp[1] = 2
        for _ in range(2, n + 1):
            current = (prev1 + prev2) % MOD
            prev2, prev1 = prev1, current
        
        return (prev1 * prev1) % MOD

This implementation first handles the base case n = 0. It uses two variables instead of a full DP array to save space. The loop computes the number of valid arrangements on one side, and the final return value squares it modulo 10^9 + 7 to account for both sides.

Go Solution

func countHousePlacements(n int) int {
    const MOD = 1000000007
    if n == 0 {
        return 1
    }
    
    prev2, prev1 := 1, 2
    for i := 2; i <= n; i++ {
        current := (prev1 + prev2) % MOD
        prev2, prev1 = prev1, current
    }
    
    return (prev1 * prev1) % MOD
}

The Go version is nearly identical to Python. We use const MOD and integer variables for the DP calculation. Go handles integer overflow by modular arithmetic, similar to Python. There is no need for slices since we only track the last two DP values.

Worked Examples

Example 1: n = 1

Step	prev2	prev1	current
Initial	1	2	-
Result	-	-	2 → (2*2) % MOD = 4

Output: 4

Example 2: n = 2

Step	prev2	prev1	current
Initial	1	2	-
i = 2	2	-	(2 + 1) % MOD = 3 → prev1 = 3, prev2 = 2
Result	-	-	(3*3) % MOD = 9

Output: 9

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single loop from 2 to n for DP computation
Space	O(1)	Only two variables needed for DP instead of full array

The optimal solution is efficient even for the upper limit of n = 10^4, because it avoids generating all possible configurations and only keeps the last two DP values.

Test Cases

# provided examples
assert Solution().countHousePlacements(1) == 4  # smallest n
assert Solution().countHousePlacements(2) == 9  # example with diagram

# additional tests
assert Solution().countHousePlacements(3) == 25  # small n > 2
assert Solution().countHousePlacements(4) == 64  # sequence continues
assert Solution().countHousePlacements(0) == 1  # edge case, no plots
assert Solution().countHousePlacements(10) == 20736  # larger n
assert Solution().countHousePlacements(1000) >= 1  # stress test

Test	Why
n = 1	Validates smallest non-zero input
n = 2	Checks correctness with diagram
n = 3, 4	Ensures DP sequence continues correctly
n = 0	Edge case of no plots
n = 10	Medium input to check growth
n = 1000	Stress test for large input

Edge Cases

1. n = 0: With zero plots, there is only one way (no houses). This could trip up naive implementations that assume n >= 1. Handled by a direct base case.
2. Maximum n = 10^4: Ensures that the solution scales. Using only two variables for DP ensures memory efficiency.
3. All houses empty vs all houses filled: The first and last plots can be empty or filled, testing boundary conditions. The DP recurrence naturally handles this without special casing.

This implementation handles all these edge cases efficiently and correctly.