What is the time complexity of Domino and Tromino Tiling?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Domino and Tromino Tiling?

This problem uses Dynamic Programming. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Domino and Tromino Tiling?

Insight 1: The number of ways to tile the board depends on the number of columns (n). We can define a recursive relationship to represent this. Insight 2: Dynamic programming is suitable because the problem has overlapping subproblems, meaning the number of ways to tile a smaller board contributes to the number of ways to tile a larger board.

Which companies ask LeetCode 790. Domino and Tromino Tiling in interviews?

This problem is frequently asked at WinZO.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Domino and Tromino Tiling - LeetCode 790 Solution

Domino and Tromino Tiling - Complete Solution Guide

Domino and Tromino Tiling is LeetCode problem 790, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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 10 9 + 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 Expla

Detailed Explanation

The problem asks us to calculate the number of ways to tile a 2 x n board using 2 x 1 dominoes and trominoes (L-shaped tiles). We need to return the answer modulo 10^9 + 7 because the number of ways can be very large. Two tilings are considered different if there are two adjacent cells where only one of the tilings has both squares occupied by a tile.

Solution Approach

The solution uses dynamic programming to calculate the number of ways to tile the 2 x n board. Instead of using a full array to store all intermediate results, it keeps track of only the last three values, d0, d1, and d2, which represent the number of ways to tile a 2 x (n-3), 2 x (n-2) and 2 x (n-1) board, respectively. It iterates from 3 to n, calculating the number of ways to tile a 2 x i board based on the previously calculated values using the recurrence relation: dp[i] = (2 * dp[i-1] + dp[i-3]) % MOD. The variables d0, d1, and d2 are updated iteratively to maintain the last three values.

Step-by-Step Algorithm

Step 1: Initialize variables d0, d1, and d2 to 1, 1, and 2 respectively. These correspond to the number of ways to tile a 2x0, 2x1 and 2x2 board.
Step 2: Handle the base cases where n is less than or equal to 2. In these cases, return n directly as the answer.
Step 3: Iterate from 3 to n. In each iteration:
Step 4: Calculate the current number of ways (current) as (2 * d2 + d0) % MOD. This follows from the recurrence relation derived from the possible ways to add tiles to the previous configurations.
Step 5: Update d0, d1, and d2 to d1, d2, and current respectively to maintain the last three values.
Step 6: After the loop finishes, return d2, which represents the number of ways to tile a 2 x n board.

Key Insights

Insight 1: The number of ways to tile the board depends on the number of columns (n). We can define a recursive relationship to represent this.
Insight 2: Dynamic programming is suitable because the problem has overlapping subproblems, meaning the number of ways to tile a smaller board contributes to the number of ways to tile a larger board.
Insight 3: We only need to store the results for the last three values of 'n' to compute the current value, allowing us to optimize space complexity to O(1).

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Dynamic Programming.

Companies

Asked at: WinZO.

Domino and Tromino Tiling | LeetCode 790

Medium

Dynamic Programming

Time: O(n)Space: O(1)

Solution Code

Available in:

class Solution {
    public int numTilings(int n) {
        int MOD = 1_000_000_007;

        if (n <= 2) {
            return n;
        }
        
        long d0 = 1, d1 = 1, d2 = 2;
        
        for (int i = 3; i <= n; i++) {
            long current = (2 * d2 + d0) % MOD;
            d0 = d1;
            d1 = d2;
            d2 = current;
        }
        
        return (int)d2;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 790: Domino and Tromino Tiling - Detailed explanation and solution approaches.

Topics

Dynamic Programming

Companies

WinZO

Stats

Difficulty:Medium

Languages:4

Companies:1

Problem #:790

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

6 steps

1
Step 1: Initialize variables d0, d1, and d2 to 1, 1, and 2 respectively. These correspond to the number of ways to tile a 2x0, 2x1 and 2x2 board.
2
Step 2: Handle the base cases where n is less than or equal to 2. In these cases, return n directly as the answer.
3
Step 3: Iterate from 3 to n. In each iteration:
4
Step 4: Calculate the current number of ways (current) as (2 * d2 + d0) % MOD. This follows from the recurrence relation derived from the possible ways to add tiles to the previous configurations.
5
Step 5: Update d0, d1, and d2 to d1, d2, and current respectively to maintain the last three values.
6
Step 6: After the loop finishes, return d2, which represents the number of ways to tile a 2 x n board.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The time complexity is O(n) because the solution iterates from 3 to n in a single loop. The space complexity is O(1) because the solution only uses a fixed number of variables (d0, d1, d2, current, MOD) regardless of the input size 'n'.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Matrix Exponentiation

The problem can also be solved using matrix exponentiation by expressing the recurrence relation in matrix form. This allows for faster computation when n is very large.

Time: O(log n)Space: O(1)

Trade-offs: Matrix exponentiation is faster for very large values of n but has a higher constant factor and is more complex to implement than the iterative dynamic programming approach. The iterative approach is simpler and more efficient for the constraint n <= 1000 given in the problem.

✨

Key Insights

1Insight 1: The number of ways to tile the board depends on the number of columns (n). We can define a recursive relationship to represent this.
2Insight 2: Dynamic programming is suitable because the problem has overlapping subproblems, meaning the number of ways to tile a smaller board contributes to the number of ways to tile a larger board.
3Insight 3: We only need to store the results for the last three values of 'n' to compute the current value, allowing us to optimize space complexity to O(1).

📚

Key Terms Explained

For Students

Dynamic Programming

Breaking complex problems into smaller subproblems and storing results.

Edge Cases

Edge case 1: n = 1 or n = 2. The solution correctly handles these base cases by returning n directly.
Edge case 2: Large values of n. The modulo operation ensures that the result does not overflow, preventing incorrect answers.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not applying the modulo operation. Without the modulo operation, the result will overflow for larger values of n, leading to incorrect answers.

✗Common mistake 2: Using incorrect recurrence relation. Carefully analyze the possible tiling configurations to derive the correct recurrence relation. A slight mistake here will lead to a wrong answer.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: This type of tiling problem can be applied to resource allocation where you have different types of resources and need to cover a specific area efficiently.

🏦Real-world scenario 2: In VLSI design, tiling problems arise when placing components on a chip to minimize the area occupied.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

Start with recursion, then memoize. The hardest part is identifying the state. Ask yourself: "What information do I need to make the current decision?"

🎯 Interview Tip

If stuck, try working through a small example by hand. The pattern often reveals itself.

⚠️ Watch Out

Forgetting base cases or initializing the DP array incorrectly. Start by solving the smallest subproblems.

👨‍💻 From Experience

This problem pattern appears frequently in real codebases. I've used similar logic when building production systems.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: August 10, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 13

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 6

❓

Frequently Asked Questions

How do I identify if a problem needs dynamic programming?

DP problems typically have: 1) Overlapping subproblems (same calculation repeated), 2) Optimal substructure (optimal solution uses optimal solutions to subproblems). Look for keywords like "minimum/maximum," "count ways," "is it possible," or "longest/shortest."

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Domino and Tromino Tiling"?

For this medium-level Dynamic Programming problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether standard techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?