_{December 09, 2025}

My Approach to Advent Of Code 2025 Day 9 Part 2

Intro

It’s hard to believe, but this year marks the eleventh Advent of Code.

This time it’s shorter - only 12 days. Today is the 9th day, and the second part of the puzzle was the first one this year that I didn’t solve instantly.

Now that I finally have a blog (even though I rarely find the free time to write anything here), I can at least share how I solved this puzzle.

My solution can be found on my GitHub. (It’s written as a one-off script.)

The Problem

We are given a list of 2D integer points that form a polygon. We want to find the largest rectangle whose opposite corners are two of those points and that lies entirely inside the polygon.

For example, consider the following polygon:

........
.1####2.
.######.
.###4#3.
.6##5...
........

(I labeled the input points with numbers and filled the polygon with #.)

For this input, the maximal rectangle is the one between points 1 and 3. The rectangle between 2 and 6 is larger, but it is not fully inside the polygon.

The Approach

Initially, I decided to go with a brute-force approach and optimize it later.

The brute-force idea is:

Create a 2D array - let’s call it a canvas.
Draw and fill the polygon on the canvas.
For each pair of points, check whether the rectangle defined by them is fully filled on the canvas.

This works, and I believe that if I had used Rust (or any other compiled language like Go or C++) it would run in a reasonable amount of time. But since I’m using Python this year, my estimate was around 2–3 hours. Too slow.

So I had to introduce some optimizations:

The main optimization I used is what I call coordinate space compression. I remap coordinates so that large empty gaps count as size 1.
I use prefix sums to quickly check whether a rectangle is fully filled.

Now for the details.

Filling the Polygon

The most common algorithm for determining whether a point lies inside a polygon is to cast a ray from the point and count how many polygon edges it crosses. If the number is even, the point is outside; otherwise, it is inside.

Essentially, I used this idea:

Plot vertical borders on the canvas

For each row:
    inside = false
    For each cell:
        if there is a border:
            inside = not inside
        else if inside:
            mark cell as inside

However, there are some edge cases.

Consider this example:

1  .......
2  ...v#v.
3  .v#v#v.
4  .v###v.
5  .......

(v marks vertical borders and # marks other polygon points.)

On line 2 the algorithm works as expected, but on line 3 it incorrectly produces:

3  .v#v.v#

To fix this, I distinguish between borders going up and going down. This way, I know which border I crossed first and only exit when I cross one going in the opposite direction.

For example:

1  .......
2  ...u#d.
3  .u#u#d.
4  .u###d.
5  .......

Now on line 3, the logic works like this:

Cross a border going up - we are inside
Cross another border going up - still inside
Cross a border going down - now we are outside

Compressing the Space

This step can take a lot of time - and memory. Coordinates go up to (10^5), which means potentially (10^10) operations.

To fix this, I collect all unique x- and y-coordinates and remap them so that empty spaces between consecutive coordinates have size 1.

For example, for coordinates [10, 11, 15, 20, 21], I map them to [0, 1, 3, 5, 6]:

10 11 12 13 14 15 16 17 18 19 20 21
 #  #  .  .  .  #  .  .  .  .  #  #
 |  |   \   /       \      /
 #  #     .     #      .       #  #
 0  1     2     3      4       5  6

This reduces the problem space from (O(max_coordinate^2) to O(num_points^2).

Using these compressed coordinates, I perform the filling algorithm described earlier.

Finding the Maximal Rectangle

To find the maximum rectangle, I examine every pair of points and check whether the rectangle between them is fully filled.

A naive check would examine every cell inside the rectangle, making the solution O(n^3).

Instead, I compute prefix sums, where
prefix_sum[x, y] = number of painted cells in the rectangle (0,0) - (x,y).

This allows checking whether a rectangle is fully filled in O(1) time and keep the whole solution O(N^2).

Conclusion

I’m looking forward to solving tomorrow’s puzzle, even though I’m not sure I’ll have time to write about it here.