1240. Tiling a Rectangle with the Fewest Squares LeetCode Solution
In this guide, you will get 1240. Tiling a Rectangle with the Fewest Squares LeetCode Solution with the best time and space complexity. The solution to Tiling a Rectangle with the Fewest Squares problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Tiling a Rectangle with the Fewest Squares
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 1×1)
1 (square of 2×2)
Example 2:
Input: n = 5, m = 8
Output: 5
Example 3:
Input: n = 11, m = 13
Output: 6
Constraints:
1 <= n, m <= 13
Complexity Analysis
Time Complexity: O(\max(n, m) \cdot 2^{\max(n, m)})
Space Complexity: O(\max(n, m) \cdot 2^{\max(n, m)})
1240. Tiling a Rectangle with the Fewest Squares LeetCode Solution in C++
class Solution {
public:
int tilingRectangle(int n, int m) {
unordered_map<long, int> mem;
return tilingRectangle(n, m, 0, /*heights=*/vector<int>(m), mem);
}
private:
static constexpr int kBase = 13;
int tilingRectangle(int n, int m, long hashedHeights, vector<int>&& heights,
unordered_map<long, int>& mem) {
if (const auto it = mem.find(hashedHeights); it != mem.cend())
return it->second;
const auto it = ranges::min_element(heights);
const int minHeight = *it;
if (minHeight == n) // All filled.
return 0;
int ans = m * n;
const int start = it - heights.begin();
// Try to put square of different size that doesn't exceed the width/height.
for (int sz = 1; sz <= min(m - start, n - minHeight); ++sz) {
// heights[start..start + sz) must has the same height.
if (heights[start + sz - 1] != minHeight)
break;
// Put a square of size `sz` to cover heights[start..start + sz).
for (int i = start; i < start + sz; ++i)
heights[i] += sz;
ans = min(ans,
tilingRectangle(n, m, hash(heights), std::move(heights), mem));
for (int i = start; i < start + sz; ++i)
heights[i] -= sz;
}
return mem[hashedHeights] = 1 + ans;
}
long hash(const vector<int>& heights) {
long hashed = 0;
for (int i = heights.size() - 1; i >= 0; --i)
hashed = hashed * kBase + heights[i];
return hashed;
}
}; /* code provided by PROGIEZ */
1240. Tiling a Rectangle with the Fewest Squares LeetCode Solution in Java
class Solution {
public int tilingRectangle(int n, int m) {
return tilingRectangle(n, m, 0, new int[m]);
}
private static final int kBase = 13;
private Map<Long, Integer> dp = new HashMap<>();
private int tilingRectangle(int n, int m, long hashedHeights, int[] heights) {
if (dp.containsKey(hashedHeights))
return dp.get(hashedHeights);
final int minHeight = Arrays.stream(heights).min().getAsInt();
if (minHeight == n) // All filled.
return 0;
int ans = m * n;
int start = -1;
for (int i = 0; i < m; ++i)
if (heights[i] == minHeight) {
start = i;
break;
}
// Try to put square of different size that doesn't exceed the width/height.
for (int sz = 1; sz <= Math.min(m - start, n - minHeight); ++sz) {
// heights[start..start + sz) must has the same height.
if (heights[start + sz - 1] != minHeight)
break;
// Put a square of size `sz` to cover heights[start..start + sz).
for (int i = start; i < start + sz; ++i)
heights[i] += sz;
ans = Math.min(ans, tilingRectangle(n, m, hash(heights), heights));
for (int i = start; i < start + sz; ++i)
heights[i] -= sz;
}
dp.put(hashedHeights, 1 + ans);
return 1 + ans;
}
private long hash(int[] heights) {
long hashed = 0;
for (int i = heights.length - 1; i >= 0; --i)
hashed = hashed * kBase + heights[i];
return hashed;
}
} // code provided by PROGIEZ
1240. Tiling a Rectangle with the Fewest Squares LeetCode Solution in Python
class Solution:
def tilingRectangle(self, n: int, m: int) -> int:
@functools.lru_cache(None)
def dp(heights: int) -> int:
minHeight = min(heights)
if minHeight == n: # All filled.
return 0
ans = m * n
heightsList = list(heights)
start = heightsList.index(minHeight)
# Try to put square of different size that doesn't exceed the width/height.
for sz in range(1, min(m - start + 1, n - minHeight + 1)):
# heights[start..start + sz) must has the same height.
if heights[start + sz - 1] != minHeight:
break
# Put a square of size `sz` to cover heights[start..start + sz).
heightslist[start:start + sz] = [minHeight + sz] * sz
ans = min(ans, dp(tuple(heightsList)))
return 1 + ans
return dp(tuple([0] * m)) # code by PROGIEZ
