Return to Question

The only solution I can think about is in \$O(n^2)\$. It consist of calculating the slope between every coordinate: Given that if \$\frac{y_2-y_1}{x_2 –x_1} = \frac{y_3-y_2}{x_3-x_2}\$ then these three points are on the same line. I have been trying to think about a DP solution but haven't been able to think about one.

Here is the current code:

def points_in_lins(l):
 length = len(l)
 for i in range(0,length -1):
 gradients = {}
 for j in range(i+1, length):
 x1, y1 = l[i]
 x2, y2 = l[j]
 if x1 == x2:
 m = float("inf")
 else:
 m = float((y2 -y1) / (x2 - x1))
 if m in gradients:
 gradients[m] += 1
 if gradients[m] == 3:
 return(True)
 else:
 gradients[m] = 1
 return(False)

I was doing some preparation for coding interviews and I came across the following question:

Given a list of coordinates "x y" return True if there exists a line containing at least 4 of the points (ints), otherwise return False.

Here is the current code:

def points_in_lins(l):
 length = len(l)
 for i in range(0,length -1):
 gradients = {}
 for j in range(i+1, length):
 x1, y1 = l[i]
 x2, y2 = l[j]
 if x1 == x2:
 m = float("inf")
 else:
 m = float((y2 -y1) / (x2 - x1))
 if m in gradients:
 gradients[m] += 1
 if gradients[m] == 3:
 return(True)
 else:
 gradients[m] = 1
 return(False)

I was doing some preparation for coding interviews and I came across the following question:

Given a list of coordinates "x y" return True if there exists a line containing at least 4 of the points (ints), otherwise return False.

Here is the current code:

def points_in_lins(l):
 length = len(l)
 for i in range(0,length -1):
 gradients = {}
 for j in range(i+1, length):
 x1, y1 = l[i]
 x2, y2 = l[j]
 if x1 == x2:
 m = float("inf")
 else:
 m = float((y2 -y1) / (x2 - x1))
 if m in gradients:
 gradients[m] += 1
 if gradients[m] == 3:
 return(True)
 else:
 gradients[m] = 1
 return(False)