Number Of Rectangles That Can Form The Largest Square

Easy
1107.

Number Of Rectangles That Can Form The Largest Square

Number Of Rectangles That Can Form The Largest Square is an easy coding problem on arrays and counting, asked in Amazon and Google interviews.

rectangles[i] = [l, w] is a rectangle of length l and width w. You may cut a square out of a rectangle as long as its side is at most both l and w — so the biggest square rectangle i can give has side min(l, w).

Let maxLen be the largest square side that any rectangle can give. Return how many rectangles can give a square of side maxLen.

Example 1

Input
rectangles = [[4,9],[7,3],[9,4],[4,6]]
Output
3
Explanation
The best squares have sides 4, 3, 4 and 4, so maxLen = 4 and three rectangles reach it.

Example 2

Input
rectangles = [[2,3],[6,5],[3,9]]
Output
1

Example 3

Input
rectangles = [[10,1000000000]]
Output
1

Constraints

  • 1 <= rectangles.length <= 1000
  • rectangles[i].length == 2
  • 1 <= l, w <= 10^9
  • l != w
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} rectangles
 * @return {number}
 */
var countGoodRectangles = function(rectangles) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number Of Rectangles That Can Form The Largest Square Solution

Number Of Rectangles That Can Form The Largest Square solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Number Of Rectangles That Can Form The Largest Square is an easy coding problem on arrays and counting, asked in Amazon and Google interviews.

  • Difficulty: Easy
  • Topics: Arrays, Counting
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

rectangles[i] = [l, w] is a rectangle of length l and width w. You may cut a square out of a rectangle as long as its side is at most both l and w — so the biggest square rectangle i can give has side min(l, w).

Let maxLen be the largest square side that any rectangle can give. Return how many rectangles can give a square of side maxLen.

Example 1

Input: rectangles = [[4,9],[7,3],[9,4],[4,6]]
Output: 3
Explanation: The best squares have sides 4, 3, 4 and 4, so maxLen = 4 and three rectangles reach it.

Example 2

Input: rectangles = [[2,3],[6,5],[3,9]]
Output: 1

Example 3

Input: rectangles = [[10,1000000000]]
Output: 1

Constraints

  • 1 <= rectangles.length <= 1000
  • rectangles[i].length == 2
  • 1 <= l, w <= 10^9
  • l != w

Hints for Number Of Rectangles That Can Form The Largest Square

  1. Hint 1

    Each rectangle contributes exactly one number: the shorter of its two sides.

  2. Hint 2

    You need the maximum of those numbers and how often it occurs.

  3. Hint 3

    Both can be tracked in a single pass: reset the count when a new maximum appears.

How to solve Number Of Rectangles That Can Form The Largest Square

Reduce each rectangle to min(l, w), the side of the largest square it can give; the answer is how many times the maximum of those values occurs.

Approach

  1. Keep best = 0 and count = 0.
  2. For each rectangle compute side = min(l, w).
  3. If side > best, set best = side and count = 1; if side == best, increment count.
  4. Return count.

Why it works

A rectangle can give a square of side maxLen exactly when its shorter side is at least maxLen, and since maxLen is the largest shorter side, that means exactly equal. The running maximum with a reset counter counts those rectangles in one pass.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Use the shorter side — the longer side does not limit the square.
  • Reset the count to 1, not 0, when a new maximum appears.
  • Sides reach 10^9, which still fits a 32-bit int; no sums are needed.

Reference solution

Python

from typing import List

def countGoodRectangles(rectangles: List[List[int]]) -> int:
    sides = [min(l, w) for l, w in rectangles]
    return sides.count(max(sides))

Java

public static int countGoodRectangles(int[][] rectangles) {
    int best = 0, count = 0;
    for (int[] r : rectangles) {
        int side = Math.min(r[0], r[1]);
        if (side > best) {
            best = side;
            count = 1;
        } else if (side == best) {
            count++;
        }
    }
    return count;
}

C++

int countGoodRectangles(vector<vector<int>>& rectangles) {
    int best = 0, count = 0;
    for (auto& r : rectangles) {
        int side = min(r[0], r[1]);
        if (side > best) {
            best = side;
            count = 1;
        } else if (side == best) {
            count++;
        }
    }
    return count;
}

JavaScript

var countGoodRectangles = function(rectangles) {
    var best = 0, count = 0;
    for (var i = 0; i < rectangles.length; i++) {
        var side = Math.min(rectangles[i][0], rectangles[i][1]);
        if (side > best) {
            best = side;
            count = 1;
        } else if (side === best) {
            count++;
        }
    }
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays