How do you solve Domino and Tromino Tiling on LeetCode?

Domino and Tromino Tiling (LeetCode #790) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Understanding how to break down the problem into smaller subproblems is crucial for dynamic programming.

What is the brute force solution for Domino and Tromino Tiling?

The brute force approach for Domino and Tromino Tiling is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves recursively trying to place tiles on the board in all possible configurations. This method explores every combination of placing dominoes and trominoes, leading to a large number of possibilities. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Domino and Tromino Tiling?

Domino and Tromino Tiling uses the following concepts: Dynamic Programming. The recommended patterns to study are: Dynamic Programming, Recursion, Memoization.

What are the interview tips for Domino and Tromino Tiling?

Always clarify the problem statement and constraints before diving into coding. Discuss your thought process and approach with the interviewer to get feedback. Practice explaining your code and reasoning clearly, as communication is key in interviews.

What are common mistakes when solving Domino and Tromino Tiling?

Failing to account for all possible tile placements, especially trominoes. Not using modulo operation correctly, leading to overflow errors.

#790

Domino and Tromino Tiling

Medium

Dynamic ProgrammingDynamic ProgrammingRecursionMemoization

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution uses dynamic programming to build up the number of ways to tile the board from smaller subproblems. This avoids redundant calculations and allows us to compute the result in linear time.

⚙️

Algorithm

4 steps

1Step 1: Create an array dp of size n+1 to store the number of ways to tile the board of length i.
2Step 2: Initialize dp[0] = 1, dp[1] = 1, dp[2] = 2 (base cases).
3Step 3: Iterate from 3 to n, calculating dp[i] as dp[i-1] + dp[i-2] + 2 * dp[i-3] (considering the placements of dominoes and trominoes).
4Step 4: Return dp[n] modulo 10^9 + 7.

solution.py9 lines

1# Full working Python code
2MOD = 10**9 + 7
3
4def numTilings(n):
5    dp = [0] * (n + 1)
6    dp[0], dp[1], dp[2] = 1, 1, 2
7    for i in range(3, n + 1):
8        dp[i] = (dp[i - 1] + dp[i - 2] + 2 * dp[i - 3]) % MOD
9    return dp[n]

ℹ

Complexity note: The time complexity is O(n) because we compute the number of ways to tile the board for each length from 3 to n once. The space complexity is O(n) due to the storage of results in the dp array.

1Understanding how to break down the problem into smaller subproblems is crucial for dynamic programming.
2Recognizing the base cases helps in building the solution iteratively.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.