Daily bit(e) of C++ | Maximum number of points on a line
Daily bit(e) of C++ #56, The common interview problem: Maximum number of points on a line.
Today we will look at a common C++ interview problem: The maximum number of points on a line.
Given a list of points represented by x and y integer coordinates, determine the maximum number of points that can be connected by drawing a single straight line.
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a compiler explorer link with a couple of test cases: https://compiler-explorer.com/z/ej4GhGx3b.
Solution
The critical observation is that any two points will define a line (crossing those two points). This directly leads to the obvious solution. We can iterate over all pairs of points, counting which other points also lie on that line. Unfortunately, this approach is O(n^3). We can do better.
Let’s instead anchor one point and consider the lines we can draw through this point. Then, each unique line will be identified by its angle. If we iterate over all other points, the maximum line going through our anchor corresponds to the angle with the maximum number of instances.
We can use an unordered map from angle to count, which will allow us to update the count in O(1), and since we need to consider all points as the potential anchors, and for each, we iterate over all other points, we end up with O(n^2) complexity.
To represent the angle, we can build a simple fraction type, taking care of normalizing it so that each unique angle has a unique representation (leading to the same hash). To make it usable as a key in an unordered map, we must provide the operator== and specialization for the std::hash.
