Number Of Rectangles That Can Form The Largest Square - Video Solutions

Problem Overview: You are given a list of rectangles where each rectangle has a width and height. From each rectangle, you can cut a square whose side length equals min(width, height). The goal is to determine the maximum square side you can obtain and count how many rectangles can produce that square.

The key observation: every rectangle can contribute at most one square, and the largest square you can cut from a rectangle is limited by its smaller side. So the problem reduces to computing min(width, height) for each rectangle and counting how many rectangles achieve the maximum possible value.

Approach 1: Iterative Calculation of Maximum Square (O(n) time, O(1) space)

Scan the list of rectangles once. For each rectangle, compute side = min(width, height). Track two variables while iterating: the current maximum square size and how many rectangles achieve that size. If side > maxSide, update maxSide and reset the count to 1. If side == maxSide, increment the count. This works because the largest square possible overall must be the largest min(width, height) among all rectangles. The algorithm performs a single pass over the array, making it both optimal and straightforward.

This approach avoids extra data structures and performs constant work per rectangle. It is the cleanest implementation for interviews and production code because it directly models the problem's constraint: the square side is always limited by the rectangle's smaller dimension.

Approach 2: Using Sorting to Simplify Counting (O(n log n) time, O(1) extra space)

Another option is to compute min(width, height) for each rectangle and then sort these values. After sorting, the largest square size appears at the end of the array. Count how many times this maximum value occurs by scanning backward until the value changes. Sorting introduces O(n log n) time due to the ordering step, but the counting logic becomes very simple.

This method can be useful when you already plan to sort data for another reason or when solving variations that require ordered processing. The idea relies on standard sorting techniques applied to values derived from the array.

Recommended for interviews: The iterative single-pass solution is what interviewers expect. It runs in O(n) time with O(1) space and shows you recognized the key insight: the largest square from a rectangle equals its smaller side. Mentioning the sorting alternative demonstrates understanding of tradeoffs, but the linear scan highlights stronger algorithmic reasoning.