Count Number of Ways to Place Houses - Practice Coding Problems

Count Number of Ways to Place Houses - Problem

Dynamic Programming Medium

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 10⁹ + 7.

Note: If a house is placed on the i^th plot on one side of the street, a house can also be placed on the i^th plot on the other side of the street.

Input & Output

Example 1 — Small Street

$ Input: n = 2

› Output: 9

💡 Note: For each side with 2 plots, there are 3 ways: [], [1], [2]. Total combinations: 3 × 3 = 9 ways to arrange houses on both sides.

Example 2 — Single Plot

$ Input: n = 1

› Output: 4

💡 Note: For each side with 1 plot, there are 2 ways: place house or don't place. Total: 2 × 2 = 4 ways for both sides.

Example 3 — Larger Street

$ Input: n = 3

› Output: 25

💡 Note: For each side with 3 plots, there are 5 valid arrangements. Both sides independent: 5 × 5 = 25 total ways.

Constraints

1 ≤ n ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Street with n plots on each side (n=3)

Rule

No adjacent houses on same side allowed

Output

Count all valid arrangements (25 ways)

Key Takeaway

🎯 Key Insight: Each side follows Fibonacci pattern, both sides are independent - multiply the results

Asked in

G Google 25 a Amazon 20 M Microsoft 15 A Apple 12

The key insight is recognizing that each side follows a Fibonacci pattern and both sides are independent. The optimal approach uses space-optimized Fibonacci calculation with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Memoized Recursion	O(n)	O(n)	Add caching to avoid recomputing same subproblems
Dynamic Programming (Bottom-up)	O(n)	O(n)	Build solution iteratively using DP table
Brute Force Recursion	O(2ⁿ)	O(n)	Try all possible house placements recursively
Mathematical Formula (Fibonacci)	O(n)	O(1)	Recognize Fibonacci pattern and use space-optimized calculation

Memoized Recursion — Algorithm Steps

Step 1: Create memoization cache for (position, canPlace) states
Step 2: Check cache before computing, store results after
Step 3: Square the result for both sides of street

Visualization

Tap to expand

Step-by-Step Walkthrough

Cache

Store results of (position, canPlace) states

Lookup

Check cache before computing recursively

Reuse

Avoid redundant calculations, O(n) time

Code -

solution.c — C

#include <stdio.h>
#include <string.h>

const int MOD = 1000000007;
int N;
long long memo[1001][2]; // memo[pos][canPlace]
int visited[1001][2];

long long countWays(int pos, int canPlace) {
    if (pos > N) {
        return 1;
    }
    
    if (visited[pos][canPlace]) {
        return memo[pos][canPlace];
    }
    
    long long ways = 0;
    // Don't place house at current position
    ways += countWays(pos + 1, 1);
    
    // Place house at current position if allowed
    if (canPlace) {
        ways += countWays(pos + 1, 0);
    }
    
    ways %= MOD;
    memo[pos][canPlace] = ways;
    visited[pos][canPlace] = 1;
    return ways;
}

int solution(int n) {
    N = n;
    memset(visited, 0, sizeof(visited));
    
    // Count ways for one side
    long long oneSide = countWays(1, 1);
    
    // Both sides are independent, so multiply
    return (oneSide * oneSide) % MOD;
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", solution(n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each (position, canPlace) state computed once, 2n total states

✓ Linear Growth

Space Complexity

O(n)

Memoization table stores 2n states plus recursion stack

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~15 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Memoized Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler