Home » Data Structure » Hashing Coding Problems

# Count maximum points on same line

In this article, we are going to see how to use hashing efficiently to solve the problem of finding the maximum points on the same line?

Submitted by Radib Kar, on July 05, 2020

Prerequisite: Hashing data structure

**Problem statement:**

From a given set of input points find a maximum no of points on the same line.

**Example:**

Points are represented as a list of lists where the inner list is *[x, y]* representing a single point.

Input list: [1,1] -> 1st point [3,3] -> 2nd point [-1,-1] -> 3rd point [4, 4] -> 4th point [5, 6] -> 5th point [7,4] -> 6th point

The graph plotted is like below,

From the above input images, it’s visible that max no of point in the same line is 4. As there is 4 point in one line and the other line there are 2 points. So maximum points on the same line are 4.

**Edge cases:**

The edges cases for the problem is:

- In the inputs, there can be similar points which will be counted separately

**Solution:**

To find whether three or more points are on the same line or not we need gradient (*m*) to check.

If two points are *[x1,y1]* and *[x2,y2]* then the gradient, *m* is calculated as: *m=(y1-y2)/(x1-x2) or 1/m=(x1-x2)/(y1-y2)/*

Now, *m* can be 0 when *y1=y2* and can be infinity when *x1=x2*. While computing we need to take care of the infinity case as well.

So, the basic idea is, take two points as reference points for the line initially and check with other points how many points will fall on that line, i.e., will have the same gradient.

But this will take *O(n^3)* as we will require three loops to runs. Outer two loops will for two reference point selection and the inner one will be for other points selection.

Hashing can improve the complexity of keeping the logic the same. So what will be our hash function and how would we construct our hash table.

The idea is, we will have one point as reference and we will compute gradient with all the other points and store the gradient in our hash table and ill increment the same hash values.

So the hashing function, *h(point)=gradient(x, reference point)*.

So it will have complexity only *O(n^2)* as the outer loop will be to choose the reference point and the inner loop to pick other points to compute the gradient. After completion of each inner loop, we will get the number of points falling in the same line with the reference point.

Finally, we will keep updating our maximum number of points after each outer loop iteration.

**How to handle edge case of repeating points?**

As mentioned earlier we may have the same points in the input list and both need to be considered separately. If we compute gradient we will find 0/0 which is indeterminate. So we need to keep a check for whether the other point is the same or not. If the same increment the count and finally add the count in max no of points for the reference point.

Check the detailed algorithm to understand fully and check the code to get the implementation.

**Algorithm:**

Input array of points=points 1. Set max_point=0 2. For each point o taking as reference point: Initialize an hash table to store the gradients Set temp_max_point =0 Set count=1 which will track same no of points for other points(edge case handling) For each other point p If p is not same as o Find gradient m b/w p and o Add gradient to the hash table like below mymap[m]++; update temp_max_point=max(temp_max_point,mymap[m]); else if p and o are same point increment count end if-else end for update max_point=max(max_point,count+ temp_max_point) (consider the same points too) end for max_point has the final result

**C++ implementation:**

#include <bits/stdc++.h> using namespace std; //to find gradient long double slope(vector<int> a, vector<int> b) { //infinity case if (a[0] == b[0]) return DBL_MAX; return (long double)((long double)(a[1] - b[1]) / (long double)(a[0] - b[0])); } //whether two points are same or not bool same(vector<int> a, vector<int> b) { if (a[0] == b[0] && a[1] == b[1]) return true; return false; } //function to find maximum points in the same line int maxPoints(vector<vector<int> >& points) { if (points.size() < 2) return points.size(); int maxl = 0; int n = points.size(); for (int i = 0; i < n; i++) { map<long double, int> mymap; int temp = 0; int count = 1; for (int j = 0; j < n; j++) { if (j != i && !same(points[i], points[j])) { long double p; p = slope(points[i], points[j]); //cout<<p<<endl; mymap[p]++; temp = max(temp, mymap[p]); //cout<<temp<<endl; } else if (j != i && same(points[i], points[j])) { count++; } } maxl = max(maxl, count + temp); } return maxl; } int main() { int n; cout << "Enter number of points\n"; cin >> n; vector<vector<int> > arr; cout << "Enter points as <x,y> pair\n"; for (int i = 0; i < n; i++) { int x, y; cin >> x >> y; arr.push_back(vector<int>{ x, y }); } cout << "maximum no of points on the same line: " << maxPoints(arr) << endl; return 0; }

**Output:**

Enter number of points 6 Enter points aspair 1 1 3 3 5 6 7 4 4 4 -1 -1 maximum no of points on the same line: 4

Also tagged in: Amazon

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions