Number Of Rectangles That Can Form The Largest Square

Number Of Rectangles That Can Form The Largest Square - Problem

Array Easy

You are given an array rectangles where rectangles[i] = [li, wi] represents the ith rectangle of length li and width wi.

You can cut the ith rectangle to form a square with a side length of k if both k <= li and k <= wi. For example, if you have a rectangle [4,6], you can cut it to get a square with a side length of at most 4.

Let maxLen be the side length of the largest square you can obtain from any of the given rectangles.

Return the number of rectangles that can make a square with a side length of maxLen.

Input & Output

Example 1 — Basic Case

$ Input: rectangles = [[5,8],[3,9],[5,12],[16,5]]

› Output: 3

💡 Note: The largest square you can cut from each rectangle: [5,8]→5, [3,9]→3, [5,12]→5, [16,5]→5. The largest square size is 5, and 3 rectangles can form this size.

Example 2 — All Same Size

$ Input: rectangles = [[2,3],[3,7],[4,3]]

› Output: 2

💡 Note: Maximum square sizes: [2,3]→2, [3,7]→3, [4,3]→3. The largest square size is 3, and 2 rectangles ([3,7] and [4,3]) can form this size.

Example 3 — Single Rectangle

$ Input: rectangles = [[10,20]]

› Output: 1

💡 Note: Only one rectangle [10,20] can form a square of size min(10,20)=10. So 1 rectangle can form the maximum square.

Constraints

1 ≤ rectangles.length ≤ 1000
rectangles[i].length == 2
1 ≤ li, wi ≤ 10⁹

Visualization

Tap to expand

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is that the largest square you can cut from a rectangle is limited by its shorter side. The optimal approach tracks both the maximum square size and count in a single pass through the array. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Two-Pass Approach	O(n)	O(1)	First find the maximum possible square size, then count rectangles that can form it
Single-Pass Approach	O(n)	O(1)	Find maximum square size and count in one pass through the array

Two-Pass Approach — Algorithm Steps

Step 1: Find the maximum square size by taking min(length, width) for each rectangle
Step 2: Count how many rectangles have min(length, width) equal to the maximum size

Visualization

Tap to expand

Step-by-Step Walkthrough

Pass 1

Find maximum possible square size from all rectangles

Pass 2

Count rectangles that can form the maximum square

Result

Return the count

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

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

int max(int a, int b) {
    return a > b ? a : b;
}

int solution(int rectangles[][2], int n) {
    // First pass: find maximum square size
    int maxSquareSize = 0;
    for (int i = 0; i < n; i++) {
        int squareSize = min(rectangles[i][0], rectangles[i][1]);
        maxSquareSize = max(maxSquareSize, squareSize);
    }
    
    // Second pass: count rectangles that can form max square
    int count = 0;
    for (int i = 0; i < n; i++) {
        int squareSize = min(rectangles[i][0], rectangles[i][1]);
        if (squareSize == maxSquareSize) {
            count++;
        }
    }
    
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    int rectangles[1000][2];
    int n = 0;
    
    char* ptr = line + 1; // Skip first [
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            rectangles[n][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++; // Skip comma
            rectangles[n][1] = atoi(ptr);
            while (*ptr && *ptr != ']') ptr++;
            ptr++; // Skip ]
            n++;
        }
        if (*ptr == ',') ptr++;
    }
    
    printf("%d\n", solution(rectangles, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Two separate loops through n rectangles

✓ Linear Growth

Space Complexity

O(1)

Only using variables to track maximum and count

✓ Linear Space

27.7K Views

Medium Frequency

~10 min Avg. Time

867 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

Two-Pass Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler