2320. Count Number of Ways to Place Houses


Problem Description

Imagine a street that has n plots on each side, making a total of n * 2 plots. The task is to determine the number of different ways to build houses on these plots with the constraint that no two houses can be adjacent to each other on the same side of the street. Interestingly, if a house is built on one side of a plot, it's still allowed to build another directly across from it on the other side of the street. The final answer to the number of ways to arrange houses should be provided modulo 10^9 + 7 to keep the numbers manageable, due to potentially large results for big values of n.

Intuition

The solution uses dynamic programming to solve the problem efficiently. To understand the intuition behind this approach, let's consider the subproblem of deciding whether to place a house on a plot. When you're considering a new plot, you have two choices: either to place a house on it or not. If you choose to place a house, the next plot cannot have a house because of the no-adjacent-houses rule. Conversely, if you choose not to place a house, you are free to place a house on the next plot.

We can define two states expressed as arrays f and g, where f[i] represents the number of ways to place houses up to plot i with a house on the ith plot, and g[i] represents the number of ways to place houses up to plot i without a house on the ith plot. These states are dependent on the previous states:

  • f[i] relies on g[i-1] since a house on plot i means the i-1th plot cannot have a house.
  • g[i] combines f[i-1] and g[i-1] because plot i being empty allows for either a house or no house on the i-1th plot.

The solution iterates through each plot, updating these states according to the rules established, and takes the modulo 10**9 + 7 to ensure the answer remains in the required bounds. With the values for the final plot calculated, the total number of house placements on one side of the street is the sum of f[-1] and g[-1].

Since the problem allows for independent house placement on either side of the street, the final answer is the square of this sum, again modulo 10**9 + 7, to account for all combinations on both sides of the street.

Learn more about Dynamic Programming patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

Solution Approach

The solution implements a form of dynamic programming, which is an optimization over plain recursion where subproblems are solved once and stored for future use, thus avoiding the recomputation of the same subproblems. The dynamic programming approach used here is tabulation, where we iteratively calculate and store the solution to each subproblem in a bottom-up fashion. In this case, the subproblems are the number of ways to place houses up to a certain plot without violating the "no adjacent houses" rule.

The code uses two lists, f and g, as mentioned before:

  • f is initialized with n elements, all set to 1, representing that there is initially one way to arrange a house on the ith plot. f[0] is always 1 because placing a house on the first plot obviously has no restrictions from previous plots.
  • g is also initialized with n elements, all set to 1, because at the beginning there is also one way to have a plot without a house on it.

The core logic of the problem is encapsulated in the for-loop:

  • f[i] is updated to g[i - 1]. This captures the idea that if there is a house on the ith plot, then there could not have been one on the i-1th plot, and the number of ways to reach this state is exactly the number of ways to reach plot i-1 without a house.

  • g[i] is updated to (f[i - 1] + g[i - 1]) % mod. Here, if the ith plot does not have a house, we are free to choose whether we had a house on the i-1th plot or not, and the total number of ways to arrange houses up to the ith plot is the sum of both possibilities.

After the loop ends, you have the total count of placements for a side street stored in f[n - 1] and g[n - 1]. Since we can combine any arrangement on one side of the street with any arrangement on the other side, the total number of arrangements is the square of the sum of f[n - 1] and g[n - 1]. This value is calculated as v * v % mod, where v is f[-1] + g[-1], and mod is 10**9 + 7.

This approach efficiently calculates the solution in O(n) time, as it only involves a single pass through the plots, and in O(n) space, due to the storage required for the f and g arrays.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which type of traversal does breadth first search do?

Example Walkthrough

Let's illustrate the solution approach with a street that has n = 3 plots on each side. Here's how we would use dynamic programming to find the count of all possible ways to build houses according to the given rules:

  1. We start by initializing the arrays f and g with 3 elements each, set to 1, since there's initially one way to have a house or not have a house on every plot. Hence, f = [1, 1, 1] and g = [1, 1, 1].

  2. Next, we iterate through the plots one by one and use the given relations to update f[i] and g[i].

  3. When i = 1 (second plot):

    • We update f[1] to g[0], which is 1, because if we put a house on the second plot, we can't have had a house on the first plot.
    • We update g[1] to (f[0] + g[0]) % mod, which is (1 + 1) % mod, resulting in 2, because if we don't put a house on the second plot, we could have either had a house or not had a house on the first plot.
  4. When i = 2 (third plot):

    • f[2] becomes g[1], which is 2, signifying that if we build on the third plot, we must not have built on the second.
    • g[2] becomes (f[1] + g[1]) % mod, which is (1 + 2) % mod, resulting in 3. This accounts for the scenarios where the second plot was either empty or had a house, affecting the possibilities for the third plot.
  5. Now f = [1, 1, 2] and g = [1, 2, 3].

  6. For the final count on one side of the street, we add the last elements of f and g, resulting in 2 + 3 = 5, meaning there are 5 unique ways to place houses along one side of a 3-plot street.

  7. For both sides of the street, we take this result and square it, giving us the final answer: 5 * 5 = 25. But we must remember to take modulo 10^9 + 7.

The calculations above simply illustrate the process. For different values of n, we would run the exact same process and compute the final count accordingly. Every step carefully abides by the rule of not allowing adjacent houses on the same side, while assuming both sides are independent, thus squaring the final sum before taking the modulo. This example demonstrates the solution approach for a small example where n is 3. The same principles apply for any value of n.

Solution Implementation

1class Solution:
2    def countHousePlacements(self, n: int) -> int:
3        # Define the modulo constant to handle large numbers.
4        MOD = 10**9 + 7
5
6        # f represents the count of ways to place houses such that
7        # the last plot is empty.
8        f = [1] * n
9      
10        # g represents the count of ways to place houses such that
11        # the last plot is occupied.
12        g = [1] * n
13
14        # Iterate over the plots starting from the second one.
15        for i in range(1, n):
16            # If the last plot is empty, then it must come after an occupied plot.
17            f[i] = g[i - 1]
18          
19            # If the last plot is occupied, it can come after either
20            # an empty plot or another occupied plot.
21            g[i] = (f[i - 1] + g[i - 1]) % MOD
22
23        # v is the total number of ways to place houses on the last plot.
24        v = f[-1] + g[-1]
25
26        # Since we can independently choose how to place houses on each side of the street,
27        # we square the number of ways to find the total combinations.
28        # We return the result modulo MOD to handle large numbers.
29        return (v * v) % MOD
30
1class Solution {
2    public int countHousePlacements(int n) {
3        final int MODULO = 1_000_000_007; // Define a constant for the modulo value
4        int[] place = new int[n]; // place[i] represents the number of ways to place houses up to position i without a house at position i
5        int[] noPlace = new int[n]; // noPlace[i] represents the number of ways to place houses up to position i with a house at position i
6      
7        // Base cases
8        place[0] = 1; // Only one way to not place a house at the first position
9        noPlace[0] = 1; // Only one way to place a house at the first position
10      
11        // Fill in the arrays using dynamic programming approach
12        for (int i = 1; i < n; ++i) {
13            place[i] = noPlace[i - 1]; // We can only place a house if the previous position has no house
14            noPlace[i] = (place[i - 1] + noPlace[i - 1]) % MODULO; // We can place a house if the previous position is either empty or occupied
15        }
16      
17        // Calculate the total number of ways for all positions
18        // After calculating for n-1 positions, we have to consider options for placement at the nth place hence (place[n - 1] + noPlace[n - 1])
19        // Since we are considering placements on two sides of the street, we need to square the value for one side to get the total combinations
20        long totalWays = (place[n - 1] + noPlace[n - 1]) % MODULO;
21      
22        // Return the total number of ways with modulo, ensuring we don't exceed integer limits
23        return (int) (totalWays * totalWays % MODULO);
24    }
25}
26
1class Solution {
2public:
3    int countHousePlacements(int n) {
4        // Initialize a constant MOD to use for modulo operation to avoid overflow
5        const int MOD = 1e9 + 7;
6      
7        // Create two arrays to hold the number of ways to place houses
8        // f represents number of ways when the last plot is empty
9        // g represents number of ways when the last plot has a house
10        // Initialize the first element as 1 since there's 1 way to place 0 houses 
11        int f[n + 1], g[n + 1];
12        f[0] = g[0] = 1;
13      
14        // Calculate the number of ways to place houses dynamically
15        for (int i = 1; i < n; ++i) {
16            f[i] = g[i - 1]; // If the current plot is empty, previous plot can either be empty or have a house
17            g[i] = (f[i - 1] + g[i - 1]) % MOD; // If the current plot has a house, previous plot must be empty
18        }
19      
20        // Calculate the final number of ways, considering both plots can be either empty or have a house
21        // Long is used here to avoid integer overflow due to squaring the value
22        long result = (f[n - 1] + g[n - 1]) % MOD;
23        result = (result * result) % MOD; // We square it because we calculate for both sides of the street
24
25        // Return the final result modulus MOD
26        return static_cast<int>(result);
27    }
28};
29
1// Function to count the number of ways to place houses in plots
2function countHousePlacements(n: number): number {
3    // Initialize two arrays to store intermediate values
4    const emptyPlotCounts = new Array(n);
5    const housePlotCounts = new Array(n);
6  
7    // Base case for the DP, 1 way to place on 0th index for both situations
8    // 'n' is a BigInt literal (ES2020+ feature)
9    emptyPlotCounts[0] = housePlotCounts[0] = 1n;
10  
11    // Define the modulo constant for the final result to prevent overflow
12    const mod = BigInt(10 ** 9 + 7);
13
14    // Populate both arrays using dynamic programming approach
15    for (let i = 1; i < n; ++i) {
16        // Count for the current plot being empty depends on the previous plot having a house
17        emptyPlotCounts[i] = housePlotCounts[i - 1];
18        // Count for the current plot having a house depends on the previous plot being either empty or having a house
19        housePlotCounts[i] = (emptyPlotCounts[i - 1] + housePlotCounts[i - 1]) % mod;
20    }
21  
22    // Calculate final value from both arrays, representing both placing or not placing a house on the last plot
23    const totalCount = emptyPlotCounts[n - 1] + housePlotCounts[n - 1];
24  
25    // Return the total number of ways squared modulo mod
26    // The square comes from calculating the same for both sides of the street
27    // We must cast BigInt result back to a number before returning
28    return Number(totalCount ** 2n % mod);
29}
30
Not Sure What to Study? Take the 2-min Quiz:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Time and Space Complexity

The given code snippet is designed to count the number of ways to place houses on a street with n plots, where houses cannot be placed on adjacent plots. This is solved using dynamic programming with two arrays f and g representing the number of ways to arrange houses with certain conditions.

Time Complexity:

To analyze the time complexity, we look at the operations inside the main loop:

  • The loop runs from 1 to n-1, which indicates O(n) iterations.
  • Inside the loop, the operations are constant-time; f[i] = g[i - 1] and g[i] = (f[i - 1] + g[i - 1]) % mod each take O(1).
  • Calculation of v and final return statement also takes O(1) time.

Therefore, the overall time complexity of the code is O(n).

Space Complexity:

For space complexity:

  • We are using two arrays f and g, each of size n, resulting in O(n) space.
  • The variables mod and v use constant space, O(1).

Hence, the space complexity of the code is O(n) due to the two arrays.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫