Skip to content

Commit 10e14ba

Browse files
committed
New Problem Solution -"Number Of Rectangles That Can Form The Largest Square"
1 parent 3c577b4 commit 10e14ba

File tree

2 files changed

+75
-0
lines changed

2 files changed

+75
-0
lines changed

README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -52,6 +52,7 @@ LeetCode
5252
|1734|[Decode XORed Permutation](https://leetcode.com/problems/decode-xored-permutation/) | [C++](./algorithms/cpp/decodeXORedPermutation/DecodeXoredPermutation.cpp)|Medium|
5353
|1733|[Minimum Number of People to Teach](https://leetcode.com/problems/minimum-number-of-people-to-teach/) | [C++](./algorithms/cpp/minimumNumberOfPeopleToTeach/MinimumNumberOfPeopleToTeach.cpp)|Medium|
5454
|1732|[Find the Highest Altitude](https://leetcode.com/problems/find-the-highest-altitude/) | [C++](./algorithms/cpp/findTheHighestAltitude/FindTheHighestAltitude.cpp)|Easy|
55+
|1725|[Number Of Rectangles That Can Form The Largest Square](https://leetcode.com/problems/number-of-rectangles-that-can-form-the-largest-square/) | [C++](./algorithms/cpp/numberOfRectanglesThatCanFormTheLargestSquare/NumberOfRectanglesThatCanFormTheLargestSquare.cpp)|Easy|
5556
|1625|[Lexicographically Smallest String After Applying Operations](https://leetcode.com/problems/lexicographically-smallest-string-after-applying-operations/) | [C++](./algorithms/cpp/lexicographicallySmallestStringAfterApplyingOperations/LexicographicallySmallestStringAfterApplyingOperations.cpp)|Medium|
5657
|1624|[Largest Substring Between Two Equal Characters](https://leetcode.com/problems/largest-substring-between-two-equal-characters/) | [C++](./algorithms/cpp/largestSubstringBetweenTwoEqualCharacters/LargestSubstringBetweenTwoEqualCharacters.cpp)|Easy|
5758
|1605|[Find Valid Matrix Given Row and Column Sums](https://leetcode.com/problems/find-valid-matrix-given-row-and-column-sums/) | [C++](./algorithms/cpp/FindValidMatrixGivenRowAndColumnSums/FindValidMatrixGivenRowAndColumnSums.cpp)|Medium|
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,74 @@
1+
// Source : https://leetcode.com/problems/number-of-rectangles-that-can-form-the-largest-square/
2+
// Author : Hao Chen
3+
// Date : 2021-03-27
4+
5+
/*****************************************************************************************************
6+
*
7+
* You are given an array rectangles where rectangles[i] = [li, wi] represents the i^th rectangle of
8+
* length li and width wi.
9+
*
10+
* You can cut the i^th rectangle to form a square with a side length of k if both k <= li and k <=
11+
* wi. For example, if you have a rectangle [4,6], you can cut it to get a square with a side length
12+
* of at most 4.
13+
*
14+
* Let maxLen be the side length of the largest square you can obtain from any of the given rectangles.
15+
*
16+
* Return the number of rectangles that can make a square with a side length of maxLen.
17+
*
18+
* Example 1:
19+
*
20+
* Input: rectangles = [[5,8],[3,9],[5,12],[16,5]]
21+
* Output: 3
22+
* Explanation: The largest squares you can get from each rectangle are of lengths [5,3,5,5].
23+
* The largest possible square is of length 5, and you can get it out of 3 rectangles.
24+
*
25+
* Example 2:
26+
*
27+
* Input: rectangles = [[2,3],[3,7],[4,3],[3,7]]
28+
* Output: 3
29+
*
30+
* Constraints:
31+
*
32+
* 1 <= rectangles.length <= 1000
33+
* rectangles[i].length == 2
34+
* 1 <= li, wi <= 10^9
35+
* li != wi
36+
******************************************************************************************************/
37+
38+
class Solution {
39+
public:
40+
int countGoodRectangles(vector<vector<int>>& rectangles) {
41+
return countGoodRectangles2(rectangles);
42+
return countGoodRectangles1(rectangles);
43+
}
44+
45+
int countGoodRectangles1(vector<vector<int>>& rectangles) {
46+
int maxLen = 0;
47+
for(auto& rect : rectangles) {
48+
int len = min(rect[0], rect[1]);
49+
maxLen = max(maxLen, len);
50+
}
51+
52+
int cnt = 0;
53+
for(auto& rect : rectangles) {
54+
if (maxLen <= rect[0] && maxLen <= rect[1]) cnt++;
55+
}
56+
return cnt;
57+
}
58+
59+
int countGoodRectangles2(vector<vector<int>>& rectangles) {
60+
int maxLen = 0;
61+
int cnt = 0;
62+
for(auto& rect : rectangles) {
63+
int len = min(rect[0], rect[1]);
64+
if (len > maxLen ) {
65+
cnt = 1;
66+
maxLen = len;
67+
}else if (len == maxLen ) {
68+
cnt++;
69+
}
70+
}
71+
72+
return cnt;
73+
}
74+
};

0 commit comments

Comments
 (0)