<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>

# 2:07pm
class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        # Thoughts:
        # - In order for a point to be on the same line, they must have a matching slope
        #   Meaning p1 = p2 + x(slope)
        # - There are a lot of possible slopes
        # - So brute force solution:
        #       - Calculate all slopes between each 2 points
        #       - Try applying those slopes to all the relevant points, and count the number of items that match
        # Edgecases:
        # - Slope is not an integer
        # - Can points not be integers?:    NO
        # - Dont' want to accidentally calculate the opposite slope by iterating backwards
        # 
        # Approach 1:
        #   Sort the points by x coord (so we don't get opposite slopes)                                O(nlogn)
        #   Iterate all combination of points with later points to calc possible slopes at each point   O(n^2)
        #   Combine slopes with points and compare (use % operation)    Iterate over each obtained slope once, then apply it to all points, so O(n^3)
        #   How do I reduce slopes?
        # Approach 2:
        #   Is there a faster/cleaner way to calculate all possible slopes?
        #   What if I tried applying the operations out of order?
        #   Take the mod of all x's from 1-max(x)
        #   Take the mod of all y's from 1-max(y)
        #   Try to match them up?
        #   That sounds interesting. Let's write out some pseudocode
        # Approach 3: Saw in someone's solution
        #   Create a line from every combination of 2 data points. 
        #   Convert line to y-intercept form
        #   Line that is created the most often is the answer
        count = {}
        visited = {}
        maxCount = 0
        if not points:
            return 0
            
        if len(points) == 1:
            return 1

        points.sort(key=lambda a: a[0]) # Sort by ascending x value
        for i in range(len(points)):
            for j in range(i+1, len(points)):
                x1, y1 = points[i]
                x2, y2 = points[j]
                if x2 == x1:
                    slope = 'inf'
                    yInt = x1   # No y-intercept. So put x-int instead
                else:
                    slope = (y2-y1)/(x2-x1)
                    yInt = y1 - x1*slope
                if slope not in count:
                    count[slope] = {}

                if slope not in visited:
                    visited[slope] = {}
                # Only concern here is how sloppy python is with floats.
                # I don't know if using floats as keys is a good idea.
                
                # If the start and endpoint have both had this slope before, don't count them again
                if i not in visited[slope] or j not in visited[slope]:
                    count[slope][yInt] = count[slope].get(yInt, 1) + 1
                    maxCount = max(maxCount, count[slope][yInt]) 
                    visited[slope][i] = True
                    visited[slope][j] = True

        return maxCount



33953