Glad that you created this channel for uploading more solution videos. Some solutions which should be on youtube just aren't there. And some of those which are available are hard to understand. Thats why I always look out for your video solution first. Thanks for everything. I hope you're able to manage.
Why a second channel? Whats the purpose of the first channel if all new leetcode vids will be here? Just wondering, I love your content and I subbed to this one too
Saw this solution posted in the discussions by another user. Parallel lines have same slope which would make this fail. Surprised that this works. Probably works because a new dictionary is created every loop. 🤔
I believe there could also be issues wrt floating point precision if the slope value is high enough and the real difference in slopes between two different lines is relatively small enough. This could lead to false collisions where slightly different slopes get the same floating point value and we miscount the coincident points. For this reason it might be better to use a tuple (numerator: int, denominator: int) as hashmap key and make sure to reduce these as far as possible using gcd.
Is this an accepted solution by Leetcode? What about the y-offset? Shouldn't that make this solution not work? The formula that describes a straight line is _y = kx + m_ , where _k_ is the slope and _m_ is the offset at x = 0. It is possible to have two different lines with the same slope, but different offset. For example, the line through the points [0, 0] and [1, 2] (y = 2k) will have the exact same slope as a line through [1, 0] and [1, 3] (y=2k+1), but there is still no way to draw a line through all 4 points, since they have different offsets. Am I missing something here? Or is this just a fairly poorly test by LeetCode?
You are right, both slope and y-intercept are required to uniquely determine a line. I think we have to keep something like "slope-yintercept" format in the hashmap to get it right in other platforms where there are stronger testcases.
code is incomplete, here is a solution: var maxPoints = function(points) { const propIdxMap = new Map() for(let i = 0; i { const indiSet = new Set(n) max = Math.max(indiSet.size, max) } ) return max };
Like @two697 said, the loop with j considers p1 as a common point. So p1 point is common and slope is the same means the points lie on the same line that passes through p1. Also, don't forget that we are looping through all the points so we'll also get the case where the pair of p2 and p3 is considered, excluding p1. It's already established that p1 and p2 are on the same line, so p2 and p3 have to be as well if the slope is the same.
To account for the slope, use the x intercept in the count map. The x intercept is where y = 0, so 0 = slope*x + b, or -slope*x = b. Then using the slope and intercept you'll get the actual answer
When we obtain slope (rise / run) as a key, it looks like we are storing a decimal/floating number. When we store a floating number as a hash table key wouldn't we run into a floating number precision? Aren't computers really bad at handling floating number arithmetics? We might have two slopes that round to the same number. Like two slopes that a very close in decimal will round to the same slope; that necessarily isn't the same line with the same points.
Im from a math background before i began coding and this is my first hard i tried. This wasnt too bad! One issue, y =mx PLUS B. The slops can be the same and not be on the same line, they could be adjacent. Did LC mess that up?
is this complete solution? yes i know it passes testcases sir but line has two parameter slope and constant as by high school maths, y=mx+c . so two lines with same slope is parallel but need not to be same straight line. we haven't considered c.
we are forming pairs by keeping 1 point as fixed. so if we get same slope for 2 pairs, note that 1 point is the same in both pairs. notice on line 10 we are creating a new hash map every time for the fixed point. hence there will never be a case where slope is same but y intercept is not
Hii Neetcode, Congrats for your new channel. I have an enhancement request for you. It would be great if we have a text box column near the code column of the problems page in the site. It will help us to write some hints or notes for that problem for future reference. Hope you read this comment.
Thank you for your great explanation, but you should update your solution because it will fail in the new test cases, as two different lines may have the same slope with two different y_intercept
I don't know how your line 13 p2[0] == p1[0] worked out. Because if your p2[0] = -2 and your p1[0] = 2 then adding them produces 0 ( Error, can't divide by 0 ). This is what I did to fix that # Create a variable to store the longest line we could get longest_straight_line = 1 # Go through each pair in the list and find the slope for point_pair_1 in range(len(points)): # With the current point we are at, try to find the number of same slopes we can get same_slope_points = {} for point_pair_2 in range(point_pair_1 + 1, len(points)): y1 = points[point_pair_1][1] y2 = points[point_pair_2][1] x1 = points[point_pair_1][0] x2 = points[point_pair_2][0] # If adding the two x axis don't result in 0. That means they are on same "x" axis. (2,1)(3,1)(4,1) if (x2 - x1 != 0): slope = (y2 - y1) / (x2 - x1) # Add this slope in the same_slope_points same_slope_points[slope] = same_slope_points.get(slope, 0) + 1 # If on same x axis else: slope = "same" same_slope_points[slope] = same_slope_points.get(slope, 0) + 1 longest_straight_line = max(longest_straight_line, same_slope_points[slope] + 1) return longest_straight_line
why do we need to increment count[slope]+1 line 18, why this is wrong : res = max(res, count[slope]), for me count has been already incremented at line 17
