Tiling a Rectangle with the Fewest Squares

Tiling a Rectangle with the Fewest Squares - Problem

Backtracking Hard

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

You need to find the optimal way to divide the rectangle into squares such that:

All squares have integer side lengths
The squares completely cover the rectangle without overlapping
The total number of squares is minimized

Example: A 2×3 rectangle can be tiled with 3 squares of size 1×1, or with other combinations, but we want the minimum count.

Input & Output

Example 1 — Square Case

$ Input: n = 2, m = 2

› Output: 1

💡 Note: A 2×2 rectangle is already a perfect square, so we need only 1 square of size 2×2

Example 2 — Small Rectangle

$ Input: n = 2, m = 3

› Output: 3

💡 Note: We can tile the 2×3 rectangle with 3 squares: one 2×2 square and two 1×1 squares, or three 2×1 rectangles each made of two 1×1 squares. The minimum is 3 squares total.

Example 3 — Larger Rectangle

$ Input: n = 5, m = 8

› Output: 5

💡 Note: The 5×8 rectangle can be optimally tiled with 5 squares. One approach: one 5×5 square and four smaller squares to cover the remaining 5×3 area.

Constraints

1 ≤ n, m ≤ 13
Answer will be a positive integer

Visualization

Tap to expand

Understanding the Visualization

Input

Rectangle of dimensions n × m

Process

Try all possible cuts to minimize square count

Output

Minimum number of squares needed

Key Takeaway

🎯 Key Insight: Use recursive cuts with memoization to avoid recalculating the same subproblems

Asked in

G Google 15 M Microsoft 12 F Facebook 8

The key insight is to use recursive backtracking with memoization to try all possible cuts. We can make horizontal or vertical cuts at any position and recursively solve the resulting subproblems. Best approach is memoized recursion with pruning for optimal performance. Time: O(n²×m²), Space: O(n×m)

Common Approaches

Approach	Time	Space	Notes
✓ Recursive Backtracking	O(2^(n+m))	O(n+m)	Try all possible ways to cut the rectangle and recursively solve subproblems
Optimized Backtracking with Pruning	O(n²×m²)	O(n×m)	Enhanced recursion with early termination and smart ordering
Memoized Recursion	O(n²×m²)	O(n×m)	Cache results of subproblems to avoid recomputation

Recursive Backtracking — Algorithm Steps

Step 1: If rectangle is already a square, return 1
Step 2: Try all horizontal cuts, recursively solve top and bottom parts
Step 3: Try all vertical cuts, recursively solve left and right parts
Step 4: Return minimum squares needed across all cutting options

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial Rectangle

Start with n×m rectangle

Try Cuts

Test horizontal and vertical cuts at each position

Recurse

Solve subproblems and combine results

Code -

solution.c — C

#include <stdio.h>
#include <limits.h>

int min(int a, int b) {
    return (a < b) ? a : b;
}

int solution(int n, int m) {
    if (n == m) {
        return 1;
    }
    
    int result = INT_MAX;
    
    // Try horizontal cuts
    for (int i = 1; i < n; i++) {
        result = min(result, solution(i, m) + solution(n - i, m));
    }
    
    // Try vertical cuts
    for (int j = 1; j < m; j++) {
        result = min(result, solution(n, j) + solution(n, m - j));
    }
    
    return result;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(2^(n+m))

Each position can be cut or not cut, leading to exponential combinations

✓ Linear Growth

Space Complexity

O(n+m)

Recursion depth limited by sum of dimensions

⚡ Linearithmic Space

28.4K Views

Medium Frequency

~35 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

Recursive Backtracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler