<p>Given an array of <code>points</code> where <code>points[i] = [x<sub>i</sub>, y<sub>i</sub>]</code> represents a point on the <strong>X-Y</strong> plane, return <em>the maximum number of points that lie on the same straight line</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/02/25/plane1.jpg" style="width: 300px; height: 294px;" />
<pre>
<strong>Input:</strong> points = [[1,1],[2,2],[3,3]]
<strong>Output:</strong> 3
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/02/25/plane2.jpg" style="width: 300px; height: 294px;" />
<pre>
<strong>Input:</strong> points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
<strong>Output:</strong> 4
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= points.length &lt;= 300</code></li>
	<li><code>points[i].length == 2</code></li>
	<li><code>-10<sup>4</sup> &lt;= x<sub>i</sub>, y<sub>i</sub> &lt;= 10<sup>4</sup></code></li>
	<li>All the <code>points</code> are <strong>unique</strong>.</li>
</ul>


"""
+7 min on timer btw

need to be able to determine which existing straight lines a new point is on, then we can update thos e counters.
finally, we can iterate over all teh lines and max their sizes.


maybe we can keep track of unique lines by its left and right most points (poitnts with min and max x).


then for every thing we can iterate over all points and update their counte if the point falls within those two points. we also update the point thing if we find that the new point is further left


N = len(points)
This would be an O(N^3), O(N^2) space solution as there can be up to N^2 unique staright lines as every single point can be joing with any of the other n points to make a new line.


if there is a duplicate point, that is coinsideerd an addiontal point for whatever line the existing point is.



we can have up to 2* (2*10^4) distinct lines that a point can fall on (all lines intersecting with
all integer points on x-axis, and all lines inetersiection with all itngeter points o axis)

what if we keep a hash table of which points intersectwith each distinc point on the x or 
y axis and 

    a line can be uniquitely idetnifeid with its m and b values in y = mx + b

IDEA:

first, iterate through the ponitns and keep count of # of poitns at each
unique (x,y) value.

then iterate over this map and for each point, iterate over all other points and 
see if the points have a point at that slope. Basiaal,y we need a map that maps (x,y) values to
a dictionary of slopes to the size of the lines with that sloe. if therei s one, we add to that value in both points maps with the count of the current point, if not we create a lnew line entry and make it the sume of teh count of points between the two points. everytime we do an updat, updateh tem ax.

This is an O(N^2) solution  with O(N^2 ) space (because each point can have up to n unique-sloped lines)

"""
import dataclasses 
from typing import Dict, List
@dataclasses.dataclass
class Point:

    x : int
    y : int
    lines : Dict[float , int]  # mapping slope to # of points in that line 

    def get_slope(self, other_point : "Point"):
        if other_point.x - self.x == 0:
            return float("inf")
        return (other_point.y- self.y) / (other_point.x- self.x) 

    def update_line_size(self, other_point : "Point") -> int:
        # update line size of lines that meet the other point, returning the new # of points in the line after adding the other point 
        slope = self.get_slope(other_point)

        if slope in other_point.lines:
            
            other_point.lines[slope] += 1
            #self.lines[slope] = other_point.lines[slope]
        else:
            other_point.lines[slope] = 2
            #self.lines[slope] = 2
        
        
        return other_point.lines[slope]





def get_point_counts(points):
    out = []
    for pos in points:
        x,y = pos
        out.append(Point(x =x, y=y, lines = {}))

    return out


class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        if len(points) == 1:
            return 1
        points : List[Point] = get_point_counts(points) # tuple of points
        ans = 0
        for i in range(len(points)):
            for j in range(i): # only iterate over previous points so we dont overcount

                ans = max(ans, points[i].update_line_size(points[j]))

        return ans
19750