Leetcode 149 - Maximum Points on a Line - Python

NeetCodeIO · Intermediate ·⚡ Algorithms & Data Structures ·3y ago

Key Takeaways

The video demonstrates a solution to the LeetCode problem 'Maximum Points on a Line' using a hash map to count points with the same slope and a brute force approach, with the implementation in Python using collections.defaultdict.

Full Transcript

hey everyone welcome back and let's write some more neat code today so today let's solve the problem Max points on a line The Prompt is pretty simple we're given an array of points that exist on some two-dimensional grid with an x-axis and a y-axis and we want to return the maximum number of points that lie on the same straight line so in this case we're just given three points and all of them happen to lie on the straight line now the first observation that you need to make is how do you know if points are on the same line visually you can kind of tell we need the slope to determine that we know that these two points are well pretty much any two points that we're given are going to be on the same line like no matter where they're located we can connect them via a straight line but when we introduce a third point we have to make sure that it intersects this line how do we know that well it has to be on the same slope as these points and I personally think that leak code's solution kind of over complicates this problem so I'll be giving my own variation which I think is slightly more simple but that's kind of the main idea here the slope is what matters here now even after realizing this we can come up with two solutions one is going to be the slightly less optimal solution it's going to be n cubed but we can make a simple observation which can get this to be more efficient which will be N squared let me show you how so the most Brute Force solution would be to go with every single possible pair of points because we know a pair of points is going to give us a slope and then we have a slope so then what we do is go to every other point in the Grid in this case there's only one but you know there could have been a bunch of other points and we go through every single one of these points and we would then calculate the slope with this point how would we do that well first we'd have to calculate it with this one and then we'd also have to calculate it with that one and if the slope was the same then we would say okay this point also lies along the same line in this case it does not though uh but this point would because this point uh using this point has the same slope and then using this point also has the same slope so therefore it lies on the same line now the problem with this approach is first of all we're going through every pair of points we're going to have one outer loop like a for Loop that goes through every single point then for every n of the points let's assume that there's n of them and then we'll have another inner loop which will give us uh go through every other point and this will give us the pair of points here and then we'll have a third Loop that goes through all the rest of the points so this is going to be n cubed basically we can fix this by using a hash map and instead what we're gonna do conceptually at least is say that we're going through every single point on the grid and we're considering is this the point that happens to lie on the longest line is this the one that's the question we're asking how do we determine that well for this point we go through every other point and calculate the slope and using that slope we're going to count how many points have the same slope running through it quickly on this example is going to be simple because what we're going to find is that let's say this is our first point and then we go through every other point let's say this one first we see that the slope between these points is equal to one so we say that for all points with a slope of one we have two points that do that then we're going to go to this third point and we're going to see what's the slope between these two points it's also one so then we say we have three points that have a slope of one now let's say we had another point over here over at y equals five we'd see what's the slope between these points well it's two so we'd say we have two points for a slope of two we have two points that lie on that line now you tell me which one of these is the maximum three so in that case we would return three but actually in this case we haven't finished the algorithm because all we asked so far is what's the longest line we can create with this point we also have to ask that same question for this point and this point and this point two quick things that I haven't covered yet is how do we actually calculate the slope I'll show that in the coding section but it's pretty basic algebra you might have forgotten it but that's probably not the most complicated thing about this problem the last thing is when we do calculate the slope what about when we do it with points that are vertical like these two because we're going to get a denominator of zero because the way we calculate the slope is we take Y2 minus y1 X2 minus X1 and since these two points have the same x value we're going to have a denominator of zero that's going to give us a problem so for the slope in that case I'm just going to use the value Infinity so that's how we'll know which points lie on the same vertical line so now let's code it up I left a few comments here just to kind of give a summary of what we're going to do so the first thing I'm going to do is initialize the result to equal one because we're guaranteed that we're given at least one point and then we're going to go ahead and start iterating through every single point so we're going to go through our entire list of points so this is point one it's at index I we're asking is this the point that lies on the longest line to determine that we need a hash map which is kind of what I was alluding to earlier which I'm gonna in Python use collections.defaultdict and then pass an INT into it because that will by default if we like go like this now count of four and then we increment it by one this will set count of four equal to one because what the default dick does is it if you use a key that hasn't already been inserted into the hashmap it will by default give it a value of zero so then adding one to zero sets it equal to one which is kind of what we would expect then I'm going to iterate through every other point so I'm going to take I plus 1 and every other point basically after I P2 is going to be the point at index J and I'm going to have a conditional because we want to know if the two points lie on the same X point so if P2 of 0 is equal to P 1 of 0. that means they lie on the same x value so we're just going to say the slope is equal to Infinity otherwise we actually have to calculate the slope not too bad Y2 which is the P2 point at index 1 minus P1 at index one this divided by the difference of the x value so P2 of 0 minus P1 of 0 and then we're going to set our count using this slope value that we calculated and incrementing it by one basically we found another point that lies on this line with this slope now this is kind of slightly different than what I showed in the drawing explanation because if we found a pair of points on the same line now with the same slope initially this is just going to be set to one well that's okay because now when we actually update the result we're going to say the result is equal to the maximum of what it currently is or it's going to be the count of the current slope value that we just calculated plus one and the reason I'm doing the plus one is we pretty much have to because we're counting the number of total points whereas here we're getting like one less than that and believe it or not that pretty much is it so let's go ahead and return the result and quickly run this to make sure that it works and of course we made a simple mistake we're not going to be iterating through n our input is actually points I don't know how I messed that up but now let's run it and make sure that it works and as you can see yes it does and it is pretty efficient if this was helpful please like And subscribe if you'd like to see code solutions for languages other than python check out neat code.io it's got a ton of free resources that'll help you prepare for coding interviews thanks for watching and hopefully I'll see you pretty soon

Original Description

🚀 https://neetcode.io/ - A better way to prepare for Coding Interviews 🥷 Discord: https://discord.gg/ddjKRXPqtk 🐦 Twitter: https://twitter.com/neetcode1 🐮 Support the channel: https://www.patreon.com/NEETcode ⭐ BLIND-75 PLAYLIST: https://www.youtube.com/watch?v=KLlXCFG5TnA&list=PLot-Xpze53ldVwtstag2TL4HQhAnC8ATf 💡 DYNAMIC PROGRAMMING PLAYLIST: https://www.youtube.com/watch?v=73r3KWiEvyk&list=PLot-Xpze53lcvx_tjrr_m2lgD2NsRHlNO&index=1 Problem Link: https://leetcode.com/problems/max-points-on-a-line/ 0:00 - Read the problem 0:30 - Drawing Explanation 5:05 - Coding Explanation leetcode 149 #neetcode #leetcode #python
Watch on YouTube ↗ (saves to browser)
Sign in to unlock AI tutor explanation · ⚡30

Playlist

Uploads from NeetCodeIO · NeetCodeIO · 1 of 60

← Previous Next →
▶ Leetcode 149 - Maximum Points on a Line - Python
Leetcode 149 - Maximum Points on a Line - Python
NeetCodeIO
 2 Design Linked List - Leetcode 707 - Python
Design Linked List - Leetcode 707 - Python
NeetCodeIO
 3 Minimum Time to Collect All Apples in a Tree - Leetcode 1443 - Python
Minimum Time to Collect All Apples in a Tree - Leetcode 1443 - Python
NeetCodeIO
 4 Design Browser History - Leetcode 1472 - Python
Design Browser History - Leetcode 1472 - Python
NeetCodeIO
 5 Number of Good Paths - Leetcode 2421 - Python
Number of Good Paths - Leetcode 2421 - Python
NeetCodeIO
 6 Flip String to Monotone Increasing - Leetcode 926 - Python
Flip String to Monotone Increasing - Leetcode 926 - Python
NeetCodeIO
 7 Maximum Sum Circular Subarray - Leetcode 918 - Python
Maximum Sum Circular Subarray - Leetcode 918 - Python
NeetCodeIO
 8 Find Closest Node to Given Two Nodes - Leetcode 2359 - Python
Find Closest Node to Given Two Nodes - Leetcode 2359 - Python
NeetCodeIO
 9 Concatenated Words - Leetcode 472 - Python
Concatenated Words - Leetcode 472 - Python
NeetCodeIO
 10 Data Stream as Disjoint Intervals - Leetcode 352 - Python
Data Stream as Disjoint Intervals - Leetcode 352 - Python
NeetCodeIO
 11 LFU Cache - Leetcode 460 - Python
LFU Cache - Leetcode 460 - Python
NeetCodeIO
 12 N-th Tribonacci Number - Leetcode 1137
N-th Tribonacci Number - Leetcode 1137
NeetCodeIO
 13 Best Team with no Conflicts - Leetcode 1626 - Python
Best Team with no Conflicts - Leetcode 1626 - Python
NeetCodeIO
 14 Greatest Common Divisor of Strings - Leetcode 1071 - Python
Greatest Common Divisor of Strings - Leetcode 1071 - Python
NeetCodeIO
 15 Shortest Path in a Binary Matrix - Leetcode 1091 - Python
Shortest Path in a Binary Matrix - Leetcode 1091 - Python
NeetCodeIO
 16 Insert into a Binary Search Tree - Leetcode 701 - Python
Insert into a Binary Search Tree - Leetcode 701 - Python
NeetCodeIO
 17 Delete Node in a BST - Leetcode 450 - Python
Delete Node in a BST - Leetcode 450 - Python
NeetCodeIO
 18 Shuffle the Array (Constant Space) - Leetcode 1470 - Python
Shuffle the Array (Constant Space) - Leetcode 1470 - Python
NeetCodeIO
 19 Fruits into Basket - Leetcode 904 - Python
Fruits into Basket - Leetcode 904 - Python
NeetCodeIO
 20 Number of Subarrays of size K and Average Greater than or Equal to Threshold - Leetcode 1343 Python
Number of Subarrays of size K and Average Greater than or Equal to Threshold - Leetcode 1343 Python
NeetCodeIO
 21 Naming a Company - Leetcode 2306 - Python
Naming a Company - Leetcode 2306 - Python
NeetCodeIO
 22 As Far from Land as Possible - Leetcode 1162 - Python
As Far from Land as Possible - Leetcode 1162 - Python
NeetCodeIO
 23 Shortest Path with Alternating Colors - Leetcode 1129 - Python
Shortest Path with Alternating Colors - Leetcode 1129 - Python
NeetCodeIO
 24 Minimum Fuel Cost to Report to the Capital - Leetcode 2477 - Python
Minimum Fuel Cost to Report to the Capital - Leetcode 2477 - Python
NeetCodeIO
 25 Count Odd Numbers in an Interval Range - Leetcode 1523 - Python
Count Odd Numbers in an Interval Range - Leetcode 1523 - Python
NeetCodeIO
 26 Contains Duplicate II - Leetcode 219 - Python
Contains Duplicate II - Leetcode 219 - Python
NeetCodeIO
 27 Path with Maximum Probability - Leetcode 1514 - Python
Path with Maximum Probability - Leetcode 1514 - Python
NeetCodeIO
 28 Add to Array-Form of Integer - Leetcode 989 - Python
Add to Array-Form of Integer - Leetcode 989 - Python
NeetCodeIO
 29 Unique Paths II - Leetcode 63 - Python
Unique Paths II - Leetcode 63 - Python
NeetCodeIO
 30 Minimum Distance between BST Nodes - Leetcode 783 - Python
Minimum Distance between BST Nodes - Leetcode 783 - Python
NeetCodeIO
 31 Design Hashmap - Leetcode 706 - Python
Design Hashmap - Leetcode 706 - Python
NeetCodeIO
 32 Range Sum Query Immutable - Leetcode 303 - Python
Range Sum Query Immutable - Leetcode 303 - Python
NeetCodeIO
 33 Binary Tree Zigzag Level Order Traversal - Leetcode 103 - Python
Binary Tree Zigzag Level Order Traversal - Leetcode 103 - Python
NeetCodeIO
 34 Middle of the Linked List - Leetcode 876 - Python
Middle of the Linked List - Leetcode 876 - Python
NeetCodeIO
 35 Course Schedule IV - Leetcode 1462 - Python
Course Schedule IV - Leetcode 1462 - Python
NeetCodeIO
 36 Single Element in a Sorted Array - Leetcode 540 - Python
Single Element in a Sorted Array - Leetcode 540 - Python
NeetCodeIO
 37 Capacity to Ship Packages - Leetcode 1011 - Python
Capacity to Ship Packages - Leetcode 1011 - Python
NeetCodeIO
 38 IPO - Leetcode 502 - Python
IPO - Leetcode 502 - Python
NeetCodeIO
 39 Minimize Deviation in Array - Leetcode 1675 - Python
Minimize Deviation in Array - Leetcode 1675 - Python
NeetCodeIO
 40 Longest Turbulent Array - Leetcode 978 - Python
Longest Turbulent Array - Leetcode 978 - Python
NeetCodeIO
 41 Last Stone Weight II - Leetcode 1049 - Python
Last Stone Weight II - Leetcode 1049 - Python
NeetCodeIO
 42 Construct Quad Tree - Leetcode 427 - Python
Construct Quad Tree - Leetcode 427 - Python
NeetCodeIO
 43 Find Duplicate Subtrees - Leetcode 652 - Python
Find Duplicate Subtrees - Leetcode 652 - Python
NeetCodeIO
 44 Sort an Array - Leetcode 912 - Python
Sort an Array - Leetcode 912 - Python
NeetCodeIO
 45 Ones and Zeroes - Leetcode 474 - Python
Ones and Zeroes - Leetcode 474 - Python
NeetCodeIO
 46 Remove Duplicates from Sorted Array II - Leetcode 80 - Python
Remove Duplicates from Sorted Array II - Leetcode 80 - Python
NeetCodeIO
 47 Maximum Twin Sum of a Linked List - Leetcode 2130 - Python
Maximum Twin Sum of a Linked List - Leetcode 2130 - Python
NeetCodeIO
 48 Concatenation of Array - Leetcode 1929 - Python
Concatenation of Array - Leetcode 1929 - Python
NeetCodeIO
 49 Symmetric Tree - Leetcode 101 - Python
Symmetric Tree - Leetcode 101 - Python
NeetCodeIO
 50 Check Completeness of a Binary Tree - Leetcode 958 - Python
Check Completeness of a Binary Tree - Leetcode 958 - Python
NeetCodeIO
 51 Construct Binary Tree from Inorder and Postorder Traversal - Leetcode 106 - Python
Construct Binary Tree from Inorder and Postorder Traversal - Leetcode 106 - Python
NeetCodeIO
 52 Find Peak Element - Leetcode 162 - Python
Find Peak Element - Leetcode 162 - Python
NeetCodeIO
 53 Accounts Merge - Leetcode 721 - Python
Accounts Merge - Leetcode 721 - Python
NeetCodeIO
 54 Binary Tree Preorder Traversal (Iterative) - Leetcode 144 - Python
Binary Tree Preorder Traversal (Iterative) - Leetcode 144 - Python
NeetCodeIO
 55 Binary Tree Postorder Traversal (Iterative) - Leetcode 145 - Python
Binary Tree Postorder Traversal (Iterative) - Leetcode 145 - Python
NeetCodeIO
 56 Number of Zero-Filled Subarrays - Leetcode 2348 - Python
Number of Zero-Filled Subarrays - Leetcode 2348 - Python
NeetCodeIO
 57 Minimum Score of a Path Between Two Cities - Leetcode 2492 - Python
Minimum Score of a Path Between Two Cities - Leetcode 2492 - Python
NeetCodeIO
 58 Sqrt(x) - Leetcode 69 - Python
Sqrt(x) - Leetcode 69 - Python
NeetCodeIO
 59 Successful Pairs of Spells and Potions - Leetcode 2300 - Python
Successful Pairs of Spells and Potions - Leetcode 2300 - Python
NeetCodeIO
 60 Optimal Partition of String - Leetcode 2405 - Python
Optimal Partition of String - Leetcode 2405 - Python
NeetCodeIO

This video teaches how to solve the LeetCode problem 'Maximum Points on a Line' using a hash map and brute force approach in Python, with a focus on systems design and algorithms. The solution is efficient and works as expected.

Key Takeaways
  1. Initialize result to 1
  2. Iterate through each point
  3. Calculate slope between points
  4. Use hash map to count points on the same line
  5. Update result with maximum count
  6. Run the code to test the solution
  7. Fix a simple mistake in the code
💡 Using a hash map to count points with the same slope is an efficient way to solve the problem

Related AI Lessons

⚡
Bloom Filters, Explained Properly
Learn how Bloom filters work and their benefits, including tiny memory and blazing speed, in exchange for potential false positives.
Dev.to · Daksh Gargas
 ⚡
Prefix Sums: The Preprocessing Trick That Makes Range Queries Instant
Learn how prefix sums enable instant range queries in arrays, boosting performance in various applications
Medium · Programming
 ⚡
I Thought I Was Ready for the Interview — Then One Simple Math Question Destroyed Me
A simple math question can destroy a developer's interview, highlighting the importance of being prepared for unexpected questions
Medium · Programming
 ⚡
Week 2(Day 10): LeetCode Two Pointers(slow & fast): Remove Duplicates from Sorted Array (Brute…
Learn to remove duplicates from a sorted array using the two pointers technique, improving from brute force to optimized solutions
Medium · Python

Chapters (3)

Read the problem
0:30 Drawing Explanation
5:05 Coding Explanation
Up next
Stump Grinder Carbide Wheel Grinds Hardwood To Chips
Innoforge Studio
Watch →