Number of Ways to Build House of Cards - Video Solutions
How to Stack Playing Cards | WIRED
Number of Ways to Build House of Cards - Video Solution
Watch 10 video solutions for Number of Ways to Build House of Cards, a medium level problem involving Math, Dynamic Programming. This walkthrough by WIRED has 940,393 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Recursion | Exponential | O(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 Programming | O(n²) | O(n) | When you prefer iterative DP and lower memory usage |