This problem comes from cracking the coding interview chapter 7 problem 6. To me as a mathematician this seems like a simple least squares problem where we find the best fit line. Although, in the solution they take a different approach.
My question is the following: is a developing a least squares approach a sufficient solution or am I not understanding the problem at hand?
Least squares isn't an appropriate solution, it doesn't care about the number of aligned points. The least-squares fit might contain no point at all.
The solution in the link by julian has an O(N²) behavior, assuming that a hash map has O(N) behavior to count duplicates. (With sorting, O(N²Log N) can be guaranteed.)
The main idea is to take every point in turn, to compute the directions to all other points, and count the coincident directions.