Scale Engineer

Count Number of Ways to Place Houses

Med
#2114Time: 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.1 company
Patterns
Dynamic Programming
Companies
Nagarro

Prompt

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 <= 104

Approaches

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

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;    }}

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.

Trade-offs

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.

Solutions

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);    }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem