Number Of Rectangles That Can Form The Largest Square

🏠 ⬅️ ➡️

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
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: n = 4
    integer, dimension(n) :: rectangles
    integer :: i, k, maxLen, count

    ! Examples
    rectangles(1) = [5, 8]
    rectangles(2) = [3, 9]
    rectangles(3) = [5, 12]
    rectangles(4) = [16, 5]

    ! Output
    write (*, '(A)') 'Example 1:'
    call solve(rectangles, maxLen, count)
    write (*, '(I0, A, I0)') count, ' rectangles can make a square with a side length of ', maxLen
    write (*, '(A)') ''

    rectangles(1) = [2, 3]
    rectangles(2) = [3, 7]
    rectangles(3) = [4, 3]
    rectangles(4) = [3, 7]

    ! Output
    write (*, '(A)') 'Example 2:'
    call solve(rectangles, maxLen, count)
    write (*, '(I0, A, I0)') count, ' rectangles can make a square with a side length of ', maxLen
    write (*, '(A)') ''

contains

    subroutine solve(rectangles, maxLen, count)
        implicit none
        integer, intent(in) :: rectangles(:, :)
        integer, intent(out) :: maxLen, count
        integer :: i, j, k, l, m, n, p, q, r, s, t, u, v, w, x, y, z

        maxLen = -huge(maxLen)
        count = 0

        do i = 1, size(rectangles, 1)
            do j = 1, size(rectangles, 2)
                k = rectangles(i, 1)
                l = rectangles(i, 2)
                m = min(k, l)
                n = max(k, l)
                p = (m + 1) / 2
                q = (n + 1) / 2
                r = (p * q) / 2
                s = (r + 1) / 2
                t = (s + 1) / 2
                u = (t + 1) / 2
                v = (u + 1) / 2
                w = (v + 1) / 2
                x = (w + 1) / 2
                y = (x + 1) / 2
                z = (y + 1) / 2
                if (z > maxLen) then
                    maxLen = z
                    count = 1
                else if (z == maxLen) then
                    count = count + 1
                end if
            end do
        end do
    end subroutine solve
end program main
❌ Compiled
❌ Executed
❌ Correct 
module SquareWithMaxSide
    implicit none
    private
    public :: squareWithMaxSide
contains
    function squareWithMaxSide(rectangles) result(count)
        integer, intent(in) :: rectangles(:,:)
        integer :: count, i, k, maxLen, li, wi

        count = 0
        maxLen = 0

        do i = 1, size(rectangles, 1)
            li = rectangles(i, 1)
            wi = rectangles(i, 2)

            k = min(li, wi)

            if (k > maxLen) then
                maxLen = k
                count = 1
            else if (k == maxLen) then
                count = count + 1
            end if
        end do
    end function squareWithMaxSide
end module SquareWithMaxSide

program test_squareWithMaxSide
    use SquareWithMaxSide
    implicit none
    integer, parameter :: rectangles(4, 2) = reshape([5, 8, 3, 9, 5, 12, 16, 5], [4, 2])
    integer :: count

    count = squareWithMaxSide(rectangles)

    write (*, '(A, I0)') 'The number of rectangles that can make a square with a side length of ', maxLen
end program test_squareWithMaxSide
🌐 Data from online sources 
def numberOfSets(n, k):
    mod = 10**9 + 7
    dp = [[0] * (k + 1) for _ in range(n)]
    presum = [1] * n

    for j in range(1, k + 1):
        for i in range(n):
            dp[i][j] = presum[i]
            if i > 0:
                dp[i][j] += dp[i - 1][j]
            dp[i][j] %= mod
            presum[i] = (presum[i] + dp[i][j - 1]) % mod

    return dp[n - 1][k]

The problem can be solved using dynamic programming. We create a 2D array dp of dimensions (n, k + 1), where dp[i][j] stores the number of ways to draw j non-overlapping line segments up to point i. We also maintain an array presum which is the prefix sum of the dp array.

We then loop through j from 1 to k and i from 0 to n-1, calculating dp[i][j] using the values in presum and dp arrays. To avoid recomputing values, we update the presum array iteratively.

Finally, we return the value in dp[n - 1][k] which is the number of ways to draw k non-overlapping line segments up to point n-1.

🌐 Data from online sources 
int numberOfSets(int n, int k) {
    long long mod = 1e9 + 7;
    vector<vector<long long>> dp(n, vector<long long>(k + 1, 0));
    vector<long long> presum(n, 1);

    for (int j = 1; j <= k; ++j) {
        for (int i = 0; i < n; ++i) {
            dp[i][j] = presum[i];
            if (i) {
                dp[i][j] += dp[i - 1][j];
            }
            dp[i][j] %= mod;
            presum[i] = (presum[i] + dp[i][j - 1]) % mod;
        }
    }

    return dp[n - 1][k];
}

The problem can be solved using dynamic programming. We create a 2D array dp of dimensions (n, k + 1), where dp[i][j] stores the number of ways to draw j non-overlapping line segments up to point i. We also maintain an array presum which is the prefix sum of the dp array.

We then loop through j from 1 to k and i from 0 to n-1, calculating dp[i][j] using the values in presum and dp arrays. To avoid recomputing values, we update the presum array iteratively.

Finally, we return the value in dp[n - 1][k] which is the number of ways to draw k non-overlapping line segments up to point n-1.