Given a list of coordinates, find the rectangle with minimal area

Question

A problem on leetcode asks the coder to write an algorithm to take a bunch of coordinates in the xy-plane and return the minimum area of a rectangle made from four of these coordinates (or return 0 if no four of these coordinates describe a rectangle). Admissible rectangles must have sides parallel to the coordinate axes.

I'd appreciate any comments and improvements on my code whatsoever. Of course some of them may not make sense in the context of Leetcode, and I mention such an example below. But they may still be good for me to be aware of. My code scores well among submissions on Leetcode, so I may have the right idea for the algorithm. I'm posting this code because I think it's decent, and I want to get a reality check if it's actually decent or not -- this is my first post on code review.

Leetcode asks the code to be a class called Solution with a method int minAreaRect(std::vector<std::vector<int>>& points), and they will test this code using this method. One effect of this is that it does no good (as far as I know) to make a constructor Solution::Solution(std::vector<std::vector<int>> &points), which would be the most natural. Therefore, for instance, I have to store points in my class as a pointer, not a reference, because I can't know what points is at construction time.

This problem seems to call for something like a multimap from x-coordinates to the set of y-coordinates for which (x,y) is in points. I chose to implement my own "flat multimap" -- since I am doing all my insertion at once, it seems better to just make a sorted vector, and so I just sorted the input vector. (The problem does not address whether I am allowed to modify the input vector -- if I were not allowed to, I would copy it and sort the copy.)

My code examines all possible pairs of distinct x-coordinates, and then looks for the overlap of the y-coordinates associated with them. If the intersection of their y-coordinates has less than two elements, there is no possible rectangle to be made from this pair of x-coordinates. Therefore the code bypasses x-coordinates that have fewer than two y-coordinates associated with them.

An example test case would look like this

int main ()
{
    std::vector<std::vector<int>> v {{0,1}, {3,2}, {5, 5}, {4, 5}, {4,4}, {2,0}, {2, 3}, {2, 2}, {1, 0}, {5, 1}, {2, 5}, {5, 2}, {2, 4}, {4, 0}};
    Solution sol;
    std::cout << sol.minAreaRect(v);
    return 0;
}

Outputs: 2, because (2,4), (2,5), (4,4), and (4,5) describe a rectangle of area two, and that is the best we can do.

My code uses two different comparators -- one which puts coordinates in lexicographic order, and one called comp_coords_fc_only which simply compares the first coordinate. The reason I made the second is so that I could call std::upper_bound(current_coord, points.end(), (*current_coord)[0], comp_coords_fc_only), which will take me to the next entry of points that has a different x-coordinate. I put this in a method called next_fc.

#include <vector>
#include <algorithm>
#include <iterator>
#include <iostream>

using coord_it = std::vector<std::vector<int>>::iterator;

bool comp_coords_lexic(const std::vector<int> &lhs, const std::vector<int> &rhs) {
    if (lhs[0] != rhs[0])
        return lhs[0] < rhs[0];
    return lhs[1] < rhs[1];
}

bool comp_coords_fc_only(const std::vector<int> &lhs,  const std::vector<int> &rhs) {
    return (lhs[0] < rhs[0]);
}

class Solution {
    //"fc" = "first coordinate" and "sc" = "second coordinate"
public:
    int minAreaRect(std::vector<std::vector<int>>& _points) {

        if (_points.size() < 4)
            return 0;

        std::sort(_points.begin(), _points.end(), comp_coords_lexic);

        points = &_points;
        int record_min_area = INT_MAX;

        for (coord_it current_left_fc = _points.begin(); current_left_fc != _points.end(); current_left_fc = next_fc(current_left_fc)) {
            if (has_less_than_two(current_left_fc))
                continue;

            for (coord_it current_right_fc = next_fc(current_left_fc); current_right_fc != _points.end(); current_right_fc = next_fc(current_right_fc)) {
                if (has_less_than_two(current_right_fc))
                    continue;

                int distance_fc = (*current_right_fc)[0] - (*current_left_fc)[0];

                if (distance_fc > record_min_area)
                    continue; // need not explore first coords that are so far apart the area would necessarily be too big.

                int min_distance_sc = min_distance_shared_scs(current_left_fc, current_right_fc);

                if (min_distance_sc == 0)
                    continue; // if they don't have two scs in common

                record_min_area = std::min(record_min_area, distance_fc * min_distance_sc);
            } // for loop, right fc
        } // for loop, left fc

        if (record_min_area == INT_MAX)
            return 0;
        return record_min_area;
    }

private:
    int min_distance_shared_scs(coord_it beg_left_fc_range, coord_it beg_right_fc_range) {
        // given two first coordinates (in the form of iterators pointing at the first entry
        // with that first coordinate) x1 and x2, find min d(y1, y2) subject to (x1,y1), (x1, y2)
        // (x2, y1), and (x2, y2) all being in the coordinate vector.

        int last_match = INT_MIN; // sentinel value
        int record_min_distance = INT_MAX;

        auto upper_bound_left = next_fc(beg_left_fc_range), upper_bound_right = next_fc(beg_right_fc_range);
        auto current_left_sc = beg_left_fc_range, current_right_sc = beg_right_fc_range;
        while (current_left_sc != upper_bound_left && current_right_sc != upper_bound_right) {

            if (equal_second_coord(current_left_sc, current_right_sc)) {

                if (last_match == INT_MIN) {
                    last_match = (*current_left_sc)[1];
                    ++current_left_sc; ++current_right_sc;
                    continue;
                }

                int distance_from_last = (*current_left_sc)[1] - last_match;
                record_min_distance = std::min(record_min_distance, distance_from_last);
                last_match = (*current_left_sc)[1];
                ++current_left_sc; ++current_right_sc;
                continue;
            }

            if ((*current_left_sc)[1] < (*current_right_sc)[1])
                ++current_left_sc;
            else
                ++current_right_sc;
        } // while loop going through two ranges

        if (record_min_distance == INT_MAX)
            return 0;
        return record_min_distance;
    }

    static bool equal_second_coord(coord_it it1, coord_it it2) {
        return ((*it1)[1] == (*it2)[1]);
    }

    bool has_less_than_two(coord_it input_it) {
        auto upper_bound = next_fc(input_it);
        return (std::distance(input_it, upper_bound) < 2);
    }

    coord_it next_fc(coord_it it) {
        return std::upper_bound(it, (*points).end(), *it, comp_coords_fc_only);
    }

    std::vector<std::vector<int>>* points;
};

Answer 1

We already have a standard algorithm for comp_coords_lexic:

bool comp_coords_lexic(const std::vector<int> &lhs, const std::vector<int> &rhs)
{
    return std::lexicographical_compare(lhs.begin(), lhs.end(),
                                        rhs.begin(), rhs.end());
}

Stylewise, I'd probably write x and y rather than fc and sc everywhere. Those are a better match to programmer expectations when we're doing planar geometry.

For the algorithm, perhaps a better representation of the points would be a pair of maps: one from each x-coordinate to a set of y-coordinates and another mapping each y-coordinate to a set of x-coordinates? That makes it much easier to find other points to consider with the current one (and since sets are sorted, we can finish the inner loop when we reach the current outer-loop point).

It may make sense to compute the area when we have three candidate points, and discard it unless the possible area is an improvement on the current smallest, and only then check for the existence of the fourth point (since the search is more expensive than multiplication).

Is there a limit on the range of int values used for coordinates? We might need a wider type for storing the area (in fact, we may well need a wider type simply to represent coordinate differences).