1725. Number Of Rectangles That Can Form The Largest Square
Introduction
Geometry in Programming, oh boy… here we go again. Programing Problems built exclusively for computer science undergrads, what did I get myself into. Don’t they realize many folks entering this field are career changers? It’s been years since many of us even saw a geometry problem, let alone solve one!
Well, at least that’s what I felt initially. Oftentimes “mathy” stuff triggers a boatload of negative experiences from the past. I’ve noticed this with other people making this change in their lives. You may have been a poor student, had a terrible math teacher, or just found the whole topic boring. Whatever happened in your past, I want you to know that I’m deeply sorry and clearly have been wronged in some way. Math is pretty awesome, and maybe you weren’t ready for it; consider letting it back into your heart again. More importantly, this problem isn’t as “mathy” as it seems. So no worries will get this code challenge.
First, let’s take a breath, re-center ourselves, and channel our inner problem-solving warrior. Feeling better? good, now lets Henry V., out of this mother… Our weapon of choice will be Javascript, and if you're not familiar with it, I encourage you to keep reading along to understand the reasoning behind how I solved this problem.
The Prompt
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.
My Thoughts
With this problem, we will need to read the prompt, look at the provide examples, and try to deduce what the author is asking us. The idea here is to be able to phrase the question in our own words. If we fully comprehend the problem, we have a much better chance of creating an all-encompassing solution to it.
As always, if things seem too concise or dense to understand fully, I break them down line by line. Please allow me to show you what I mean…
You are given an array rectangles where rectangles[i] = [li, wi] represents the ith rectangle of length li and width wi.Okay, write off the bat. We see the author uses li and wi, which are the width and length of a rectangle. The author mentions that the rectangles’ dimensions (li and wi)are held in an array as a pair. Makes sense so far.
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.Interesting and also equally confusing. What the author is saying is, we can cut squares out of rectangles. Think of it like a sheet of construction paper, and we are cutting out squares from it.
Let maxLen be the side length of the largest square you can obtain from any of the given rectangles.Understanding that will be cutting squares from any given rectangle from the rectangles array. We want the largest possible squares based on the length of the rectangle we are cutting from. So rectangle[i] = [4,6], we know 4 is the length value ‘li,’ so the biggest square would be the length of 4.
Return the number of rectangles that can make a square with a side length of maxLen.We will need the number of squares we can cut from a given rectangle. So our output will be an integer. Pretty simple.
Sum up what we know…
- Our input is an array of rectangles called rectangles
- li is length, wi is width, stored in pairs. The first number is length, and the second is width.
- Each rectangles[i] = [li, wi] , each rectangle is stored in the array under an index
- We will be cutting squares from any given rectangle.
- We want the biggest possible square, so that should match either the length or the width.
- We will need to look at the smallest value(length or width), though, because squares have widths and lengths that are always equal.
- Our output: The most “Max Length” or “Biggest” squares you can cut from any given rectangle
Let’s work it out…
Let’s use the same method of breaking down the prompt. Will cut up this solution into smaller problems. Like above, we will break things down to understand them and build things up with our new insights into the problem.
The let’s start with grabbing all the smallest values from each rectangle. We will need some variables and a loop. I approached this step like so…
- Lookup- set to an empty object. You’ll store each number, and if we get duplicates will count them. It should be a key-value pair…
- Key: “unique lowest number(could be length or width)”
- Value: “your count of duplicates/How many you have.”
- Low variable- set to an empty array. Will want to collect all the smallest values from the reach rectangle here.
- For a loop- It should iterate over rectangles array.
const countGoodRectangles = function(rectangles) {
let lookup = {}, low = [];
for(let i = 0; i < rectangles.length; i++) {
} ...We will use the .push() array method to put each rectangle value into our low array. To find the lowest value, we will use the Math.min() method. Since we don’t want to mutate the rectangles array we are iterating over, we will use a spread operator to make a clone/copy of this data. It looks like this “…rectangles[i]”
... for(let i = 0; i < rectangles.length; i++) {
low.push(Math.min(...rectangles[i]))
} ...Now will use a ternary statement to look at each value in our low array. What will happen here is it will make a new entry into the lookup variable we created(our key-value pair). If it already exists, it will simple up the count by 1.
... for(let i = 0; i < rectangles.length; i++) {
low.push(Math.min(...rectangles[i]))
lookup[low[i]] ? lookup[low[i]] += 1 : lookup[low[i]] = 1
} ...So now we have an object with all the information we need to solve this problem. We need to access this data and return it. Let’s start with another for loop and iterate over our low array…
for(let j = 0; j < low.length; j++) {
}Will want to grab the largest value and hold on to it with a variable. This will play nicely with our lookup variable. Both are global variables so that this new loop will have access to them.
for(let j = 0; j < low.length; j++) {
let target = Math.max(...low)
}Finally, we will need to use an if statement to access this lookup variable. If it exists, it will return its value. TADA! there’s the count we needed to return. Run your test, next submit it, and pat yourself on the back.
for(let j = 0; j < low.length; j++) {
let target = Math.max(...low)
if (`${target}`in lookup) {
return lookup[target]
}
}Solution
const countGoodRectangles = function(rectangles) {
let lookup = {}, low = [];
for(let i = 0; i < rectangles.length; i++) {
low.push(Math.min(...rectangles[i]))
lookup[low[i]] ? lookup[low[i]] += 1 : lookup[low[i]] = 1
}
for(let j = 0; j < low.length; j++) {
let target = Math.max(...low)
if (`${target}`in lookup) {
return lookup[target]
}
}};
Conclusion
We got our code to pass while simultaneously overcoming an irrational fear of math. At least I hope so... No worries if it’s confusing. Most complex things are. So you’re in the right place to learn and grow ;)
Let’s focus on the takeaway from this problem. By breaking things down into smaller pieces, we can understand them better. Writing out the concepts in your own terms means you’ve translated the knowledge into something that makes sense to you. Using that knowledge, it’s MUCH easier to solve the problem.
If you get things wrong, you NEED to target the issues. Was it a conceptual problem, like the rules of a square? Was it a factual problem… you forgot the syntax for the .reduce(). Real learning starts here. It’s not necessarily fast. Oftentimes it feels like a slow grind, but over time you’ll build up that knowledge, and suddenly you’ve become damn good at problem solver. Stick with it, and Happy Coding!
Links:
LeetCode: leetcode.com
