Number Of Rectangles That Can Form The Largest Square Python/Java solution

In Python or Java, iterate through the rectangles list and compute min(width, height) for each pair. Track the maximum side length and how many rectangles produce it. Both implementations run in O(n) time with O(1) additional space.

How to solve Number Of Rectangles That Can Form The Largest Square in O(n)?

Iterate through the rectangles array and compute side = min(width, height) for each rectangle. Maintain two variables: maxSide and count. If side exceeds maxSide, update maxSide and reset count to 1; if side equals maxSide, increment count. After processing all rectangles, count represents how many rectangles can form the largest square.

What is the best approach for Number Of Rectangles That Can Form The Largest Square?

The best approach is a single-pass greedy scan. For each rectangle, compute min(width, height) to determine the largest square it can produce. Track the maximum square side and count how many rectangles achieve that value. This solution runs in O(n) time and O(1) space.

Is Number Of Rectangles That Can Form The Largest Square asked at Google/Amazon/Meta?

Array-based greedy counting problems like this appear frequently in coding interviews at large tech companies such as Amazon, Google, and Meta. While this exact question is relatively simple, it tests basic array traversal, reasoning about constraints, and recognizing key observations quickly.

What data structure is used in Number Of Rectangles That Can Form The Largest Square?

The primary data structure is a simple array containing rectangle dimensions. The algorithm processes each element sequentially and does not require additional structures such as hash maps or heaps, keeping memory usage constant.

What is the time complexity of Number Of Rectangles That Can Form The Largest Square?

The optimal solution runs in O(n) time because it iterates through the rectangles once and performs constant work per element. Space complexity is O(1) since only a few variables are used to track the maximum square side and its count.

Description Hints 3 Solution Video 9:09

1725. Number Of Rectangles That Can Form The Largest Square

Q: Is Number Of Rectangles That Can Form The Largest Square easy or hard?

Number Of Rectangles That Can Form The Largest Square is classified as an Easy problem. The key step is recognizing that the largest square from a rectangle is determined by its smaller dimension, which leads to a straightforward linear scan solution.

Easy79.5% acceptance1 company

You are given an array rectangles where rectangles[i] = [l_i, w_i] represents the i^th rectangle of length l_i and width w_i.

You can cut the i^th rectangle to form a square with a side length of k if both k <= l_i and k <= w_i. 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.

Example 1:

Input: rectangles = [[5,8],[3,9],[5,12],[16,5]]
Output: 3
Explanation: The largest squares you can get from each rectangle are of lengths [5,3,5,5].
The largest possible square is of length 5, and you can get it out of 3 rectangles.

Example 2:

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

Constraints:

1 <= rectangles.length <= 1000
rectangles[i].length == 2
1 <= l_i, w_i <= 10⁹
l_i != w_i

Asked at 1 company

Allincall

Topics

Array

Hints open one at a time

Hint 1

What is the length of the largest square the can be cut out of some rectangle? It'll be equal to min(rectangle.length, rectangle.width). Replace each rectangle with this value.

Hint 2

Calculate maxSize by iterating over the given rectangles and maximizing the answer with their values denoted in the first hint.

Hint 3

Then iterate again on the rectangles and calculate the number whose values = maxSize.

9:09

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def countGoodRectangles(self, rectangles: List[List[int]]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[[5,8],[3,9],[5,12],[16,5]]

Input

[[2,3],[3,7],[4,3],[3,7]]

Your code is saved on this device.Solution