Builds on Hash Map, which you haven’t finished yet.
Canonical-Form Hashing (Normalize Before You Count)
You're handed a list of 2D points, each entry points[i] = [xi, yi] marking a spot on the X-Y plane. Work out the size of the largest subset of those points that all sit on one common straight line.
Canonical Key
integers (a, b) ➔ Euclidean reduction ➔ normalized coprime factors| 1 | import math |
| 2 | from collections import defaultdict |
| 3 | |
| 4 | def max_points_on_line(points: list[list[int]]) -> int: |
| 5 | """Maximum points collinear on a plane using GCD slope hashing. |
| 6 | Time: O(N^2) | Space: O(N) |
| 7 | """ |
| 8 | # 1. Handle Trivial Inputs: |
| 9 | # Any 0, 1, or 2 points are always collinear, so the general counting |
| 10 | # below is skipped for those sizes. |
| 11 | if len(points) <= 2: |
| 12 | return len(points) |
| 13 | |
| 14 | max_pts = 0 # largest count of collinear points found across all anchors |
| 15 | |
| 16 | # 2. Anchor on Each Point in Turn: |
| 17 | # slopes counts, for the current anchor points[i], how many later points |
| 18 | # share each direction from it; a fresh dict per anchor keeps directions |
| 19 | # from different anchors from being mixed into the same count. |
| 20 | for i in range(len(points)): |
| 21 | slopes: dict[tuple[int, int], int] = defaultdict(int) |
| 22 | x1, y1 = points[i] |
| 23 | |
| 24 | for j in range(i + 1, len(points)): |
| 25 | x2, y2 = points[j] |
| 26 | dx, dy = x2 - x1, y2 - y1 |
| 27 | g = math.gcd(dx, dy) |
| 28 | |
| 29 | # 3. Reduce the Direction to a Canonical Key: |
| 30 | # Dividing dx and dy by their gcd keeps the same direction in |
| 31 | # lowest terms, then flipping the sign so dy is positive (or dy |
| 32 | # == 0 with dx positive) makes opposite vectors of one line hash alike. |
| 33 | slope = (dy // g, dx // g) |
| 34 | if slope[0] < 0 or (slope[0] == 0 and slope[1] < 0): |
| 35 | slope = (-slope[0], -slope[1]) |
| 36 | |
| 37 | # 4. Count and Track the Best Line Through This Anchor: |
| 38 | # Every point sharing a key lies on the same line through |
| 39 | # points[i]; the + 1 below counts the anchor point itself. |
| 40 | slopes[slope] += 1 |
| 41 | max_pts = max(max_pts, slopes[slope] + 1) |
| 42 | |
| 43 | return max_pts |
points[i], two points share a key in slopes exactly when they lie on the same line through points[i].Before counting, turn each item into a key that is equal exactly when the items should count as equal; here the item is the direction from points[i] to points[j], and its key is (dy // g, dx // g) with g = gcd(dx, dy), sign fixed. Two directions lie on the same line through points[i] exactly when their reduced integer pairs match, and integers compare exactly, so two different directions never share one bucket, as rounded float slopes can when the coordinates are large. The trap is the sign: (1, -2) and (-1, 2) are the same direction, so force dy positive (or dy == 0 with dx positive) before counting slope, or one line is counted as two.
See it run
Canonical Key, step by step
anchor i -j -max_pts 0
Each column is one point, written as x,y. The key row and the count row belong to the current anchor only. Keys are written as dy,dx.
anchorthe point points[i] that every direction is measured fromjthe point points[j] whose direction from the anchor is computedkeythe pair (dy // g, dx // g) stored under that pointcountslopes[key] after this point is counted
Start: max_pts = 0. Each point in turn becomes the anchor points[i], with a fresh empty slopes.
Gotcha 1 of 4
- The trap
Gotcha 1: Leaving the sign of
(dy // g, dx // g)unfixedMistakeslope = (dy // g, dx // g)Fixslope = (dy // g, dx // g) if slope[0] < 0 or (slope[0] == 0 and slope[1] < 0): slope = (-slope[0], -slope[1])What happens:
math.gcdnever returns a negative number. Sody // ganddx // gkeep the signs ofdyanddx. Forpoints = [[0, 0], [1, 1], [-1, -1]], the anchor[0, 0]gives[1, 1]the key(1, 1). It gives[-1, -1]the key(-1, -1), although both points lie on the same line. That one line is then counted in two buckets. The fix flips the pair so thatdyis positive, ordy == 0anddxis positive.Example: points = [[0, 0], [1, 1], [-1, -1]]Mistake: returns 2Fix: returns 3
- The key is the item itself or its sorted letters, as in Group Anagrams (LC 49): no division or sign fix is needed to make equal items look equal. See Hash Map
Deep Dive
What a canonical key must guarantee
A canonical key is a standard form of an item. Two items get the same key exactly when you want to count them as equal. The key must satisfy two rules.
Rule 1: equal items give equal keys. Rule 2: different items give different keys. If rule 1 fails, one group is split into two buckets and each bucket is too small. If rule 2 fails, two different groups share one bucket and the count is too large.
In Max Points on a Line (LC 149), the item is the direction from points[i] to points[j]. The vectors (dy, dx) = (2, 2), (1, 1) and (3, 3) are all the same direction. Dividing both numbers by g = math.gcd(dx, dy) gives (1, 1) for all three. The vector (2, 1) is a different direction, and it stays (2, 1).
Other problems use other normal forms. Group Shifted Strings (LC 249) uses the differences between neighbouring letters, modulo 26, so "abc" and "bcd" both get (1, 1). Number of Distinct Islands (LC 694) subtracts the first cell of the island from every cell, so a moved island gets the same key.
Why the sign fix is needed, traced on four points
math.gcd never returns a negative number. So dy // g and dx // g keep the signs of dy and dx. The vector from [0, 0] to [-1, -1] gives (-1, -1). The vector from [0, 0] to [2, 2] gives (1, 1). Both points are on the same line through the anchor, but the pairs differ. The sign fix flips a pair when dy is negative, or when dy is 0 and dx is negative. After the flip, both pairs are (1, 1).
Trace for points = [[0, 0], [2, 2], [-1, -1], [1, 2]]. Anchor 0 gives the keys (1, 1), (1, 1) after the flip, and (2, 1). So slopes[(1, 1)] = 2 and max_pts = 3. Anchor 1 gives (1, 1) after a flip for point 2, and (0, 1) for point 3. For point 3, dx = -1 and dy = 0, so the raw pair (0, -1) is flipped to (0, 1). Anchor 2 gives (3, 2). The answer is 3.
The loop for j starts at i + 1. A line is counted from its first point in list order. That point is an anchor at some i, and every other point of the line has a larger index. So the largest slopes[slope] + 1 over all anchors is the size of the best line. The + 1 counts the anchor itself.
Why slopes is created again for every anchor
A key is only a direction. A direction names one line only when every point is measured from the same anchor. Two parallel lines have the same direction but different anchors.
If slopes were shared by all anchors, the count for one direction would add points from two parallel lines. Take points = [[0, 0], [1, 0], [5, 5], [6, 5]]. A shared slopes adds the horizontal pair from anchor 0 and the horizontal pair from anchor 2 into one count, slopes[(0, 1)] = 2. The result is 3. The correct answer is 2. The blueprint creates an empty slopes inside the loop over i, so each count belongs to one anchor.
Only one slopes exists at a time, and it holds at most N - 1 keys. So the extra space is O(N).
Integer keys, floats and the cost
A float dy / dx has two problems. A vertical line has dx = 0, and the division raises ZeroDivisionError. A float also rounds. For 94911150 / 94911151 and 94911151 / 94911152, Python returns equal floats, although the two fractions are different. Two different directions would then share one bucket.
The pair (dy // g, dx // g) has neither problem. A vertical line becomes (1, 0). Integers in Python have no size limit, and two pairs are equal only when the fractions are equal.
The loops visit every pair (i, j) with i < j once, which is N * (N - 1) / 2 pairs. Each pair costs one gcd and one dictionary update. The time is O(N^2) and the space is O(N), as in the blueprint docstring. LeetCode limits the input to 300 points, so the work is at most 44,850 pairs.
60-Second Pitch
"The task is to find the most points on one line. I make every point the anchor in turn. For each later point, I compute the direction from the anchor and reduce it with the gcd, so (2, 2) and (1, 1) become the same pair. I also fix the sign, so that a direction and its opposite give one key. Then one dictionary count per anchor tells me how many points share a line through that anchor. The key is a pair of integers, so there is no rounding and no division by zero for vertical lines. The time is O(N^2) and the space is O(N). The same idea works for any problem where items must be put into a standard form before they are counted."
Common Questions
- Why do you divide
dxanddyby their gcd? Different vectors can point in the same direction. For example,
(2, 2),(1, 1)and(3, 3)all lie on the same line through the anchor. The gcd reduces each pair to its smallest integers, so all of them become(1, 1)and share one key.- Why do you fix the sign of the key?
math.gcdis never negative, so the signs ofdyanddxstay. The vector to[-1, -1]and the vector to[1, 1]lie on one line but give(-1, -1)and(1, 1). The fix makesdypositive, ordxpositive whendyis 0. Then both give(1, 1).- Why not use the float
dy / dxas the key? A vertical line has
dx = 0, so the division fails. Floats also round, and two different slopes can become equal floats when the coordinates are large. An integer pair is exact and has no division.- What is the time and space complexity?
The time is O(N^2). There are about N^2 / 2 pairs and each pair costs one gcd and one dictionary update. The space is
O(N), becauseslopesis replaced for each anchor and holds at most N - 1 keys.- How do you handle vertical lines and repeated points?
A vertical line has
dx = 0. Theng = abs(dy), and the key is(1, 0)after the sign fix, with no division bydx. Repeated points givedx = dy = 0, which makes the gcd 0. Count those copies in a separate variable and add it to the best line through the anchor.
SWE Reasoning
Spot it
- The problem groups or counts items that are equal after a change of form, such as points on one line, strings that are shifts of each other, or shapes that match after a move.
- Comparing every group of items directly would take O(N^3) time or more. Hashing one key per item or per pair takes O(N^2) time or less.
- Max Points on a Line (LC 149), Number of Distinct Islands (LC 694) and Group Shifted Strings (LC 249) all ask which items share a standard form.
- A float would be the natural key, but exact comparison is needed.
The invariant, step by step
- For anchor
points[i],slopesis empty andmax_ptsholds the best count from earlier anchors. - For each later point
points[j], the code computesdxanddyand divides both byg = math.gcd(dx, dy). - The sign fix makes
dypositive, ordxpositive whendyis 0. Now every vector on the same line through the anchor has the same key. slopes[slope] += 1counts one more point on that line.slopes[slope] + 1is the number of points on that line, including the anchor.max_ptskeeps the largest value.- After all anchors,
max_ptsis the size of the largest set of collinear points. Collinear means on one straight line.
Traps
- No sign fix. The points
[1, 1]and[-1, -1]give(1, 1)and(-1, -1)from anchor[0, 0]. One line is counted in two buckets, andmax_points_on_line([[0, 0], [1, 1], [-1, -1]])returns 2 instead of 3. - One shared
slopes. Parallel lines from different anchors add into one bucket. For[[0, 0], [1, 0], [5, 5], [6, 5]]the result is 3 instead of 2. - Float slope. A vertical line raises
ZeroDivisionError. Large coordinates can make two different slopes round to one float. - Repeated points. If two points are equal,
dxanddyare both 0,math.gcd(0, 0)is 0 and the division raisesZeroDivisionError. LC 149 promises distinct points. A variant needs a separate count of copies.
Practice
Builds on Hash Map, which you haven’t finished yet.
Canonical-Form Hashing (Normalize Before You Count)
You're handed a list of 2D points, each entry points[i] = [xi, yi] marking a spot on the X-Y plane. Work out the size of the largest subset of those points that all sit on one common straight line.
Canonical Key
integers (a, b) ➔ Euclidean reduction ➔ normalized coprime factors| 1 | import math |
| 2 | from collections import defaultdict |
| 3 | |
| 4 | def max_points_on_line(points: list[list[int]]) -> int: |
| 5 | """Maximum points collinear on a plane using GCD slope hashing. |
| 6 | Time: O(N^2) | Space: O(N) |
| 7 | """ |
| 8 | # 1. Handle Trivial Inputs: |
| 9 | # Any 0, 1, or 2 points are always collinear, so the general counting |
| 10 | # below is skipped for those sizes. |
| 11 | if len(points) <= 2: |
| 12 | return len(points) |
| 13 | |
| 14 | max_pts = 0 # largest count of collinear points found across all anchors |
| 15 | |
| 16 | # 2. Anchor on Each Point in Turn: |
| 17 | # slopes counts, for the current anchor points[i], how many later points |
| 18 | # share each direction from it; a fresh dict per anchor keeps directions |
| 19 | # from different anchors from being mixed into the same count. |
| 20 | for i in range(len(points)): |
| 21 | slopes: dict[tuple[int, int], int] = defaultdict(int) |
| 22 | x1, y1 = points[i] |
| 23 | |
| 24 | for j in range(i + 1, len(points)): |
| 25 | x2, y2 = points[j] |
| 26 | dx, dy = x2 - x1, y2 - y1 |
| 27 | g = math.gcd(dx, dy) |
| 28 | |
| 29 | # 3. Reduce the Direction to a Canonical Key: |
| 30 | # Dividing dx and dy by their gcd keeps the same direction in |
| 31 | # lowest terms, then flipping the sign so dy is positive (or dy |
| 32 | # == 0 with dx positive) makes opposite vectors of one line hash alike. |
| 33 | slope = (dy // g, dx // g) |
| 34 | if slope[0] < 0 or (slope[0] == 0 and slope[1] < 0): |
| 35 | slope = (-slope[0], -slope[1]) |
| 36 | |
| 37 | # 4. Count and Track the Best Line Through This Anchor: |
| 38 | # Every point sharing a key lies on the same line through |
| 39 | # points[i]; the + 1 below counts the anchor point itself. |
| 40 | slopes[slope] += 1 |
| 41 | max_pts = max(max_pts, slopes[slope] + 1) |
| 42 | |
| 43 | return max_pts |
points[i], two points share a key in slopes exactly when they lie on the same line through points[i].Before counting, turn each item into a key that is equal exactly when the items should count as equal; here the item is the direction from points[i] to points[j], and its key is (dy // g, dx // g) with g = gcd(dx, dy), sign fixed. Two directions lie on the same line through points[i] exactly when their reduced integer pairs match, and integers compare exactly, so two different directions never share one bucket, as rounded float slopes can when the coordinates are large. The trap is the sign: (1, -2) and (-1, 2) are the same direction, so force dy positive (or dy == 0 with dx positive) before counting slope, or one line is counted as two.
See it run
Canonical Key, step by step
anchor i -j -max_pts 0
Each column is one point, written as x,y. The key row and the count row belong to the current anchor only. Keys are written as dy,dx.
anchorthe point points[i] that every direction is measured fromjthe point points[j] whose direction from the anchor is computedkeythe pair (dy // g, dx // g) stored under that pointcountslopes[key] after this point is counted
Start: max_pts = 0. Each point in turn becomes the anchor points[i], with a fresh empty slopes.
Gotcha 1 of 4
- The trap
Gotcha 1: Leaving the sign of
(dy // g, dx // g)unfixedMistakeslope = (dy // g, dx // g)Fixslope = (dy // g, dx // g) if slope[0] < 0 or (slope[0] == 0 and slope[1] < 0): slope = (-slope[0], -slope[1])What happens:
math.gcdnever returns a negative number. Sody // ganddx // gkeep the signs ofdyanddx. Forpoints = [[0, 0], [1, 1], [-1, -1]], the anchor[0, 0]gives[1, 1]the key(1, 1). It gives[-1, -1]the key(-1, -1), although both points lie on the same line. That one line is then counted in two buckets. The fix flips the pair so thatdyis positive, ordy == 0anddxis positive.Example: points = [[0, 0], [1, 1], [-1, -1]]Mistake: returns 2Fix: returns 3
- The key is the item itself or its sorted letters, as in Group Anagrams (LC 49): no division or sign fix is needed to make equal items look equal. See Hash Map
Deep Dive
What a canonical key must guarantee
A canonical key is a standard form of an item. Two items get the same key exactly when you want to count them as equal. The key must satisfy two rules.
Rule 1: equal items give equal keys. Rule 2: different items give different keys. If rule 1 fails, one group is split into two buckets and each bucket is too small. If rule 2 fails, two different groups share one bucket and the count is too large.
In Max Points on a Line (LC 149), the item is the direction from points[i] to points[j]. The vectors (dy, dx) = (2, 2), (1, 1) and (3, 3) are all the same direction. Dividing both numbers by g = math.gcd(dx, dy) gives (1, 1) for all three. The vector (2, 1) is a different direction, and it stays (2, 1).
Other problems use other normal forms. Group Shifted Strings (LC 249) uses the differences between neighbouring letters, modulo 26, so "abc" and "bcd" both get (1, 1). Number of Distinct Islands (LC 694) subtracts the first cell of the island from every cell, so a moved island gets the same key.
Why the sign fix is needed, traced on four points
math.gcd never returns a negative number. So dy // g and dx // g keep the signs of dy and dx. The vector from [0, 0] to [-1, -1] gives (-1, -1). The vector from [0, 0] to [2, 2] gives (1, 1). Both points are on the same line through the anchor, but the pairs differ. The sign fix flips a pair when dy is negative, or when dy is 0 and dx is negative. After the flip, both pairs are (1, 1).
Trace for points = [[0, 0], [2, 2], [-1, -1], [1, 2]]. Anchor 0 gives the keys (1, 1), (1, 1) after the flip, and (2, 1). So slopes[(1, 1)] = 2 and max_pts = 3. Anchor 1 gives (1, 1) after a flip for point 2, and (0, 1) for point 3. For point 3, dx = -1 and dy = 0, so the raw pair (0, -1) is flipped to (0, 1). Anchor 2 gives (3, 2). The answer is 3.
The loop for j starts at i + 1. A line is counted from its first point in list order. That point is an anchor at some i, and every other point of the line has a larger index. So the largest slopes[slope] + 1 over all anchors is the size of the best line. The + 1 counts the anchor itself.
Why slopes is created again for every anchor
A key is only a direction. A direction names one line only when every point is measured from the same anchor. Two parallel lines have the same direction but different anchors.
If slopes were shared by all anchors, the count for one direction would add points from two parallel lines. Take points = [[0, 0], [1, 0], [5, 5], [6, 5]]. A shared slopes adds the horizontal pair from anchor 0 and the horizontal pair from anchor 2 into one count, slopes[(0, 1)] = 2. The result is 3. The correct answer is 2. The blueprint creates an empty slopes inside the loop over i, so each count belongs to one anchor.
Only one slopes exists at a time, and it holds at most N - 1 keys. So the extra space is O(N).
Integer keys, floats and the cost
A float dy / dx has two problems. A vertical line has dx = 0, and the division raises ZeroDivisionError. A float also rounds. For 94911150 / 94911151 and 94911151 / 94911152, Python returns equal floats, although the two fractions are different. Two different directions would then share one bucket.
The pair (dy // g, dx // g) has neither problem. A vertical line becomes (1, 0). Integers in Python have no size limit, and two pairs are equal only when the fractions are equal.
The loops visit every pair (i, j) with i < j once, which is N * (N - 1) / 2 pairs. Each pair costs one gcd and one dictionary update. The time is O(N^2) and the space is O(N), as in the blueprint docstring. LeetCode limits the input to 300 points, so the work is at most 44,850 pairs.
60-Second Pitch
"The task is to find the most points on one line. I make every point the anchor in turn. For each later point, I compute the direction from the anchor and reduce it with the gcd, so (2, 2) and (1, 1) become the same pair. I also fix the sign, so that a direction and its opposite give one key. Then one dictionary count per anchor tells me how many points share a line through that anchor. The key is a pair of integers, so there is no rounding and no division by zero for vertical lines. The time is O(N^2) and the space is O(N). The same idea works for any problem where items must be put into a standard form before they are counted."
Common Questions
- Why do you divide
dxanddyby their gcd? Different vectors can point in the same direction. For example,
(2, 2),(1, 1)and(3, 3)all lie on the same line through the anchor. The gcd reduces each pair to its smallest integers, so all of them become(1, 1)and share one key.- Why do you fix the sign of the key?
math.gcdis never negative, so the signs ofdyanddxstay. The vector to[-1, -1]and the vector to[1, 1]lie on one line but give(-1, -1)and(1, 1). The fix makesdypositive, ordxpositive whendyis 0. Then both give(1, 1).- Why not use the float
dy / dxas the key? A vertical line has
dx = 0, so the division fails. Floats also round, and two different slopes can become equal floats when the coordinates are large. An integer pair is exact and has no division.- What is the time and space complexity?
The time is O(N^2). There are about N^2 / 2 pairs and each pair costs one gcd and one dictionary update. The space is
O(N), becauseslopesis replaced for each anchor and holds at most N - 1 keys.- How do you handle vertical lines and repeated points?
A vertical line has
dx = 0. Theng = abs(dy), and the key is(1, 0)after the sign fix, with no division bydx. Repeated points givedx = dy = 0, which makes the gcd 0. Count those copies in a separate variable and add it to the best line through the anchor.
SWE Reasoning
Spot it
- The problem groups or counts items that are equal after a change of form, such as points on one line, strings that are shifts of each other, or shapes that match after a move.
- Comparing every group of items directly would take O(N^3) time or more. Hashing one key per item or per pair takes O(N^2) time or less.
- Max Points on a Line (LC 149), Number of Distinct Islands (LC 694) and Group Shifted Strings (LC 249) all ask which items share a standard form.
- A float would be the natural key, but exact comparison is needed.
The invariant, step by step
- For anchor
points[i],slopesis empty andmax_ptsholds the best count from earlier anchors. - For each later point
points[j], the code computesdxanddyand divides both byg = math.gcd(dx, dy). - The sign fix makes
dypositive, ordxpositive whendyis 0. Now every vector on the same line through the anchor has the same key. slopes[slope] += 1counts one more point on that line.slopes[slope] + 1is the number of points on that line, including the anchor.max_ptskeeps the largest value.- After all anchors,
max_ptsis the size of the largest set of collinear points. Collinear means on one straight line.
Traps
- No sign fix. The points
[1, 1]and[-1, -1]give(1, 1)and(-1, -1)from anchor[0, 0]. One line is counted in two buckets, andmax_points_on_line([[0, 0], [1, 1], [-1, -1]])returns 2 instead of 3. - One shared
slopes. Parallel lines from different anchors add into one bucket. For[[0, 0], [1, 0], [5, 5], [6, 5]]the result is 3 instead of 2. - Float slope. A vertical line raises
ZeroDivisionError. Large coordinates can make two different slopes round to one float. - Repeated points. If two points are equal,
dxanddyare both 0,math.gcd(0, 0)is 0 and the division raisesZeroDivisionError. LC 149 promises distinct points. A variant needs a separate count of copies.