Tiling a Rectangle with the Fewest Squares Solution in C++

Problem Description

So, you want to tile a rectangle with the fewest squares possible? Sounds easy, right? Just grab a bunch of square tiles and start slapping them on the rectangle like you’re decorating a cake. But wait! What if your rectangle is 11×13 and you only have square tiles of size 1×1? You might as well be trying to fit a giraffe into a Mini Cooper!

In this delightful little puzzle, you’re tasked with figuring out how to cover a rectangle of size n x m using the least number of square tiles. The catch? The tiles can be of any size, but they must be squares. So, if you thought you could just throw a few rectangles in there, think again!

Code Solution


class Solution {
 public:
  int tilingRectangle(int n, int m) {
    unordered_map mem;
    return tilingRectangle(n, m, 0, /*heights=*/vector(m), mem);
  }

 private:
  static constexpr int kBase = 13;

  int tilingRectangle(int n, int m, long hashedHeights, vector&& heights,
                      unordered_map& 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();
    for (int sz = 1; sz <= min(m - start, n - minHeight); ++sz) {
      if (heights[start + sz - 1] != minHeight)
        break;
      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& heights) {
    long hashed = 0;
    for (int i = heights.size() - 1; i >= 0; --i)
      hashed = hashed * kBase + heights[i];
    return hashed;
  }
};

Approach Explanation

The code uses a recursive backtracking approach with memoization to efficiently find the minimum number of square tiles needed to cover the rectangle. It keeps track of the heights of the columns in the rectangle and tries to place squares of varying sizes, updating the heights accordingly. If a configuration has already been computed, it retrieves the result from memory instead of recalculating it. This clever use of hashing and memoization helps avoid redundant calculations, making the solution more efficient.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O((n * m)²)
Space Complexity	O(n * m)

Real-World Example

Imagine you’re a contractor trying to tile a dance floor for a wedding. The couple wants a beautiful rectangular floor, but they’re on a budget and want to minimize the number of tiles used. You have to figure out how to arrange the tiles in such a way that you don’t waste any space. This problem is just like that! You need to find the optimal way to cover the rectangle with the fewest square tiles, ensuring that every inch is covered without any gaps.