1725. Number Of Rectangles That Can Form The Largest Square

EasyArray
Leetcode Link

Problem Description

In the given problem, we are presented with an array named rectangles, where each element rectangles[i] represents the dimensions of the ith rectangle as a pair [l_i, w_i] indicating its length l_i and width w_i.

We are allowed to make cuts to these rectangles in order to form squares. A square can be formed from a rectangle if its side length k is less than or equal to both the length and the width of the rectangle. For instance, from a rectangle [4,6], we can cut out a square with a maximum side length of 4.

The objective is to find the side length of the largest square, maxLen, that can be formed from these rectangles. Then we need to count the number of rectangles in the array that are capable of forming a square with this maximum side length.

To summarize, the task is to first determine the largest possible square side length that can be cut out from any of the rectangles, and then to count how many rectangles in the list are large enough to provide a square of that size.

Intuition

The solution involves a straightforward approach. Here's the process to understand how the solution works:

  1. Initialize two variables ans and mx to keep track of the count of rectangles that can produce the largest square, and to store the maximum square side length, respectively.

  2. Traverse through each rectangle in the rectangles array and for each rectangle, determine the side length of the largest possible square, which would be the minimum of the length and width of the rectangle as we are bound by the lesser dimension. This value is stored in a temporary variable t.

  3. If we find a square side length t greater than the current mx, we know that we have found a new, larger square side length. So, we update mx to this new maximum side length t, and reset ans to 1 since this is the first rectangle that can form a square of side length t.

  4. If t is equal to mx, it means the current rectangle can also form a square of the largest side length found so far. Therefore, we increment ans by 1 to reflect this additional rectangle.

  5. If t is less than mx, we do nothing, as the rectangle cannot produce a square of side length maxLen.

  6. Once all rectangles have been processed, ans will contain the final count of rectangles that can produce squares of side length mx, and we return ans.

This solution works well because it efficiently iterates through the list only once, determines the maximum square side length in the process, and simultaneously counts the qualifying rectangles.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Depth first search can be used to find whether two components in a graph are connected.

Solution Approach

The solution takes advantage of simple mathematical concepts and logical comparison within a single-pass for-loop to achieve the desired result.

Here's a step-by-step breakdown of the implementation details with reference to the solution code:

  1. Initialize two variables, ans to store the number of rectangles that can form the largest square, initially set to 0, and mx to store the maximum square side length possible, also initially set to 0.

    1ans = mx = 0

  2. We begin iterating over each rectangle provided in the rectangles list. Within the loop, we're performing the following steps for each rectangle:

    1for l, w in rectangles:

  3. Calculate the largest possible square side length t from the current rectangle by taking the minimum of its length l and width w. This relies on the constraint that a square's side length must be less than or equal to the lengths of both sides of the rectangle.

    1t = min(l, w)

  4. Compare the calculated square side length t with the maximum found so far, mx. If t is greater, we've discovered a new maximum square size. We then update mx to this new value, and set ans to 1 since this is the first occurrence of such a large square.

    1if mx < t:
2    mx, ans = t, 1

  5. If t equals the current maximum mx, it means another rectangle was found which can form a square of the same maximum size. Hence we increment ans by 1 without changing mx.

    1elif mx == t:
2    ans += 1

  6. If t is less than mx, that indicates the current rectangle cannot contribute to a square of side length mx, so no operation is performed.

  7. After the loop completes, the variable ans contains the count of rectangles which can form the largest square, and this value is returned.

    1return ans

In terms of algorithms and data structures, this solution is a straight-forward linear scan (O(n) complexity) without the need for any additional complex data structures. The use of basic variables and a single for-loop makes the code efficient and easy to understand. This elegant simplicity arises from the observation that we're interested only in the counts related to the maximum square size which can be maintained and updated on-the-fly as we inspect each rectangle.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Example Walkthrough

Let's consider the following array of rectangles: rectangles = [[3, 5], [6, 6], [5, 2], [4, 4]]. We need to determine the largest square side length we can cut from any rectangle and then count how many rectangles can form a square of that size.

  1. We initialize ans and mx to 0. These will keep track of the count and size of the largest square, respectively.

  2. We begin iterating over each rectangle:

    • For the first rectangle [3, 5], the largest square side length t we can cut is min(3, 5) = 3. Since 3 is greater than the current mx (0), we update mx to 3 and set ans to 1.

    • Moving on to the second rectangle [6, 6], t = min(6, 6) = 6. This is greater than the current mx (3), so mx is updated to 6 and ans is reset to 1.

    • For the third rectangle [5, 2], t = min(5, 2) = 2. This is less than the current mx (6), so no changes are made to mx or ans.

    • The last rectangle [4, 4] also provides a square with t = min(4, 4) = 4, which is still less than our mx (6), so again no changes are made to mx or ans.

  3. After completing the loop, mx is 6 and ans is 1, since only one rectangle, [6, 6], could produce a square with the largest possible side length. Hence, the function would return 1.

This example demonstrates the straightforward linear scan through the array and the simple tracking of the maximum square side length and the count of rectangles that could form a square of that maximum size.

Not Sure What to Study? Take the 2-min Quiz：

What are the most two important steps in writing a depth first search function? (Select 2)

Python Solution

1from typing import List
2
3class Solution:
4    def countGoodRectangles(self, rectangles: List[List[int]]) -> int:
5        # Initialize maximum square length and count of good rectangles
6        max_square_length = 0
7        good_rectangles_count = 0
8      
9        # Loop through each rectangle to find the maximum square length
10        for length, width in rectangles:
11            # Find the smaller of the two sides to get the largest possible square
12            side_length = min(length, width)
13          
14            # If the current square length is greater than the previous maximum,
15            # update max_square_length and reset good_rectangles_count
16            if side_length > max_square_length:
17                max_square_length = side_length
18                good_rectangles_count = 1
19            # If the current square length is equal to the maximum,
20            # increment the count of good rectangles
21            elif side_length == max_square_length:
22                good_rectangles_count += 1
23      
24        # Return the total count of rectangles that can produce the largest square
25        return good_rectangles_count
26

Java Solution

1class Solution {
2    public int countGoodRectangles(int[][] rectangles) {
3        int countOfMaxSquares = 0; // This will keep track of how many maximum squares we can cut.
4        int maxSize = 0; // This will keep the maximum square size we can get.
5
6        // Loop through each rectangle.
7        for (int[] rectangle : rectangles) {
8            // Find the size of the largest square that fits within the rectangle.
9            // This is the smaller side of the rectangle.
10            int largestSquareSize = Math.min(rectangle[0], rectangle[1]);
11
12            // If we found a larger square size than we've seen so far,
13            // update the maximum size and reset the count of max squares.
14            if (maxSize < largestSquareSize) {
15                maxSize = largestSquareSize;
16                countOfMaxSquares = 1;
17            } else if (maxSize == largestSquareSize) {
18                // If we found a square with a size equal to the current maximum,
19                // increment the count of max size squares.
20                ++countOfMaxSquares;
21            }
22        }
23
24        // After checking all rectangles, return the count of the largest squares.
25        return countOfMaxSquares;
26    }
27}
28

C++ Solution

1#include <vector>  // Include necessary library for vector
2#include <algorithm> // Include for access to the min function
3
4class Solution {
5public:
6    int countGoodRectangles(std::vector<std::vector<int>>& rectangles) {
7        int maxSquareLen = 0;     // Variable to store the maximum square length
8        int goodRectanglesCount = 0;  // Variable to count the number of good rectangles
9
10        // Iterate over each rectangle in the input vector
11        for (const std::vector<int>& rect : rectangles) {
12            // Calculate the maximum square length that can be cut out of the current rectangle
13            int squareLen = std::min(rect[0], rect[1]);
14
15            // If the current square length is greater than maxSquareLen, update maxSquareLen
16            // and reset goodRectanglesCount since we have found a larger square
17            if (squareLen > maxSquareLen) {
18                maxSquareLen = squareLen;
19                goodRectanglesCount = 1;  // Start counting from one as this is the new largest square
20            }
21            // If the current square length is equal to maxSquareLen, increment the count
22            else if (squareLen == maxSquareLen) {
23                ++goodRectanglesCount;
24            }
25        }
26      
27        // After iterating through all rectangles, return the count of good rectangles
28        return goodRectanglesCount;
29    }
30};
31

Typescript Solution

1// Function to count the number of rectangles that can form a square with the largest side
2function countGoodRectangles(rectangles: number[][]): number {
3    let maxSquareSide = 0; // Initialize a variable to keep track of the maximum square side length
4    let squareCount = 0; // Initialize a counter to keep track of the number of squares with maxSquareSide
5
6    // Loop through each rectangle
7    for (let [length, width] of rectangles) {
8        // Find the minimum side to determine the size of the largest square
9        let largestSquareSide = Math.min(length, width);
10
11        // If the current square's side is equal to the maximum found so far, increment the count
12        if (largestSquareSide == maxSquareSide) {
13            squareCount++;
14        } else if (largestSquareSide > maxSquareSide) {
15            // If current square's side is larger, update the maximum side and reset the count
16            maxSquareSide = largestSquareSide;
17            squareCount = 1;
18        }
19    }
20
21    // After looping through all rectangles, return the count of squares with the largest side
22    return squareCount;
23}
24
Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Time and Space Complexity

Time Complexity

The time complexity of the given code is O(n), where n is the number of rectangles in the input list rectangles. This is because the code iterates through each rectangle exactly once, and for each rectangle, it performs a constant number of operations: calculating the minimum of the length and width, comparison, and possibly incrementing the answer or updating the maximum length of a square.

Space Complexity

The space complexity of the code is O(1). This is because the code only uses a fixed amount of additional space: two variables (ans and mx). The amount of space used does not depend on the input size, so the space complexity is constant.

Learn more about how to find time and space complexity quickly.

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫