Domino and Tromino Tiling - Practice Coding Problems

Domino and Tromino Tiling - Problem

Dynamic Programming Medium

You have two types of tiles:

A 2 × 1 domino shape
A tromino shape (L-shaped)

You may rotate these shapes. Given an integer n, return the number of ways to tile a 2 × n board. Since the answer may be very large, return it modulo 10⁹ + 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.

Input & Output

Example 1 — Basic Case

$ Input: n = 3

› Output: 5

💡 Note: There are 5 ways to tile a 2×3 board: (1) three vertical dominos, (2) one vertical + two horizontal, (3) two horizontal + one vertical, (4) two trominos, (5) different tromino arrangement

Example 2 — Minimum Case

$ Input: n = 1

› Output: 1

💡 Note: Only one way to tile a 2×1 board: place one vertical domino

Example 3 — Small Even

$ Input: n = 2

› Output: 2

💡 Note: Two ways to tile a 2×2 board: (1) two vertical dominos side by side, (2) two horizontal dominos stacked

Constraints

1 ≤ n ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Board dimensions: 2×n where n=3

Tiles

Two types: domino (1×2) and tromino (L-shaped)

Output

Count all possible ways to tile the board

Key Takeaway

🎯 Key Insight: Use DP with three states to track board coverage patterns efficiently

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to use dynamic programming with three states: fully covered board, board with top cell extending, and board with bottom cell extending. The optimal approach uses bottom-up DP with state transitions. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Recursion	O(3^n)	O(n)	Try all possible tile placements recursively without optimization
Dynamic Programming (Bottom-Up)	O(n)	O(1)	Build solution iteratively using state transitions and optimal substructure
Recursion with Memoization	O(n)	O(n)	Cache recursive results to avoid recalculating the same subproblems

Brute Force Recursion — Algorithm Steps

Try placing vertical domino at current position
Try placing horizontal dominos at current position
Try placing trominos in all orientations
Recursively solve for remaining board

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin with empty 2×n board

Try All Tiles

At each position, try vertical domino, horizontal dominos, and trominos

Recurse

For each placement, recursively solve remaining board

Code -

solution.c — C

#include <stdio.h>
#include <stdbool.h>

const int MOD = 1000000007;

long long countWays(int col, int n, bool topFilled, bool bottomFilled) {
    if (col == n) {
        return (!topFilled && !bottomFilled) ? 1 : 0;
    }
    if (col > n) {
        return 0;
    }
    
    long long ways = 0;
    
    if (topFilled && bottomFilled) {
        ways += countWays(col + 1, n, false, false);
    } else if (topFilled && !bottomFilled) {
        ways += countWays(col + 1, n, true, false);
        ways += countWays(col + 1, n, false, true);
    } else if (!topFilled && bottomFilled) {
        ways += countWays(col + 1, n, false, true);
        ways += countWays(col + 1, n, true, false);
    } else {
        ways += countWays(col + 1, n, false, false);
        ways += countWays(col + 1, n, false, false);
        ways += countWays(col + 1, n, true, true);
        ways += countWays(col + 1, n, true, true);
    }
    
    return ways % MOD;
}

int solution(int n) {
    return countWays(0, n, false, false);
}

int main() {
    int n;
    scanf("%d", &n);
    int result = solution(n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(3^n)

Each position has roughly 3 choices (vertical domino, horizontal pair, tromino), leading to exponential branches

✓ Linear Growth

Space Complexity

O(n)

Recursion depth is at most n levels deep

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler