LeetCode 1725 - Number Of Rectangles That Can Form The Largest Square

The problem gives us a list of rectangles, where each rectangle is represented as [li, wi]. Here, li is the rectangle's length and wi is its width. From each rectangle, we want to determine the largest square that can be cut from it.

leetcodeeasyarray

LeetCode Problem 1725

Difficulty: 🟢 Easy
Topics: Array

Solution

LeetCode 1725 - Number Of Rectangles That Can Form The Largest Square

Problem Understanding

The problem gives us a list of rectangles, where each rectangle is represented as [li, wi]. Here, li is the rectangle's length and wi is its width.

From each rectangle, we want to determine the largest square that can be cut from it. A square requires all sides to be equal, so the side length of the square cannot exceed either dimension of the rectangle. Therefore, the largest square that can be formed from a rectangle has side length:

$$\min(li, wi)$$

For example:

  • Rectangle [5,8] can produce a square of side length 5
  • Rectangle [3,9] can produce a square of side length 3

The task is not to return the largest square size itself. Instead, we must count how many rectangles can produce the maximum possible square among all rectangles.

Suppose the largest achievable square side length is 5. Then every rectangle whose minimum side is also 5 contributes to the answer.

The input constraints are relatively small:

  • Up to 1000 rectangles
  • Rectangle dimensions can be as large as 10^9

The small number of rectangles means even straightforward linear scans are efficient enough. The very large dimension values indicate we should avoid algorithms that depend on the size of the dimensions themselves.

The problem also guarantees:

  • Every rectangle contains exactly two integers
  • Both dimensions are positive
  • li != wi, meaning the input rectangles are never already squares

Important edge cases include:

  • Only one rectangle in the input
  • Multiple rectangles producing the same largest square
  • All rectangles producing different square sizes
  • Very large rectangle dimensions near 10^9
  • Rectangles where the smaller side appears in different positions, such as [5,8] versus [16,5]

A naive implementation could accidentally compare the larger side instead of the smaller side, which would produce incorrect results.

Approaches

Brute Force Approach

The brute force idea is to first compute the largest square each rectangle can produce. We store all these values in a separate array. Then we find the maximum value in that array. Finally, we scan the array again and count how many times that maximum appears.

This approach is correct because the largest square from a rectangle is always determined by its smaller side. By explicitly storing every possible square size, we can later determine the global maximum and count its frequency.

Although this approach is acceptable for the given constraints, it uses unnecessary extra space because we do not actually need to keep all intermediate values.

Optimal Approach

The key observation is that we only need two pieces of information while scanning the rectangles:

  1. The current maximum square side length
  2. How many rectangles achieve that maximum

As we process each rectangle:

  • Compute currentSquare = min(length, width)

  • If currentSquare is larger than the current maximum:

  • Update the maximum

  • Reset the count to 1

  • If currentSquare equals the current maximum:

  • Increment the count

This allows us to solve the problem in a single pass without storing all intermediate square sizes.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) Stores all square sizes before processing
Optimal O(n) O(1) Single pass with constant extra space

Algorithm Walkthrough

  1. Initialize two variables:
  • maxSquareSide to store the largest square side found so far
  • count to store how many rectangles achieve that size
  1. Iterate through every rectangle in the input array.
  2. For each rectangle [length, width], compute:

$$currentSquare = \min(length, width)$$

This works because the square side cannot exceed the smaller rectangle dimension. 4. Compare currentSquare with maxSquareSide. 5. If currentSquare is greater than maxSquareSide:

  • Update maxSquareSide
  • Reset count to 1

This means we discovered a new larger square, so previous counts are no longer relevant. 6. If currentSquare equals maxSquareSide:

  • Increment count

This means another rectangle can produce the same largest square. 7. Continue until all rectangles are processed. 8. Return count.

Why it works

The algorithm maintains the invariant that after processing each rectangle:

  • maxSquareSide is the largest square side seen so far
  • count is the number of rectangles that can produce that largest square

Whenever a larger square is found, previous counts become invalid because a new maximum exists. Whenever the same maximum appears again, the count increases. Since every rectangle is processed exactly once, the final count is correct.

Python Solution

from typing import List

class Solution:
    def countGoodRectangles(self, rectangles: List[List[int]]) -> int:
        max_square_side = 0
        count = 0

        for length, width in rectangles:
            current_square = min(length, width)

            if current_square > max_square_side:
                max_square_side = current_square
                count = 1
            elif current_square == max_square_side:
                count += 1

        return count

The implementation begins by initializing max_square_side and count.

For every rectangle, the code calculates the largest possible square side using min(length, width). This reflects the geometric constraint that a square must fit entirely inside the rectangle.

The comparison logic directly mirrors the algorithm walkthrough:

  • A larger square updates the maximum and resets the count
  • An equal square increments the count

No extra arrays or data structures are needed, which keeps the solution memory efficient.

Go Solution

func countGoodRectangles(rectangles [][]int) int {
    maxSquareSide := 0
    count := 0

    for _, rectangle := range rectangles {
        length := rectangle[0]
        width := rectangle[1]

        currentSquare := length
        if width < currentSquare {
            currentSquare = width
        }

        if currentSquare > maxSquareSide {
            maxSquareSide = currentSquare
            count = 1
        } else if currentSquare == maxSquareSide {
            count++
        }
    }

    return count
}

The Go implementation follows the same logic as the Python version. Since Go does not provide a built in integer min function for basic integers, the minimum value is computed manually using an if statement.

Go slices are used for the rectangle input. No additional memory allocation is required beyond a few integer variables, so the space complexity remains constant.

Integer overflow is not a concern because rectangle dimensions are at most 10^9, which safely fits within Go's standard integer range on LeetCode platforms.

Worked Examples

Example 1

Input:

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

Largest square sizes:

Rectangle min(length, width)
[5,8] 5
[3,9] 3
[5,12] 5
[16,5] 5

Step by step execution:

Step Rectangle Current Square maxSquareSide count
1 [5,8] 5 5 1
2 [3,9] 3 5 1
3 [5,12] 5 5 2
4 [16,5] 5 5 3

Final answer:

3

Example 2

Input:

rectangles = [[2,3],[3,7],[4,3],[3,7]]

Largest square sizes:

Rectangle min(length, width)
[2,3] 2
[3,7] 3
[4,3] 3
[3,7] 3

Step by step execution:

Step Rectangle Current Square maxSquareSide count
1 [2,3] 2 2 1
2 [3,7] 3 3 1
3 [4,3] 3 3 2
4 [3,7] 3 3 3

Final answer:

3

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each rectangle is processed exactly once
Space O(1) Only a few variables are used

The algorithm performs a single linear scan through the input array. Each iteration performs constant time operations, specifically computing a minimum and performing comparisons.

No auxiliary data structures proportional to the input size are created, so the extra memory usage remains constant.

Test Cases

from typing import List

class Solution:
    def countGoodRectangles(self, rectangles: List[List[int]]) -> int:
        max_square_side = 0
        count = 0

        for length, width in rectangles:
            current_square = min(length, width)

            if current_square > max_square_side:
                max_square_side = current_square
                count = 1
            elif current_square == max_square_side:
                count += 1

        return count

solution = Solution()

assert solution.countGoodRectangles([[5,8],[3,9],[5,12],[16,5]]) == 3  # provided example 1
assert solution.countGoodRectangles([[2,3],[3,7],[4,3],[3,7]]) == 3  # provided example 2

assert solution.countGoodRectangles([[1,2]]) == 1  # single rectangle
assert solution.countGoodRectangles([[4,5],[5,4],[6,7]]) == 1  # only one largest square
assert solution.countGoodRectangles([[5,6],[6,5],[5,9]]) == 3  # all share same largest square
assert solution.countGoodRectangles([[1000000000,1],[999999999,2]]) == 1  # very large values
assert solution.countGoodRectangles([[8,2],[7,3],[6,4],[5,5]]) == 1  # increasing square sizes
assert solution.countGoodRectangles([[9,8],[8,9],[8,8],[7,10]]) == 3  # repeated maximum square
assert solution.countGoodRectangles([[10,1],[9,2],[8,3],[7,4]]) == 1  # maximum appears once

Test Case Summary

Test Why
[[5,8],[3,9],[5,12],[16,5]] Validates the first official example
[[2,3],[3,7],[4,3],[3,7]] Validates the second official example
[[1,2]] Tests minimum input size
[[4,5],[5,4],[6,7]] Ensures only one rectangle achieves maximum
[[5,6],[6,5],[5,9]] Tests multiple rectangles sharing maximum
[[1000000000,1],[999999999,2]] Verifies handling of very large values
[[8,2],[7,3],[6,4],[5,5]] Tests progressively increasing square sizes
[[9,8],[8,9],[8,8],[7,10]] Tests repeated maximum values
[[10,1],[9,2],[8,3],[7,4]] Ensures correct counting when maximum appears once

Edge Cases

One important edge case is when the input contains only a single rectangle. In that situation, the answer must always be 1 because that rectangle automatically produces the largest possible square. The implementation handles this naturally because the first rectangle initializes both the maximum square size and the count.

Another important case occurs when several rectangles produce the same largest square side length. A buggy implementation might accidentally overwrite the count instead of incrementing it. The algorithm explicitly checks for equality and increments the counter whenever another matching rectangle is found.

A third edge case involves rectangles with dimensions in different orders, such as [5,8] and [16,5]. The implementation always computes min(length, width), so the order of dimensions does not matter. This guarantees correctness regardless of how the rectangle dimensions are arranged.

Large integer values near 10^9 are another consideration. Since the algorithm only performs comparisons and minimum operations, there is no risk of overflow or expensive arithmetic. Both the Python and Go implementations safely handle the full constraint range.