LeetCode 1725. Number Of Rectangles That Can Form The Largest Square Solution in Java, C++, Python & More | Explanation + Code

Description

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.

 

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:

<li><code>1 &lt;= rectangles.length &lt;= 1000</code></li>

<li><code>rectangles[i].length == 2</code></li>

<li><code>1 &lt;= l<sub>i</sub>, w<sub>i</sub> &lt;= 10<sup>9</sup></code></li>

<li><code>l<sub>i</sub> != w<sub>i</sub></code></li>

Solutions

Solution 1: Single Pass

We define a variable ans to record the count of squares with the current maximum side length, and another variable mx to record the current maximum side length.

We traverse the array rectangles. For each rectangle [l, w], we take x = min(l, w). If mx < x, it means we have found a larger side length, so we update mx to x and update ans to 1. If mx = x, it means we have found a side length equal to the current maximum side length, so we increase ans by 1.

Finally, we return ans.

The time complexity is O(n), where n is the length of the array rectangles. The space complexity is O(1).

PythonJavaC++GoTypeScript

class Solution: def countGoodRectangles(self, rectangles: List[List[int]]) -> int: ans = mx = 0 for l, w in rectangles: x = min(l, w) if mx < x: ans = 1 mx = x elif mx == x: ans += 1 return ans(code-box)

class Solution { public int countGoodRectangles(int[][] rectangles) { int ans = 0, mx = 0; for (var e : rectangles) { int x = Math.min(e[0], e[1]); if (mx < x) { mx = x; ans = 1; } else if (mx == x) { ++ans; } } return ans; } }(code-box)

class Solution { public: int countGoodRectangles(vector<vector<int>>& rectangles) { int ans = 0, mx = 0; for (auto& e : rectangles) { int x = min(e[0], e[1]); if (mx < x) { mx = x; ans = 1; } else if (mx == x) { ++ans; } } return ans; } };(code-box)

func countGoodRectangles(rectangles [][]int) (ans int) { mx := 0 for _, e := range rectangles { x := min(e[0], e[1]) if mx < x { mx = x ans = 1 } else if mx == x { ans++ } } return }(code-box)

function countGoodRectangles(rectangles: number[][]): number { let [ans, mx] = [0, 0]; for (const [l, w] of rectangles) { const x = Math.min(l, w); if (mx < x) { mx = x; ans = 1; } else if (mx === x) { ++ans; } } return ans; }(code-box)