I just wrote some code I'm not proud of, but I just wanted to get shit done. However, I now turn to the collective wisdom of the fediverse to ask for the simplest algorithm to do the following:

Given a list of pairs of numbers (row and column indexes), check that all the numbers form a rectangle with no duplicates, and if so, return the position of the top-left element as well as the width and height of the rectangle. If not, return null.

To make things easier, I'm linking to my code below. However, I'm certain this is not the ideal solution. What is the cleanest algorithm to achieve this?

https://gist.github.com/lokedhs/5b71a8f3874429bb3ec434106396fca0

@loke Find the min x,y and max x,y, check the total number of elements equals the area of the rectangle (max x-min x+1)*(max y-min y+1).

The only remaining problem is to check there are no repeats, so sort the list of (x,y) lexicographically and look for duplicate pairs that will now be adjacent.

@sjb this, but in opposite order: lexicographical sort and remove duplicates (single n log(n) pass with early return if duplicates are found) then get the area from the first and last element of the sequence.

@namark Yes, and all that remains is getting the min/max values and checking it is consistent with a rectangle, should work.

@sjb I meant min/max is the first and last elements

@namark I don't think that works because there could be an element out-of-bounds in Y that is lexicographically in the middle of the sequence in (X,Y), so you'd need an additional loop to find the bounds at least in one axis.