790. Domino and Tromino Tiling

Hello, reader 👋🏽 ! Welcome to day 84 of the series on Problem Solving. Through this series, I aim to pick up at least one question every day and share my approach to solving it.

Today, I will be picking up LeetCode's daily challenge problem: 790. Domino and Tromino Tiling.

🤔 Problem Statement

You have two types of tiles: a 2 x 1 domino shape and a tromino shape and they can be rotated.
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<sup>9</sup> + 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.
E.g.:
- n=1 => 1
- n=3 => 5

💬 Thought Process - Brute Force

This is a dynamic programming problem where we will have to try out all the possible ways of placing the given two tiles: domino and tromino, and return the total ways.
But we do need to find out some way to represent and figure out ways to place tiles.
Let's first focus on placing domino tiles. We'll take care of ways to place one tile both horizontally and vertically.
- Look at the image below that places domino tile horizontally and vertically

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1671893153761/af204523-75a5-4bae-a3a0-ea47553dc04b.png align="center")

Hence, placing a domino tile would have two options and our subproblem reduces to

f(n) = f(n-1) + f(n-2)

What about tromino? Well tromino is the trickiest part.
Before I explain ways to place tromino tiles, let's look at the possible orientations:
Symmetrically, if we place trominoes in any of the above orientations the subproblems left to solve would be the same.
- That is either the top or bottom row with an extra square
Now that we have looked into the possible orientations, let's see the ways that we can actually place these tiles.
Again, we'll try to place one tromino tile and look at the possible ways to fill the remaning board.
We are done with the main function, but what of g(n)? We don't know how this is defined.
Let's try to find how to define g(n) by building from the previous problem where we placed 1 tromino tile.

Hence, our final equations boil down to this:

  f(n) = f(n-1) + f(n-2) + 2 * g(n-2)
  g(n) = f(n-1) + g(n-1)

Now for the base cases:
- for f the base cases would be:
  - f(0) the number of ways to tile are 0
  - f(1) the number of ways to tile are 1
  - f(2) the number of ways to tile are 2
- for g the base cases would be:
  - g(0) the number of ways are 0
  - g(1) the number of ways are 1
    - Why? Well let's visualise how g(1) would look like on the board:
    - This is becasuse as stated earlier, g(n) would have columns in one row and the other row with n+1 columns.

Hence, the final solution would be:

```java class Solution {

  int mod = (int) (1e9 + 7);
  public int numTilings(int n) {
      return (int) numTilingsHelper(n) % mod;
  }

  private long numTilingsHelper(int n) {
      if(n <= 0) return 0l;
      if(n <= 2) return n;

        // f(n-1) + f(n-2) + 2*g(n-2)
        long vert = numTilingsHelper(n-1) % mod;
        long hor = numTilingsHelper(n-2) % mod;
        long tro = numTilingsTromino(n-2) % mod;

        return (vert + hor + 2 * tro) % mod;
    }

    private long numTilingsTromino(int n) {
        if(n <= 0) return 0l;
        if(n == 1) return 1l;

        // g(n) = g(n-1) + f(n-1)
        long hor = numTilingsTromino(n-1) % mod;
        long tro = numTilingsHelper(n-1) % mod;

        return (hor + tro) % mod;
    }
}
```

Now, we cannot simply use this as the final solution because we have multiple sub problems. The worst time complexity would be O(3^N).
We can do better and it's not very diffiult to see that there are going to be subproblems.
Also note how we are using long instead of int here as return values. This is necessary since we could be dealing with numbers outside of int range.

💬 Thought Process - Memoization

There is only one dependent state: n. But we would require two different arrays to cache values. One to solve and cache sub-problems for f(n) and the other to cache and solve sub-problems for g(n).

👩🏽‍💻 Solution - Memoization

class Solution {
    int mod = (int) (1e9 + 7);
    long[] memo, tromino;
    public int numTilings(int n) {
        memo = new long[n+1];
        tromino = new long[n+1];

        Arrays.fill(memo, -1);
        Arrays.fill(tromino, -1);

        return (int) numTilingsHelper(n) % mod;
    }

    private long numTilingsHelper(int n) {
        if(n <= 0) return 0l;
        if(n <= 2) return n;

        if(memo[n] != -1) return memo[n] % mod;

        // f(n-1) + f(n-2) + 2*g(n-2)
        long verticalTile = numTilingsHelper(n-1) % mod;
        long horizontalTile = numTilingsHelper(n-2) % mod;
        long trominoTile = numTilingsTromino(n-2) % mod;

        return memo[n] = (verticalTile + horizontalTile + 
                          2 * trominoTile) % mod;
    }

    private long numTilingsTromino(int n) {
        if(n <= 0) return 0l;
        if(n == 1) return 1l;

        if(tromino[n] != -1) return tromino[n];

        // g(n) = g(n-1) + f(n-1)
        long horizontalTile = numTilingsTromino(n-1) % mod;
        long trominoTile = numTilingsHelper(n-1) % mod;

        return tromino[n] = (horizontalTile + trominoTile) % mod;
    }
}

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

💬 Thought Process - Tabulation

We can convert the above solution to tabulation. Instead of recursive calls, we can use loops to calculate for the current value of n using previous solved sub-problems.

👩🏽‍💻 Solution - Tabulation

class Solution {
    int mod = (int) (1e9 + 7);
    public int numTilings(int n) {
        if(n == 0) return 0;
        if(n <= 2) return n;

        long[] dp = new long[n+1];
        long[] tromino = new long[n+1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        tromino[0] = 0;
        tromino[1] = 1;
        tromino[2] = 2;

        for(int i = 3; i<=n; i++) {
            dp[i] = (dp[i-1] + dp[i-2] + 2 * tromino[i-2]) % mod;
            tromino[i] = (tromino[i-1] + dp[i-1]) % mod;
        }

        return (int) dp[n];
    }
}

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

💬 Thought Process - Space Optimization

We need only the answers to the two previous sub-problem for f(i) and one previous sub-problem for g(i).
Hence we can use variables and keep updating them instead of using an entire array.
We'll call the previous two states of the main sub-problem f() as firstTiling and secondTiling.
For the tromino tiling sub-problem, let's call the first and second state as firstTromino and secondTromino.
Each time we solve a sub-problem, we'll update firstTiling to the value of secondTiling and secondTilingto the value of the current answer of sub-problem.
Similarly, each time we solve a sub-problem for the tromino tiling case, we'll update firstTromino to the value of secondTromino and the secondTromino to the value of the current answer of sub-problem.
Finally, we can return the answer in the secondTiling variable.

👩🏽‍💻 Solution - Space Optimization

class Solution {
    int mod = (int) (1e9 + 7);
    public int numTilings(int n) {
        if(n == 0) return 0;
        if(n <= 2) return n;

        long firstTiling = 1;
        long secondTiling = 2;

        long firstTromino = 1;
        long secondTromino = 2;

        for(int i = 3; i<=n; i++) {
            long currentTiling = (firstTiling + secondTiling + 
                                  2 * firstTromino) % mod;
            long currentTromino = (secondTromino + secondTiling) % mod;

            firstTiling = secondTiling;
            secondTiling = currentTiling;

            firstTromino = secondTromino;
            secondTromino = currentTromino;
        }

        return (int) secondTiling;
    }
}

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

💬 Thought Process - Breaking down the equation

So far, our equations are as follows:

  f(n) = f(n-1) + f(n-2) + 2 * g(n-2) --- #1
  g(n) = f(n-1) + g(n-1) --- #2

Turns out, this could further be shortened to avoid the extra g(n) variable function.
We'll understand how this works.
Before that let's see what the value of g(n-2) would be:
```
  g(n-2) = f(n-3) + g(n-3)
```

Using the above equation in the #1 we get:

  f(n) = f(n-1) + f(n-2) + f(n-3) + g(n-3) + f(n-3) + g(n-3)

This can be regrouped as:

  f(n) = f(n-1) + f(n-3) + [f(n-2) + f(n-3) + g(n-3) + g(n-3)]

The equation: f(n-2) + f(n-3) + g(n-3) + g(n-3) is basically the value of f(n-1)

Hence, we arrive at:

  f(n) = f(n-1) + f(n-3) + f(n-1)
  f(n) = 2 * f(n-1) + f(n-3)

Hence, we'll use three variables: firstTiling, secondTiling and thirdTiling. Initially, firstTiling will be equal to f(1) => 1, secondTiling will be equal to f(2) => 2, and thirdTiling will be equal to f(3) => 5.
We'll loop from n=4 to calculate future sub-probllems and finally return the value in thirdTiling.

👩🏽‍💻 Solution - Breaking down the equation

class Solution {
    int mod = (int) (1e9 + 7);
    public int numTilings(int n) {
        if(n == 0) return 0;
        if(n <= 2) return n;

        long firstTiling = 1; // f(1) 
        long secondTiling = 2; // f(2)
        long thirdTiling = 5; // f(3)


        for(int i = 4; i<=n; i++) {
            // 2 * n-1 + n-3
            long currentTiling = ((2 * thirdTiling) + firstTiling) % mod;
            firstTiling = secondTiling;
            secondTiling = thirdTiling;
            thirdTiling = currentTiling;
        }

        return (int) thirdTiling;
    }
}

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

You can find the link to all the four solutions on the GitHub for this question here: 790. Domino and Tromino Tiling.

Conclusion

That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!

Thank you for reading!

Bharati Subramanian