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.

Description Hints 2 Solution

2189. Number of Ways to Build House of Cards

Medium60.2% acceptance1 companyPremium elsewhere, free here

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

Asked at 1 company

Airbnb

Topics

Dynamic Programming Math

Hints open one at a time

Hint 1

If a row has k triangles, how many cards does it take to build that row? It takes 3 * k - 1 cards.

Hint 2

If you still have i cards left, and on the previous row there were k triangles, what are the possible ways to build the current row? You can start at 1 triangle and continue adding more until you run out of cards or reach k - 1 triangles.

Still stuck?Read the written solution.

Open solution