Given two arrays X[] and Y[] of points where (X_{i}, Y_{i}) represents a point on the X-Y plane. Your task is to complete the function maxPoints which returns an integer denoting the maximum number of points that lie on the same straight line.
Example 1:
Input:
X[] = {1, 2, 3}
Y[] = {1, 2, 3}
Output: 3
Explanation:
The points are (1,1), (2,2) and (3,3).
Example 2:
Input:
X[] = {1, 3, 5, 4, 2, 1}
Y[] = {1, 2, 3, 1, 3, 4}
Output: 4
Explanation:
The points are- 
(1,1),(3,2),(5,3),(4,1),(2,3),(1,4)
Your Task:
You don't need to read input or print anything. Your task is to complete the function maxPoints() which takes two lists of coordinates as input and returns the maximum number of points that lies on the same line.
Expected Time Complexity: O(N^{2})
Expected Auxiliary Space: O(N)
Constraints:
1 <= N <= 300
-10^{4} <= x_{i}, y_{i} <= 10^{4}^{ }

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Mathematics

Starter code: #Back-end complete function Template for Python 3

class Solution:
    def maxPoints(self, X, Y, N):
        #code here


Solutions:
class Solution:

	def maxPoints(self, x, y, n):
		points = []
		for i in range(n):
			points.append((x[i], y[i]))
		n = len(points)
		if n < 3:
			return n
		max_val = 0
		for i in points:
			d = {}
			dups = 0
			cur_max = 0
			for j in points:
				if i != j:
					if j[0] == i[0]:
						slope = 'inf'
					else:
						slope = float(j[1] - i[1]) / float(j[0] - i[0])
					d[slope] = d.get(slope, 0) + 1
					cur_max = max(cur_max, d[slope])
				else:
					dups += 1
			max_val = max(max_val, cur_max + dups)
		return max_val


from collections import Counter

class Solution:

	def maxPoints(self, X, Y, N):
		if N == 1:
			return 1
		ans = 0
		for i in range(N):
			cnt = Counter()
			temp = 0
			for j in range(N):
				if i == j:
					continue
				if X[j] == X[i]:
					temp += 1
				else:
					cnt[(Y[j] - Y[i]) / (X[j] - X[i])] += 1
			ans = max(ans, cnt.most_common(1)[0][1] + 1, temp + 1)
		return ans


class Solution:

	def getSlope(self, a0, a1, b0, b1):
		x = b0 - a0
		y = b1 - a1
		if x == 0:
			return None
		return y / x

	def maxPoints(self, X, Y, N):
		if N <= 1:
			return N
		ans = -float('inf')
		for i in range(N):
			h = {}
			for j in range(N):
				if i != j:
					slope = self.getSlope(X[i], Y[i], X[j], Y[j])
					h[slope] = h.get(slope, 0) + 1
					ans = max(ans, h[slope])
		return ans + 1


class Solution:

	def maxPoints(self, X, Y, N):
		s = []
		for i in range(len(X)):
			s.append((X[i], Y[i]))
		maxi = 0
		for i in s:
			d = {}
			dup = 0
			curr_max = 0
			for j in s:
				if i != j:
					if i[0] == j[0]:
						slope = 'inf'
					else:
						slope = float(j[1] - i[1]) / float(j[0] - i[0])
					if slope not in d:
						d[slope] = 1
					else:
						d[slope] = d.get(slope) + 1
					curr_max = max(curr_max, d[slope])
				else:
					dup += 1
			maxi = max(maxi, curr_max + dup)
		return maxi


import math
from collections import defaultdict

class Solution:

	def maxPoints(self, X, Y, N):
		points = []
		for (x, y) in zip(X, Y):
			points.append((x, y))
		n = len(points)
		if n == 1:
			return 1
		result = 2
		for i in range(n):
			cnt = defaultdict(int)
			for j in range(n):
				if j != i:
					cnt[math.atan2(points[j][1] - points[i][1], points[j][0] - points[i][0])] += 1
			result = max(result, max(cnt.values()) + 1)
		return result


class Solution:

	def maxPoints(self, X, Y, N):
		if N < 3:
			return N
		res = -1
		for i in range(N):
			same = 1
			slope = {'inf': 0}
			for j in range(i + 1, N):
				(dx, dy) = (X[j] - X[i], Y[j] - Y[i])
				if dx == dy == 0:
					same += 1
				elif dx == 0:
					slope['inf'] += 1
				else:
					k = float(dy) / float(dx)
					if k not in slope:
						slope[k] = 1
					else:
						slope[k] += 1
			res = max(res, max(slope.values()) + same)
		return res