Welcome with another problem to solve! Today, we are dealing with some little geometry and overlapping rectangles with this interesting problem: the first one of 2024! Cheers everyone! 🎉 Even if this is a simple problem, it took a quite big bunch of code to find a solution for it, and I’m not really sure if this is the best approach to solve this. So, as always, feel free to reply with your solution if you want to discuss this further! As always, this problem was provided by the wonderful newsletter Daily Coding Problem, which you can subscribe to ! Check it out, and try to solve your challenges too! here So, while we wait for my piece of art above to get some deserved pricing, let’s jump to the problem! The Problem Given two rectangles on a 2D graph, return the area of their intersection. If the rectangles don’t intersect, return 0. For example, given the following rectangles: {
    "top_left": (1, 4),
    "dimensions": (3, 3) # width, height
} and {
    "top_left": (0, 5),
    "dimensions": (4, 3) # width, height
} return 6. The problem is pretty clear: we are given the dimensions and coordinates of two rectangles. What we are asked to do is to calculate the area of the intersection: if there is none, we should simply return 0. Let’s draw some plans first! The Plan First off, let’s draw the two overlapping rectangles as in the example. Since we are on the graph, we can consider figures like this as collections of points. For instance, the blue rectangle A, is the collection of the following points: (1,4) (2,4) (3,4) (4,4) (1,3) (2,3) … (3,1) (4,1). The same idea can be applied to the other rectangle in the same way. This way, we can easily identify points in the intersection by looking at which points appear in both rectangles, as shown in purple below. By collecting the points, we can easily calculate back the lengths of the sides and the size of the overlapping area. Let’s jump to the code. It will be Go this time, so fasten your seatbelts: it will be a long and verbose journey! The Code Let’s walk the code step by step, as usual: https://gist.github.com/NicolaM94/32290881cf90b365564f28459ad5ab82?embedable=true#file-main-go First off, we create a for our rectangle, with some properties, namely , which are all given by the problem’s text. struct startingX, startingY, width, height After that, we write a method for our structure. Don’t get fooled by the keyword: declaring a structure type after that word; it’s simply the Go methods construction syntax. func This method called , which returns an array of arrays of integers ( ), will be used to collect… well, the points coordinates of the rectangle: who would have guessed that! Points out [][]int To calculate the points, we simply iterate accordingly from point to point, collecting them one by one, and temporarily storing them into a variable that gets emptied at each loop. couple This variable will also be appended to the array on each loop, so we can return everything at the end. out In the main function, we initialize two rectangles and calculate their points. Now, we need a function to collect common points: let’s write it up! https://gist.github.com/NicolaM94/0f9826a99162b2ca2978149b9943bd4f?embedable=true#file-main-go The function accepts two instances ranging over their points. If two points have the same coordinates, this point is added to for collection. CommonPoints Rectangle out We also update the main function to print out these common points. Finally, we can calculate the area: the function does exactly this. CalcAreaFromPoints https://gist.github.com/NicolaM94/0dda69b1f877e3797fc213d1a52c22be?embedable=true#file-main-go The function initially evaluates the length of the array containing the common points: if it’s zero, there are no common points, meaning that the rectangles do not overlap. After that, the function collects the four variables needed, looping over the point’s coordinates and comparing them. Once they are collected, it’s simple to give out the size of the common area as . minX, maxX, minY, maxY (maxX — minX)*(maxY-minY) We need to update our main function one last time to print out the area of common points. Time Complexity The time complexity of this algorithm is particularly painful since it’s crowded with quadratic time. We need to collect points, and to collect them, we need to range over the two dimensions of the rectangle. This will constrain us to a quadratic time complexity. We need to collect common points ranging over two rectangles. For the same reason above, also this time we are constrained to a squared time complexity. For the above reasons, the time complexity of this algorithm is the overall of . As I mentioned above, I’m pretty sure there are better or faster algorithms to do this: if you know one or you simply want to share your opinion, please feel free to do so in the comments! O(n²) Conclusion That’s it! As always, I want to thank you for reading up to this point: if you liked the article or found it useful please leave a like or two; it would really make my day! Also, if you can, and if you are willing to, you can support my work here by sharing a Ko-fi with me ! here As always, thanks for reading. Nicola

Overlapping Rectangles: A Daily Coding Problem

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

Daily Coding Problem: Building an Algorithm to Calculate Huge Factorials!

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

Daily Coding Problem: Building an Algorithm to Calculate Huge Factorials!

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps