LeetCode 2320: Count Number of Ways to Place Houses Solution

Master LeetCode problem 2320 (Count Number of Ways to Place Houses), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2320. Count Number of Ways to Place Houses

Medium

Dynamic Programming

Problem Explanation

Explanation:

To solve this problem, we can use dynamic programming. We need to consider two cases: placing a house on a plot and leaving the plot empty. We will maintain two arrays to track the number of ways to place houses on each side of the street without violating the constraint of adjacent houses. The number of ways to place houses on each side will depend on the number of ways to place houses on the previous plots.

Initialize two arrays dp1 and dp2 of size n+1 to track the number of ways to place houses on each side of the street.
Initialize dp1[1] and dp2[1] as 1, representing placing a house on the first plot on each side.
Loop through the plots from the second plot to the nth plot.
For each plot i, the number of ways to place a house on that plot is the sum of two scenarios: placing a house on the current plot and leaving the previous plot empty.
Update dp1[i] and dp2[i] based on the above scenarios.
Finally, return the total number of ways to place houses on both sides.

Time Complexity: O(n) Space Complexity: O(n)

Solution Code

class Solution {
    public int numWays(int n) {
        int MOD = 1000000007;
        long[] dp1 = new long[n + 1];
        long[] dp2 = new long[n + 1];
        dp1[1] = 1;
        dp2[1] = 1;
        
        for (int i = 2; i <= n; i++) {
            dp1[i] = (dp1[i - 1] + dp2[i - 1]) % MOD;
            dp2[i] = dp1[i - 1];
        }
        
        long total = (dp1[n] + dp2[n]) % MOD;
        return (int)total;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2320 (Count Number of Ways to Place Houses)?

This page provides optimized solutions for LeetCode problem 2320 (Count Number of Ways to Place Houses) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2320 (Count Number of Ways to Place Houses)?

The time complexity for LeetCode 2320 (Count Number of Ways to Place Houses) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2320 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2320 in Java, C++, or Python.

Back to LeetCode Solutions