Ggthjy

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 in the 96th percentile of solutions on speed, and 100th percentile on memory, so I don't expect any drastic improvements. I'm posting this code because I think it's good, and I want to get a reality check if it's actually good 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;

};