algoadvance

Leetcode 790. Domino and Tromino Tiling

Problem Statement

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

Given an integer n, return the number of ways to tile a 2 x n board with these two shapes. Since the answer may be large, return it modulo 10^9 + 7.

Example 1:

Input: n = 3
Output: 5
Explanation: The five different ways are shown below:
- O O -
  O O -
- O O O
  O - O
- O - O
  O O O
- - O O
  O O -
- O O -
  - O O

Example 2:

Input: n = 1
Output: 1

Constraints:

• 1 <= n <= 1000

Clarifying Questions

1. Q: Is n always a positive integer?
   • A: Yes, n is always a positive integer.
2. Q: Are there limitations on the size of the input beyond the constraint?
   • A: The input n is limited to 1000 as per the constraints provided.
3. Q: Can the board be partially filled in any configuration?
   • A: No, the board must be completely filled using the tiles.

Strategy

This is a dynamic programming (DP) problem. We need to find the number of ways to tile a 2 x n board, leveraging smaller subproblems. We can utilize the following observations:

1. Subproblem Definition: dp[i] represents the number of ways to fully cover a 2 x i board.

2. Base Cases:
   • dp[0] = 1 (an empty board)
   • dp[1] = 1 (only one way to place a single domino)
3. Recurrence Relation:
   • Consider placing the last tile(s):
     • Placing one vertical domino at the end (dp[n-1])
     • Placing two horizontal dominos one above the other (dp[n-2])
     • Additionally, considering the placement of trominoes in certain configurations.

We need to consider interactions when the board has positions that can match the tromino shapes. Let’s define additional states:

• dp[i]: The number of ways to cover a 2 x i board.
• dp[i] = dp[i-1] + dp[i-2] + 2 * sum(dp[0] to dp[i-3])

Adding a more detailed breakdown for our DP:

dp[i] += dp[i-3]
dp[i] += sum(dp[0 to i-3])

To optimize the implementation:

• We can maintain running sums to avoid repeated summation calculations.

Code

public class Solution {
    public static final int MOD = 1000000007;

    public int numTilings(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        
        long[] dp = new long[n+1];
        dp[0] = 1;  // There's one way to fill a 2x0 board
        dp[1] = 1;  // There's one way to fill a 2x1 board
        dp[2] = 2;  // There are two ways to fill a 2x2 board

        // Sum of dp[0 to i-3]
        long prevSum = 0;  

        for(int i = 2; i <= n; i++) {
            if (i >= 3) {
                prevSum += dp[i-3];
                prevSum %= MOD;
            }
            dp[i] = (dp[i-1] + dp[i-2] + 2 * prevSum) % MOD;
        }

        return (int) dp[n];
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        // Test with example cases
        System.out.println(solution.numTilings(3)); // Output: 5
        System.out.println(solution.numTilings(1)); // Output: 1
    }
}

Time Complexity

• Time Complexity: O(n) since we are iterating through the sequence to populate the DP array.
• Space Complexity: O(n) as we are storing results for each subproblem in the DP array.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?