Google Interview Question — LeetCode 1240

In this post, we are going to discuss leetcode 1240 — Tiling a Rectangle with the Fewest Squares, which is asked in Google interviews.

Problem Analysis

Given a rectangle of size n x m, return the minimum number of integer-sided squares that tile the rectangle.

Example 1:

Input: n = 2, m = 3 
Output: 3 
Explanation: 3 squares are necessary to cover the rectangle. 2 (squares of 1x1) 1 (square of 2x2)

Example 2:

Input: n = 5, m = 8 
Output: 5

Example 3:

Input: n = 11, m = 13 
Output: 6

My Thinking Process

This looks like a very difficult problem, and seems like no idea to start with. But if you have been following my posts, you will find this problem is very straight forward!

Focus eon the keyword in the question statement: “ minimum number of squares” to fill the rectangle. As I have mentioned multiple times, whenever we see the keyword to that to reach a target state with minimum number of steps, it is a BFS problem!

As we have discussed, we need to define the following:

1. What the state would be for this question
2. The starting state
3. The ending state

We are filling the rectangle, and we can start filling from the bottom. The rules will be:

1. To make sure we can fill the entire rectangle, we should always try to fill in the lowest area first.
2. To use the minimum number of squares to fill, we should always try to fill the largest square possible.

We can define the following:

1. A state can be the height of the current filled area, and the number of squares have been used
2. The starting state will be an array of height zeros, and the target state will be an array of n, where n is the height of the rectangle
3. Use BFS, and at every loop, we should always follow the two rules defined above to find the square to fill.

Also, we need to have the narrower side of the rectangle as the bottom, so that it will be easier for us to find the maximum square.

Code Implementation

Base on the analysis above, below is my implementation of the problem.