Skip to main content
Talentd

Count Number of Ways to Place Houses - Solution & Explanation

MediumDynamic Programming24 min readAsked at: Amazon, Microsoft, Google +1
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You are given n plots on each side of a street. Each plot can either contain a house or remain empty, but adjacent plots on the same side cannot both contain houses. The task is to count the total number of valid placement configurations across both sides of the street.

The key observation: the two sides of the street are independent. First compute the number of valid arrangements for a single row of n plots with no two adjacent houses. Then square the result to account for both sides.

Approach 1: Dynamic Programming with Fibonacci Relation (Time: O(n), Space: O(n) or O(1))

For a single side of the street, this becomes the classic problem of counting binary strings of length n with no consecutive 1s. Let dp[i] represent the number of valid ways to arrange houses in the first i plots. If the current plot is empty, any valid arrangement of i-1 plots works. If the current plot contains a house, the previous plot must be empty, so the count comes from i-2. This gives the recurrence dp[i] = dp[i-1] + dp[i-2]. The sequence is identical to Fibonacci numbers. After computing the result for one side, square it to account for both sides. Use modulo 1e9+7 to avoid overflow.

This approach is straightforward and efficient. You iterate once from 1 to n, updating two previous states. With state compression, the space drops from O(n) to O(1). This method is commonly used in dynamic programming problems where the current state depends on a small number of previous states.

Approach 2: Matrix Exponentiation (Time: O(log n), Space: O(1))

The Fibonacci recurrence can be represented as a matrix transformation. The relation F(n) = F(n-1) + F(n-2) can be expressed using the matrix [[1,1],[1,0]]. Raising this matrix to the power n allows you to compute the result in logarithmic time using fast exponentiation.

Matrix exponentiation repeatedly squares the transition matrix while reducing the exponent by half each step. This reduces the complexity from linear to logarithmic time. After computing the Fibonacci value for one street side, square the result to get the total configurations across both sides.

This technique appears frequently in problems involving linear recurrences and is a standard optimization when n becomes very large. It is closely related to topics like matrix exponentiation and mathematical recurrence transformations.

Recommended for interviews: The dynamic programming approach with the Fibonacci relation is what most interviewers expect. It shows that you recognize the adjacency constraint and convert it into a recurrence. Matrix exponentiation demonstrates deeper algorithmic knowledge but is typically discussed as an optimization after presenting the DP solution.

Approach 1: Dynamic Programming with Fibonacci Relation

Identify the problem as a variation of the Fibonacci sequence solving adjacency constraints for house placement. Establish a dynamic programming relation where dp[i] defines the number of ways to arrange houses on i plots with no two adjacent.

Without losing generality, analyze one side of the street. For n plots, the problem becomes a classic non-adjacent placement problem, solvable by a Fibonacci-like approach. This leads to relation dp[i] = dp[i-1] + dp[i-2], since if the plot i is filled, plot i-1 can't be, and if plot i is not filled, it follows the i-1 arrangement.

Since both sides of the street are independent, compute the total ways considering both sides as the square of the computed dp[n] value modulo 10^9 + 7.

This C solution uses an iterative approach to calculate the number of arrangements using a Fibonacci-like sequence where prev and cur correspond to dp[i-2] and dp[i-1], respectively. The computation continues until the nth plot number, taking modulus 10^9+7 at every step to prevent overflow.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) - Iterates through n plots.

Space Complexity: O(1) - Uses constant space for calculations.

Try this approach in the editor →

Approach 2: Matrix Exponentiation

Another efficient method to solve this problem, especially for large values of n, is Matrix Exponentiation, which offers improved time complexity for Fibonacci-related sequence generation. The Fibonacci sequence or similar can be represented using matrix multiplication, allowing for efficient computation through exponentiation using binary methods.

This method uses matrix exponentiation to fast calculate the nth Fibonacci number, exploiting the property that Fibonacci sequences can be computed via matrix power with an initial base matrix. This reduces the problem of calculating dp[n] to logarithmic time via exponents.

Code

CC++JavaPythonJavaScript

C

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(log n) - Efficient due to matrix exponentiation

Space Complexity: O(1) apart from recursive call stack

Try this approach in the editor →

Approach 3: Dynamic Programming

Since the placement of houses on both sides of the street does not affect each other, we can consider the placement on one side only, and then square the number of ways for one side to get the final result modulo.

We define f[i] to represent the number of ways to place houses on the first i+1 plots, with the last plot having a house. We define g[i] to represent the number of ways to place houses on the first i+1 plots, with the last plot not having a house. Initially, f[0] = g[0] = 1.

When placing the (i+1)-th plot, there are two cases:

  • If the (i+1)-th plot has a house, then the i-th plot must not have a house, so the number of ways is f[i] = g[i-1];
  • If the (i+1)-th plot does not have a house, then the i-th plot can either have a house or not, so the number of ways is g[i] = f[i-1] + g[i-1].

Finally, we square f[n-1] + g[n-1] modulo to get the answer.

The time complexity is O(n), and the space complexity is O(n). Where n is the length of the street.

Code

PythonJavaC++GoTypeScriptC#

Python

Java

C++

Go

TypeScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming with Fibonacci Relation

Time Complexity: O(n) - Iterates through n plots.

Space Complexity: O(1) - Uses constant space for calculations.

Matrix Exponentiation

Time Complexity: O(log n) - Efficient due to matrix exponentiation

Space Complexity: O(1) apart from recursive call stack

Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming with Fibonacci RelationO(n)O(1) optimizedBest general solution. Simple recurrence and easy to implement in interviews.
Matrix ExponentiationO(log n)O(1)Useful when n is extremely large or when optimizing Fibonacci-style recurrences.

Video Solution

Weekly Contest 299 | Leetcode 2320 Count Number of Ways to Place Houses | DP | Fibonacci • Coding Decoded • 2,114 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Count Number of Ways to Place Houses easy or hard?
The problem is rated Medium because recognizing the Fibonacci recurrence is the main challenge. Once you identify that the arrangement constraint matches the classic no-consecutive-ones problem, the implementation becomes straightforward.
Count Number of Ways to Place Houses Python/Java solution
Both Python and Java implementations follow the same Fibonacci-style DP recurrence. Maintain two variables representing dp[i-1] and dp[i-2], update them while iterating to n, and square the final count to account for both sides. Always apply modulo 1e9+7 to keep values within integer limits.
How to solve Count Number of Ways to Place Houses in O(n)?
Treat each side of the street independently and count the number of binary arrangements of length n without consecutive 1s. Use the recurrence dp[i] = dp[i-1] + dp[i-2] with base cases dp[1] = 2 and dp[2] = 3. The result for one side is squared to include both sides of the street. Apply modulo 1e9+7 during calculations.
What is the best approach for Count Number of Ways to Place Houses?
Dynamic Programming using the Fibonacci recurrence is the most practical solution. For one side of the street, the number of valid placements follows dp[i] = dp[i-1] + dp[i-2]. After computing the result for n plots, square it to account for both sides. The solution runs in O(n) time and O(1) space with state compression.
Is Count Number of Ways to Place Houses asked at Google/Amazon/Meta?
Problems involving Fibonacci-style dynamic programming and adjacency constraints frequently appear in interviews at companies like Google, Amazon, and Meta. Variants often ask for counting valid arrangements or binary strings without consecutive elements.
What data structure is used in Count Number of Ways to Place Houses?
The solution mainly uses dynamic programming with simple integer variables or a small DP array. The recurrence only depends on the previous two states, so the implementation typically keeps two variables instead of a full array.
What is the time complexity of Count Number of Ways to Place Houses?
The standard dynamic programming solution runs in O(n) time because it iterates through all plots once while maintaining two previous states. Space complexity can be reduced to O(1). An optimized approach using matrix exponentiation computes the Fibonacci recurrence in O(log n) time.

Ready to solve this problem?

Practice Count Number of Ways to Place Houses with our built-in code editor and test cases.

Practice on FleetCode
Previous

Climbing Stairs

Next

House Robber