Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Domino and Tromino Tiling solution and explanation

MediumDynamic Programming7 min read51.4% acceptanceUpdated 9 Apr 2026
Asked atGoogleAmazonMicrosoftMetaBloomberg
Practise Domino and Tromino Tiling
16:16
Tiling Dominoes and Trominoes (Leetcode 790) | Dynamic ProgrammingWilliamFiset · 16:16 · 47K viewsWatch on YouTube
9 more videos on this problem
  1. Tiling Dominoes and Trominoes (Leetcode 790) | Dynamic ProgrammingWilliamFiset · 16:16 · 47K views
  2. Domino and Tromino Tiling | Detailed Explanations | Leetcode 790 | codestorywithMIKcodestorywithMIK · 43:02 · 28K views
  3. Domino and Tromino Tiling | Leetcode 790 | Dynamic ProgrammingAyushi Sharma · 11:06 · 20K views
  4. 花花酱 LeetCode 790. Domino and Tromino Tiling - 刷题找工作 EP171Hua Hua · 15:58 · 9K views
  5. Leetcode 790. Domino and Tromino TilingElite Code · 29:58 · 5K views
  6. Domino and Tromino Tiling | Leetcode 790Techdose · 37:48 · 5K views
  7. Daily Leetcode #998: Dec 24, 2022 - 790. Domino and Tromino TilingProgramming Live with Larry · 16:48 · 3K views
  8. Domino and Tromino Tiling | LeetCode 790 | Dynamic ProgramingRoy Rodriguez · 7:51 · 2K views
  9. Domino and Tromino Tiling - Leetcode 790 - PythonTim Huang · 5:33 · 1K views
  10. Daily Leetcode #1861: May 05, 2025 - 790. Domino and Tromino TilingProgramming Live with Larry · 11:26 · 865 views

The problem

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

Approach overview

Problem Overview: Given a 2 x n board, count the number of ways to completely tile it using dominoes (2x1 or 1x2) and L-shaped trominoes. The challenge is handling partial shapes created by tromino placements and counting all valid tilings efficiently.

Approach 1: Dynamic Programming Recurrence (O(n) time, O(1) space)

This problem becomes manageable once you observe how the board grows from smaller widths. Let dp[i] represent the number of ways to tile a 2 x i board. Domino placements extend the board by one column, while tromino placements create configurations that connect across multiple columns. Careful enumeration of these transitions leads to the recurrence dp[i] = 2 * dp[i-1] + dp[i-3]. The intuition: one vertical domino extends dp[i-1], horizontal domino pairs or mirrored tromino shapes contribute additional combinations. Iterate from 1..n while storing only the last three states, reducing memory to constant space. This technique is a classic use of dynamic programming where each state builds directly from smaller solved subproblems.

Approach 2: Matrix Exponentiation (O(log n) time, O(1) space)

The recurrence dp[i] = 2*dp[i-1] + dp[i-3] is linear, which means it can be expressed as a matrix transition. By representing the state vector as [dp[i], dp[i-1], dp[i-2]], you can construct a fixed 3x3 transformation matrix that advances the sequence by one step. Raising this matrix to the (n-2) power using fast exponentiation computes the result in logarithmic time. Each multiplication combines previous tiling counts according to the recurrence relation. This approach relies on matrix exponentiation to accelerate linear recurrences and is useful when n becomes extremely large.

Recommended for interviews: The dynamic programming recurrence is what most interviewers expect. It demonstrates that you can analyze tile placements, derive a recurrence, and implement an efficient O(n) solution with constant memory. Matrix exponentiation is rarely required during interviews but shows deeper understanding of linear recurrences and optimization techniques often discussed in advanced dynamic programming problems.

Approach 1: Dynamic Programming Approach

This problem can be solved using dynamic programming by considering the number of ways to tile smaller sections of the board and building up to solve for larger sections.

Define a DP array where dp[i] represents the number of ways to tile a 2 x i board.

The recurrence relation involves using domino and tromino tiles: 

dp[i] = dp[i-1] + dp[i-2] + 2 * sum[dp[j-2] for j in 3 to i]

This relation stems from the ways to construct tilings using the previous configurations.

class Solution:
    def numTilings(self, n: int) -> int:
        MOD = 1000000007
        if n < 3:
            return n
        dp = [0] * (n + 1)
        dp[0], dp[1], dp[2] = 1, 1, 2
        for i in range(3, n + 1):
            dp[i] = (2 * dp[i - 1] + dp[i - 3]) % MOD
        return dp[n]
public class Solution {
    public int numTilings(int n) {
        final int MOD = 1000000007;
        if (n < 3) return n;
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = (2 * dp[i - 1] % MOD + dp[i - 3] % MOD) % MOD;
        }
        return dp[n];
    }
}
#include <vector>
using namespace std;

class Solution {
public:
    int numTilings(int n) {
        const int MOD = 1000000007;
        if (n < 3) return n;
        vector<int> dp(n + 1);
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = ((2LL * dp[i - 1] % MOD) + dp[i - 3] % MOD) % MOD;
        }
        return dp[n];
    }
};
var numTilings = function(n) {
    const MOD = 1000000007;
    if (n < 3) return n;
    let dp = new Array(n + 1).fill(0);
    dp[0] = 1;
    dp[1] = 1;
    dp[2] = 2;
    for (let i = 3; i <= n; i++) {
        dp[i] = (2 * dp[i - 1] + dp[i - 3]) % MOD;
    }
    return dp[n];
};
#include <stdio.h>
#define MOD 1000000007

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

int main() {
    int n = 3;
    printf("%d\n", numTilings(n));
    return 0;
}
public class Solution {
    public int NumTilings(int n) {
        const int MOD = 1000000007;
        if (n < 3) return n;
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = (2 * dp[i - 1] % MOD + dp[i - 3] % MOD) % MOD;
        }
        return dp[n];
    }
}

This Python solution uses a list dp to implement the dynamic programming approach, iterating to compute the number of ways to place tiles for each board size from 1 to n.

Complexity

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

Try this approach in the editor

Approach 2: Matrix Exponentiation Approach

This solution uses matrix exponentiation to derive the result by considering the recurrence relation characteristic equation derived earlier. This approach is efficient for large n due to the optimization from reducing the problem to matrix multiplications.

class Solution:
    def numTilings(self, n: int) -> int:
        MOD = 1000000007

        def multiply(A, B):
            return [[sum(x * y for x, y in zip(A_row, B_col)) % MOD for B_col in zip(*B)] for A_row in A]

        def matrixExponentiation(A, n):
            result = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
            while n:
                if n % 2:
                    result = multiply(result, A)
                A = multiply(A, A)
                n //= 2
            return result

        if n < 3:
            return n
        T = [[0, 1, 0], [1, 1, 1], [0, 1, 0]]
        res = matrixExponentiation(T, n-2)
        return (res[1][0] + res[1][1] * 2 + res[1][2]) % MOD
public class Solution {
    final int MOD = 1000000007;

    private long[][] multiply(long[][] A, long[][] B) {
        long[][] C = new long[3][3];
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
                for (int k = 0; k < 3; k++)
                    C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
        return C;
    }

    private long[][] matrixExponentiation(long[][] A, int n) {
        long[][] result = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
        while (n > 0) {
            if (n % 2 == 1) result = multiply(result, A);
            A = multiply(A, A);
            n /= 2;
        }
        return result;
    }

    public int numTilings(int n) {
        if (n < 3) return n;
        long[][] T = {{0, 1, 0}, {1, 1, 1}, {0, 1, 0}};
        long[][] res = matrixExponentiation(T, n - 2);
        return (int)((res[1][0] + res[1][1] * 2 + res[1][2]) % MOD);
    }
}
#include <vector>
using namespace std;

const int MOD = 1000000007;

class Solution {
    vector<vector<long long>> multiply(vector<vector<long long>>& A, vector<vector<long long>>& B) {
        vector<vector<long long>> C(3, vector<long long>(3));
        for (int i = 0; i < 3; ++i)
            for (int j = 0; j < 3; ++j)
                for (int k = 0; k < 3; ++k)
                    C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
        return C;
    }

    vector<vector<long long>> matrixExponentiation(vector<vector<long long>>& A, int n) {
        vector<vector<long long>> result = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};  // Identity matrix
        while (n) {
            if (n % 2 == 1) result = multiply(result, A);
            A = multiply(A, A);
            n /= 2;
        }
        return result;
    }

public:
    int numTilings(int n) {
        if (n < 3) return n;
        vector<vector<long long>> T = {{0, 1, 0}, {1, 1, 1}, {0, 1, 0}};
        vector<vector<long long>> res = matrixExponentiation(T, n-2);
        return ((1LL * res[1][0] + res[1][1] * 2 + res[1][2]) % MOD) % MOD;
    }
};

Utilizing transform matrices, the Python solution applies fast matrix exponentiation to reduce computational cost, describing the recurrence relation succinctly with the transition matrix.

Complexity

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

Try this approach in the editor

Approach 3: Dynamic Programming

First, we need to understand the problem. The problem is essentially asking us to find the number of ways to tile a 2 times n board, where each square on the board can only be covered by one tile.

There are two types of tiles: 2 x 1 and L shapes, and both types of tiles can be rotated. We denote the rotated tiles as 1 x 2 and L' shapes.

We define f[i][j] to represent the number of ways to tile the first 2 times i board, where j represents the state of the last column. The last column has 4 states:

  • The last column is fully covered, denoted as 0
  • The last column has only the top square covered, denoted as 1
  • The last column has only the bottom square covered, denoted as 2
  • The last column is not covered, denoted as 3

The answer is f[n][0]. Initially, f[0][0] = 1 and the rest f[0][j] = 0.

We consider tiling up to the i-th column and look at the state transition equations:

When j = 0, the last column is fully covered. It can be transitioned from the previous column's states 0, 1, 2, 3 by placing the corresponding tiles, i.e., f[i-1][0] with a 1 x 2 tile, f[i-1][1] with an L' tile, f[i-1][2] with an L' tile, or f[i-1][3] with two 2 x 1 tiles. Therefore, f[i][0] = sum_{j=0}^3 f[i-1][j].

When j = 1, the last column has only the top square covered. It can be transitioned from the previous column's states 2, 3 by placing a 2 x 1 tile or an L tile. Therefore, f[i][1] = f[i-1][2] + f[i-1][3].

When j = 2, the last column has only the bottom square covered. It can be transitioned from the previous column's states 1, 3 by placing a 2 x 1 tile or an L' tile. Therefore, f[i][2] = f[i-1][1] + f[i-1][3].

When j = 3, the last column is not covered. It can be transitioned from the previous column's state 0. Therefore, f[i][3] = f[i-1][0].

We can see that the state transition equations only involve the previous column's states, so we can use a rolling array to optimize the space complexity.

Note that the values of the states can be very large, so we need to take modulo 10^9 + 7.

The time complexity is O(n), and the space complexity is O(1). Where n is the number of columns of the board.

function numTilings(n: number): number {
    const mod = 1_000_000_007;
    let f: number[] = [1, 0, 0, 0];

    for (let i = 1; i <= n; ++i) {
        const g: number[] = Array(4);
        g[0] = (f[0] + f[1] + f[2] + f[3]) % mod;
        g[1] = (f[2] + f[3]) % mod;
        g[2] = (f[1] + f[3]) % mod;
        g[3] = f[0] % mod;
        f = g;
    }

    return f[0];
}
func numTilings(n int) int {
	f := [4]int{}
	f[0] = 1
	const mod int = 1e9 + 7
	for i := 1; i <= n; i++ {
		g := [4]int{}
		g[0] = (f[0] + f[1] + f[2] + f[3]) % mod
		g[1] = (f[2] + f[3]) % mod
		g[2] = (f[1] + f[3]) % mod
		g[3] = f[0]
		f = g
	}
	return f[0]
}
impl Solution {
    pub fn num_tilings(n: i32) -> i32 {
        const MOD: i64 = 1_000_000_007;
        let mut f: [i64; 4] = [1, 0, 0, 0];
        for _ in 1..=n {
            let mut g = [0i64; 4];
            g[0] = (f[0] + f[1] + f[2] + f[3]) % MOD;
            g[1] = (f[2] + f[3]) % MOD;
            g[2] = (f[1] + f[3]) % MOD;
            g[3] = f[0] % MOD;
            f = g;
        }
        f[0] as i32
    }
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Dynamic Programming Approach

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

Matrix Exponentiation Approach

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

Dynamic Programming–

Complexity analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming RecurrenceO(n)O(1)Standard solution for interview settings and typical constraints
Matrix ExponentiationO(log n)O(1)Useful when n is extremely large and recurrence can be expressed as matrix transitions

Frequently asked questions

Is Domino and Tromino Tiling easy or hard?

This problem is generally rated Medium difficulty. The implementation is simple once the recurrence is known, but deriving the correct transition from domino and tromino placements requires careful reasoning.

Domino and Tromino Tiling Python/Java solution

Python, Java, C++, C#, and JavaScript implementations typically follow the same recurrence dp[i] = 2*dp[i-1] + dp[i-3]. Use a loop to build the sequence and apply modulo 1e9+7 to prevent overflow when n becomes large.

How to solve Domino and Tromino Tiling in O(n)?

Use a DP recurrence where dp[i] represents tilings of a 2 x i board. Analyze how dominoes and L-shaped trominoes extend smaller boards and derive dp[i] = 2*dp[i-1] + dp[i-3]. Initialize base cases and iterate forward while applying modulo arithmetic if required.

What is the best approach for Domino and Tromino Tiling?

Dynamic programming is the most practical approach. Define dp[i] as the number of ways to tile a 2 x i board and derive the recurrence dp[i] = 2*dp[i-1] + dp[i-3]. This computes the result in O(n) time with O(1) space by storing only the last few states.

Is Domino and Tromino Tiling asked at Google/Amazon/Meta?

Variants of tiling and recurrence-based dynamic programming problems frequently appear in interviews at companies like Google, Amazon, and Meta. They test pattern recognition, recurrence derivation, and space optimization techniques.

What data structure is used in Domino and Tromino Tiling?

The solution primarily uses dynamic programming with either an array or a few rolling variables to store previous states. No complex data structures are required beyond integer storage for the recurrence values.

What is the time complexity of Domino and Tromino Tiling?

The standard dynamic programming solution runs in O(n) time because it iterates from 1 to n while computing each state once. Space can be reduced to O(1) by keeping only the previous three values required for the recurrence.

Comments

Now write it yourselfClose this page and solve Domino and Tromino Tiling in the editor, without looking.
Practise Domino and Tromino Tiling