Skip to main content
Talentd

Number of Ways to Build House of Cards - Solution & Explanation

MediumPremiumFree on FleetCodeMathDynamic Programming13 min readAsked at: Airbnb
Practice this problem

Problem Statement

You are given an integer n representing the number of playing cards you have. A house of cards meets the following conditions:

  • A house of cards consists of one or more rows of triangles and horizontal cards.
  • Triangles are created by leaning two cards against each other.
  • One card must be placed horizontally between all adjacent triangles in a row.
  • Any triangle on a row higher than the first must be placed on a horizontal card from the previous row.
  • Each triangle is placed in the leftmost available spot in the row.

Return the number of distinct house of cards you can build using all n cards. Two houses of cards are considered distinct if there exists a row where the two houses contain a different number of cards.

 

Example 1:

Input: n = 16
Output: 2
Explanation: The two valid houses of cards are shown.
The third house of cards in the diagram is not valid because the rightmost triangle on the top row is not placed on top of a horizontal card.

Example 2:

Input: n = 2
Output: 1
Explanation: The one valid house of cards is shown.

Example 3:

Input: n = 4
Output: 0
Explanation: The three houses of cards in the diagram are not valid.
The first house of cards needs a horizontal card placed between the two triangles.
The second house of cards uses 5 cards.
The third house of cards uses 2 cards.

 

Constraints:

  • 1 <= n <= 500

Approach Overview

Problem Overview: You are given n cards and must count how many distinct houses of cards you can build. Each level contains k card triangles and requires exactly 3k - 1 cards. Higher levels must use strictly fewer triangles than the level directly below.

The challenge is deciding how many triangles to place on each level while keeping the total number of cards ≤ n and maintaining the strictly decreasing structure.

Approach 1: Brute Force Recursive Search (Exponential Time, O(n) Space)

Try every possible number of triangles k for the current level. Each choice consumes 3k - 1 cards and recursively attempts to build the next level using fewer triangles. This explores all valid sequences of decreasing triangle counts. The approach is simple but inefficient because the same states (remaining cards and previous triangle limit) are recomputed many times. Time complexity grows exponentially with n, while recursion depth uses O(n) space in the worst case.

Approach 2: Memoization Search (Top-Down Dynamic Programming) (O(n²) Time, O(n²) Space)

Cache results for states defined by (remainingCards, prevTriangles). From a given state, iterate over possible triangle counts k where k < prevTriangles and 3k - 1 ≤ remainingCards. For each valid k, recursively compute ways to build the rest of the structure using remainingCards - (3k - 1). Memoization ensures each state is solved once, eliminating repeated work. This transforms the exponential recursion into a manageable dynamic programming solution with roughly O(n²) time and space complexity. The approach relies on recursion plus caching, a common technique in dynamic programming problems.

Approach 3: Bottom-Up Dynamic Programming (O(n²) Time, O(n) Space)

The same recurrence can be built iteratively. Treat each possible level size as a "group" with cost 3k - 1. Build a DP array where dp[c] represents the number of ways to use exactly c cards. Iterate through valid level sizes and update states while enforcing the strictly decreasing triangle constraint. This formulation avoids recursion and often reduces memory usage. The logic still depends on counting combinations of valid level sizes derived from the mathematical rule 3k - 1, making it a mix of math reasoning and dynamic programming.

Recommended for interviews: The memoized top-down DP is the most practical explanation during interviews. Start with the recursive idea to show understanding of the structure, then add caching to remove duplicate work. Interviewers expect you to recognize overlapping subproblems and convert the recursion into dynamic programming.

Solution

We notice that the number of cards in each layer is 3 times k + 2, and the number of cards in each layer is different. Therefore, the problem can be transformed into: how many ways can the integer n be expressed as the sum of numbers of the form 3 times k + 2. This is a classic knapsack problem that can be solved using memoization search.

We design a function dfs(n, k), which represents the number of ways to build different houses of cards when the remaining number of cards is n and the current layer is k. The answer is dfs(n, 0).

The execution logic of the function dfs(n, k) is as follows:

  • If 3 times k + 2 \gt n, then the current layer cannot place any cards, return 0;
  • If 3 times k + 2 = n, then the current layer can place cards, and after placing them, the entire house of cards is completed, return 1;
  • Otherwise, we can choose not to place cards or to place cards. If we choose not to place cards, the remaining number of cards does not change, and the number of layers increases by 1, i.e., dfs(n, k + 1). If we choose to place cards, the remaining number of cards decreases by 3 times k + 2, and the number of layers increases by 1, i.e., dfs(n - (3 times k + 2), k + 1). The sum of these two cases is the answer.

During the process, we can use memoization to avoid repeated calculations.

The time complexity is O(n^2), and the space complexity is O(n^2). Here, n is the number of cards.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force RecursionExponentialO(n)Conceptual starting point to understand level choices
Memoization (Top-Down DP)O(n²)O(n²)Best general solution; avoids recomputation and easy to implement
Bottom-Up Dynamic ProgrammingO(n²)O(n)When you prefer iterative DP and lower memory usage

Video Solution

How to Stack Playing Cards | WIRED • WIRED • 940,393 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Number of Ways to Build House of Cards easy or hard?
This problem is considered medium difficulty. The math behind the 3k-1 card requirement is straightforward, but recognizing the strictly decreasing level constraint and converting the recursion into dynamic programming requires solid DP experience.
Number of Ways to Build House of Cards Python/Java solution
Python, Java, C++, Go, and TypeScript implementations typically follow the same memoized DFS structure. The function recursively chooses triangle counts k where 3k-1 cards are required and caches results using a dictionary or array for O(n^2) complexity.
How to solve Number of Ways to Build House of Cards in O(n^2)?
Use a recursive DFS that chooses the number of triangles k for the current level, consuming 3k-1 cards. Store results in a memo table keyed by (remainingCards, previousTriangles). Each state iterates over valid k values only once, which keeps the overall complexity around O(n^2).
What is the best approach for Number of Ways to Build House of Cards?
The most practical solution uses memoization with top-down dynamic programming. Define a state using remaining cards and the maximum triangles allowed for the next level. Cache results so each state is computed once, reducing the complexity to about O(n^2) time and O(n^2) space.
Is Number of Ways to Build House of Cards asked at Google/Amazon/Meta?
Dynamic programming counting problems similar to this appear in interviews at companies like Google, Amazon, and Meta. While this exact problem may not always appear, the pattern of counting constrained structures with DP is very common in technical interviews.
What data structure is used in Number of Ways to Build House of Cards?
The solution mainly uses recursion combined with a memoization cache such as a hash map or 2D array. This cache stores results for previously computed states to avoid recomputation in the dynamic programming process.
What is the time complexity of Number of Ways to Build House of Cards?
The optimized dynamic programming solution runs in roughly O(n^2) time because for each remaining card count you iterate through possible triangle counts for the next level. Space complexity is O(n^2) when storing memoized states.

Ready to solve this problem?

Practice Number of Ways to Build House of Cards with our built-in code editor and test cases.

Practice on FleetCode
Previous

Champagne Tower