Question

1725. Number Of Rectangles That Can Form The Largest Square

中文文档

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:

• 1 <= rectangles.length <= 1000
• rectangles[i].length == 2
• 1 <= li, wi <= 109
• li != wi

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)$.

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

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;
  }
}

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;
  }
};

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
}

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;
}