790. Domino and Tromino Tiling LeetCode Solution

In this guide, you will get 790. Domino and Tromino Tiling LeetCode Solution with the best time and space complexity. The solution to Domino and Tromino Tiling problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Domino and Tromino Tiling solution in C++
4. Domino and Tromino Tiling solution in Java
5. Domino and Tromino Tiling solution in Python
6. Additional Resources

Problem Statement of Domino and Tromino Tiling

You have two types of tiles: a 2 x 1 domino shape and a tromino shape. You may rotate these shapes.

Given an integer n, return the number of ways to tile an 2 x n board. Since the answer may be very large, return it modulo 109 + 7.
In a tiling, every square must be covered by a tile. Two tilings are different if and only if there are two 4-directionally adjacent cells on the board such that exactly one of the tilings has both squares occupied by a tile.

Example 1:

Input: n = 3
Output: 5
Explanation: The five different ways are show above.

Example 2:

Input: n = 1
Output: 1

Constraints:

1 <= n <= 1000

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

790. Domino and Tromino Tiling LeetCode Solution in C++

class Solution {
 public:
  int numTilings(int n) {
    constexpr int kMod = 1'000'000'007;
    vector<long> dp(1001);
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 5;

    for (int i = 4; i <= n; ++i)
      dp[i] = (2 * dp[i - 1] + dp[i - 3]) % kMod;

    return dp[n];
  }
};
/* code provided by PROGIEZ */

790. Domino and Tromino Tiling LeetCode Solution in Java

class Solution {
  public int numTilings(int n) {
    final int kMod = 1_000_000_007;
    long[] dp = new long[1001];
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 5;

    for (int i = 4; i <= n; ++i)
      dp[i] = (2 * dp[i - 1] + dp[i - 3]) % kMod;

    return (int) dp[n];
  }
}
// code provided by PROGIEZ

790. Domino and Tromino Tiling LeetCode Solution in Python

class Solution:
  def numTilings(self, n: int) -> int:
    kMod = 1_000_000_007
    dp = [0, 1, 2, 5] + [0] * 997

    for i in range(4, n + 1):
      dp[i] = 2 * dp[i - 1] + dp[i - 3]

    return dp[n] % kMod
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.