Max Number of Collinear Points

Asked in a Hedge fund Interview for Quant Analyst

Given n points on a 2D plane, find the equation of the line with maximum number of collinear points. What is the time complexity of your algorithm?

---

Try to solve this problem yourself before moving on to the solution below

.
.
.
.
.
.

---

Solution

This problem has a lot of possible solutions as it is open-ended.

Our Approach

The equation ax+b = y defines a line;

1. Initialize a HashMap with key (a,b) and an integer value;

2. For each edge of two points, Compute a,b and increment the integer value associated with (a,b) in the HashMap -> O(n*n)

3. Compute the maximum of the values in the HashMap and return the associated key -> O(n*n)

This algorithm assumes the HashMap can update in O(1) time. Similarly, we can use another data structure, like Binary Search tree updates in O(log n) time

Total time complexity O(n*n)

😃 Over to you: Were you able to solve this?

---

👉 If you liked this post, don’t forget to leave a like ❤️. It helps more people discover this newsletter on Substack and tells us that you appreciate solving these weekly questions. The button is located towards the bottom of this email.

👉 If you love reading this newsletter, feel free to share it with friends!