EasyNo. 1725
Number Of Rectangles That Can Form The Largest Square — LeetCode 1725 Python Solution
- Topics
- Array
- Reading time
- 2 min
- Source
- leetcode.com
The problem
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.
Example
- 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].
Python solution
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 ansComplexity
- Time
- O(n)where n is the length of the array rectangles
- Space · auxiliary
- O(1)
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0057 | Insert Interval | Medium |
| 0228 | Summary Ranges | Easy |
| 0485 | Max Consecutive Ones | Easy |
| 0665 | Non-decreasing Array | Medium |
| 0674 | Longest Continuous Increasing Subsequence | Easy |
| 0699 | Falling Squares | Hard |
Frequently asked questions
- How hard is LeetCode 1725. Number Of Rectangles That Can Form The Largest Square?
LeetCode 1725. Number Of Rectangles That Can Form The Largest Square is rated Easy on LeetCode.
- What is the time complexity of LeetCode 1725. Number Of Rectangles That Can Form The Largest Square?
The Python solution on this page runs in O(n), where n is the length of the array rectangles.
- What is the space complexity of LeetCode 1725. Number Of Rectangles That Can Form The Largest Square?
The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 1725. Number Of Rectangles That Can Form The Largest Square cover?
LeetCode 1725. Number Of Rectangles That Can Form The Largest Square is tagged Array on LeetCode.