Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1725.html

1725. Number Of Rectangles That Can Form The Largest Square

Level

Easy

Description

You are given an array rectangles where rectangles[i] = [l_i, w_i] represents the ith rectangle of length l_i and width w_i.

You can cut the i-th rectangle to form a square with a side length of k if both k <= l_i and k <= w_i. 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:

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

Solution

Loop over rectangles. For each rectangle, obtain the shorter side length as the side length of the square. After all rectangles are checked, the largest square’s side length can be determined. Then loop over rectangles again and calculate the number of rectangles that can form the largest square.

  • class Solution {
    public int countGoodRectangles(int[][] rectangles) {
        int width = 0;
        for (int[] rectangle : rectangles) {
            int shorter = Math.min(rectangle[0], rectangle[1]);
            width = Math.max(width, shorter);
        }
        int count = 0;
        for (int[] rectangle : rectangles) {
            int shorter = Math.min(rectangle[0], rectangle[1]);
            count += shorter == width ? 1 : 0;
        }
        return count;
    }
}

############

class Solution {
    public int countGoodRectangles(int[][] rectangles) {
        int ans = 0, mx = 0;
        for (int[] r : rectangles) {
            int t = Math.min(r[0], r[1]);
            if (mx < t) {
                mx = t;
                ans = 1;
            } else if (mx == t) {
                ++ans;
            }
        }
        return ans;
    }
}

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

############

# 1725. Number Of Rectangles That Can Form The Largest Square
# https://leetcode.com/problems/number-of-rectangles-that-can-form-the-largest-square/

class Solution:
    def countGoodRectangles(self, rectangles: List[List[int]]):
        
        mp = collections.defaultdict(int)
        for a,b in rectangles:
            mp[min(a,b)] += 1

        return mp[max(mp)]
        

  • class Solution {
public:
    int countGoodRectangles(vector<vector<int>>& rectangles) {
        int ans = 0, mx = 0;
        for (auto& r : rectangles) {
            int t = min(r[0], r[1]);
            if (mx < t) {
                mx = t;
                ans = 1;
            } else if (mx == t)
                ++ans;
        }
        return ans;
    }
};

  • func countGoodRectangles(rectangles [][]int) int {
	ans, mx := 0, 0
	for _, r := range rectangles {
		t := r[0]
		if t > r[1] {
			t = r[1]
		}
		if mx < t {
			mx, ans = t, 1
		} else if mx == t {
			ans++
		}
	}
	return ans
}

  • function countGoodRectangles(rectangles: number[][]): number {
    let maxLen = 0,
        ans = 0;
    for (let [l, w] of rectangles) {
        let k = Math.min(l, w);
        if (k == maxLen) {
            ans++;
        } else if (k > maxLen) {
            maxLen = k;
            ans = 1;
        }
    }
    return ans;
}

All Problems

All Solutions