Overlapping Rectangles: A Daily Coding Problem

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 here! Check it out, and try to solve your challenges too!

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 struct for our rectangle, with some properties, namely startingX, startingY, width, height , which are all given by the problem’s text.

After that, we write a method for our structure. Don’t get fooled by the func keyword: declaring a structure type after that word; it’s simply the Go methods construction syntax.

This method called Points , which returns an array of arrays of integers ( out [][]int ), will be used to collect… well, the points coordinates of the rectangle: who would have guessed that!

To calculate the points, we simply iterate accordingly from point to point, collecting them one by one, and temporarily storing them into a couple variable that gets emptied at each loop.

This variable will also be appended to the out array on each loop, so we can return everything at the end.

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 CommonPoints accepts two Rectangle instances ranging over their points. If two points have the same coordinates, this point is added to out for collection.

We also update the main function to print out these common points.

Finally, we can calculate the area: the function CalcAreaFromPoints does exactly this.

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, minX, maxX, minY, maxY 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 (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 O(n²). 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!

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