algoadvance

Leetcode 790. Domino and Tromino Tiling

Problem Statement

The problem is taken from LeetCode (#790. Domino and Tromino Tiling):

You have two types of tiles: a 2x1 domino shape and an “L” tromino shape. You can rotate the tromino shape 90 degrees to form different orientations. You want to cover an N x 2 board using these tiles, such that every cell is covered exactly once.

Return the number of ways to tile the board. Since the answer may be very large, return it modulo 1e9+7.

Clarifying Questions

  1. What is the maximum value of (N)?
    • Typically, (1 \leq N \leq 1000).
  2. What should be done if the board cannot be filled with given tiles?
    • If it’s impossible, return 0.
  3. Are there any specific example input/output we can refer to?
    • Example 1:
      • Input: (N = 3)
      • Output: 5
    • Example 2:
      • Input: (N = 1)
      • Output: 1

Strategy

We’ll use dynamic programming to solve this problem. Let’s define dp[i] as the number of ways to fully cover a 2 x i board.

The recurrence relation depends on how you lay the tiles:

  1. Base Cases:
    • dp[0] = 1: There’s exactly one way to cover a 0-length board (doing nothing).
    • dp[1] = 1: There’s exactly one way to cover a 2 x 1 board (placing one vertical domino).
  2. For i ≥ 2:
    • Place a vertical domino in the last column, leaving a 2 x (i-1) section. This can be filled in dp[i-1] ways.
    • Place two horizontal dominos in the last two rows, leaving a 2 x (i-2) section. This can be filled in dp[i-2] ways.
    • Place one tromino in different configurations which guarantees filling up spaces of 3 columns.

Thus, the recurrence relation is: [ dp[i] = dp[i-1] + dp[i-2] + 2 \times (prefix_sum[i-3]) ] where prefix_sum[i] accumulates all sums previously to handle configurations covering earlier sections.

Code

#include <vector>
#include <iostream>
using namespace std;

class Solution {
public:
    int numTilings(int N) {
        if (N == 1) return 1;
        if (N == 2) return 2;
        
        const int MOD = 1000000007;
        
        vector<long> dp(N + 1, 0);
        dp[0] = 1;  // Base case: A 2x0 board can be covered in exactly 1 way - by doing nothing
        dp[1] = 1;  // Base case: A 2x1 board can be covered in exactly 1 way - by placing one vertical domino
        dp[2] = 2;  // Base case: A 2x2 board can be covered in exactly 2 ways - two vertical dominoes or two horizontal dominoes
        
        for (int i = 3; i <= N; ++i) {
            dp[i] = (dp[i-1] + dp[i-2] + 2 * dp[i-3]) % MOD;
        }
        
        return dp[N];
    }
};

int main() {
    Solution solution;
    cout << solution.numTilings(3) << endl;  // Output: 5
    return 0;
}

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI