LeetCode 2189 - Number of Ways to Build House of Cards

The problem is asking us to count the number of distinct ways to build a house of cards using exactly n cards. Each house consists of one or more rows of triangles formed by leaning two cards together, with horizontal cards placed between adjacent triangles.

leetcodemediummathdynamic-programming

LeetCode Problem 2189

Difficulty: 🟡 Medium
Topics: Math, Dynamic Programming

Solution

Problem Understanding

The problem is asking us to count the number of distinct ways to build a house of cards using exactly n cards. Each house consists of one or more rows of triangles formed by leaning two cards together, with horizontal cards placed between adjacent triangles. The rules enforce that higher rows of triangles must rest on horizontal cards from the row below, and triangles are placed from left to right in each row. Two houses are distinct if any row has a different number of cards in the two houses.

The input n is an integer between 1 and 500, which represents the total number of cards available. The output is the count of valid arrangements of all n cards. Small inputs like n = 2 or n = 4 are edge cases that test the minimum and infeasible constructions. The constraints indicate that a naive combinatorial approach may be too slow, requiring a dynamic programming or mathematical solution.

Important edge cases include n = 2 (minimum cards to form a single triangle), n = 4 (insufficient to form the next row), and larger values like n = 500 where efficiency matters.

Approaches

The brute-force approach would attempt to enumerate every possible combination of rows and triangles that could be formed with n cards. For each possible first row, you would recursively try all valid ways to build the remaining rows with the leftover cards. While this method would eventually yield the correct answer, it is computationally infeasible due to exponential growth in possibilities. With n up to 500, the recursion would take an astronomically long time.

The optimal approach relies on dynamic programming. The key observation is that the number of cards needed for a row of k triangles follows the formula row_cards = 3*k - 1 (two cards per triangle plus one horizontal card between each pair). The cumulative number of cards for a house with 1 + 2 + ... + h triangles per row forms a strictly increasing sequence. By using a 1D DP array where dp[i] counts the number of ways to build a house using exactly i cards, we iterate over each possible row size and update the DP array. This avoids redundant computations and efficiently calculates the answer for any n.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Recursive enumeration of all row combinations, too slow for n = 500
Dynamic Programming O(n * sqrt(n)) O(n) DP iterates over possible row sizes and card counts, efficient for n ≤ 500

Algorithm Walkthrough

  1. Compute the number of cards required for each row of triangles. For k triangles, a row requires 3*k - 1 cards. Generate all possible row sizes that can fit within n cards.
  2. Initialize a DP array dp of size n + 1 with all zeros. dp[i] will store the number of ways to build a house using exactly i cards.
  3. Set the base case dp[0] = 1, representing one way to build a house with zero cards (an empty structure).
  4. Iterate over each row size cards_needed. For each cards_needed, iterate backward from n down to cards_needed, updating dp[i] += dp[i - cards_needed]. This ensures each combination counts only once.
  5. After processing all row sizes, dp[n] contains the number of distinct houses using exactly n cards.
  6. Return dp[n] as the final result.

Why it works: Each row size corresponds to a valid row configuration. By iteratively building up from smaller numbers of cards, the DP ensures all combinations of rows that sum to n are counted exactly once. The backward iteration prevents overcounting scenarios where a row is reused multiple times in the same sum.

Python Solution

class Solution:
    def houseOfCards(self, n: int) -> int:
        # Precompute the number of cards needed for each row
        row_cards = []
        k = 1
        while True:
            cards_needed = 3 * k - 1
            if cards_needed > n:
                break
            row_cards.append(cards_needed)
            k += 1

        # Initialize DP array
        dp = [0] * (n + 1)
        dp[0] = 1  # Base case: 1 way to use 0 cards

        # Fill DP table
        for cards in row_cards:
            for i in range(n, cards - 1, -1):
                dp[i] += dp[i - cards]

        return dp[n]

The Python implementation first precomputes all possible row sizes, then uses a bottom-up dynamic programming approach to count combinations. Iterating backward ensures we only consider each row once per sum calculation.

Go Solution

func houseOfCards(n int) int {
    // Precompute row sizes
    rowCards := []int{}
    for k := 1; ; k++ {
        cardsNeeded := 3*k - 1
        if cardsNeeded > n {
            break
        }
        rowCards = append(rowCards, cardsNeeded)
    }

    // Initialize DP array
    dp := make([]int, n+1)
    dp[0] = 1

    // Fill DP table
    for _, cards := range rowCards {
        for i := n; i >= cards; i-- {
            dp[i] += dp[i-cards]
        }
    }

    return dp[n]
}

The Go version mirrors the Python solution, using slices and a backward iteration to fill the DP array. The logic is identical, with careful handling of slice indexing.

Worked Examples

Example 1: n = 16

Row sizes possible: [2, 5, 8, 11, 14]

i (cards) dp[i] updates
2 dp[2] = dp[0] + dp[2] = 1
5 dp[5] = dp[0] + dp[5] = 1, dp[7] = dp[2] + dp[7] = 1
8 dp[8] = dp[0] + dp[8] = 1, dp[10] = dp[2] + dp[10] = 1, dp[13] = dp[5] + dp[13] = 1, dp[16] = dp[8] + dp[16] = 1 + previous=1 => 2

dp[16] = 2, as expected.

Example 2: n = 2

Row sizes: [2]

dp[2] = dp[0] + dp[2] = 1

Output = 1

Example 3: n = 4

Row sizes: [2]

dp[4] = dp[2] + dp[4] = 1 + 0 = 1 but this uses fewer cards in the second row, so only valid constructions of full 4 cards are 0. Hence output = 0

Complexity Analysis

Measure Complexity Explanation
Time O(n * sqrt(n)) There are O(sqrt(n)) possible row sizes and we iterate over n for each row size
Space O(n) DP array of size n+1

The time complexity comes from iterating over each row size and updating the DP table, while space complexity is dominated by the DP array.

Test Cases

# Provided examples
assert Solution().houseOfCards(16) == 2  # multiple valid houses
assert Solution().houseOfCards(2) == 1   # single triangle
assert Solution().houseOfCards(4) == 0   # impossible to form valid house

# Boundary cases
assert Solution().houseOfCards(1) == 0   # not enough for one triangle
assert Solution().houseOfCards(500) > 0  # large number of cards, must compute efficiently

# Small cases
assert Solution().houseOfCards(5) == 1   # one row of 2 triangles + 1 horizontal
assert Solution().houseOfCards(8) == 1   # two rows: 2 triangles + 1 row of 1 triangle
Test Why
n=16 tests multiple-row valid combinations
n=2 tests minimum cards for one triangle
n=4 tests impossible constructions
n=1 tests insufficient cards
n=500 tests performance on upper boundary
n=5,8 tests small multi-row structures

Edge Cases

Edge Case 1: Minimum cards (n = 1)

A single card cannot form any triangle. The DP correctly returns 0 because no row size fits.

Edge Case 2: Exact one-row match (n = 2, n = 5, n = 8)

The algorithm correctly counts configurations where the total cards exactly match one or more rows. Backward iteration ensures proper accumulation.

Edge Case 3: Large n (n = 500)

The DP approach scales efficiently due to O(n * sqrt(n)) complexity, avoiding recursion or combinatorial explosion. All intermediate sums are tracked in the DP array without duplication.

This ensures correctness across the