Find a line which passes the most number of points

Problem

Given a two dimensional graph with points on it, find a line which passes the most number of points.

Examples

Example 1

1
2
3


Input: points = [(0,0), (1,1), (2,2), (0,1)]
Output: Line y = x (passes through (0,0), (1,1), (2,2))
Explanation: Three points lie on the diagonal line with slope 1 and intercept 0, which is the maximum.

Example 2

1
2
3


Input: points = [(2,0), (2,1), (2,2), (0,0), (1,1)]
Output: Line x = 2 (passes through (2,0), (2,1), (2,2))
Explanation: A vertical line at x=2 contains three points — more than any other line.

Solution

Method 1 - Naive Solution

This is the brute force solution. We take point 1, and then point 2 and make a line. Now in the third nested loop, check if point 3 is existing on the same line or not.

Pseudocode

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


Line findLineWithMaxPoint(Set points){
   foreach Point p1 in points
      foreach Point p2  in (points - {p1}){
         Line l = makeLine(p1,p2);
         int count = 2 //line contains p1 and p2
         foreach(Point p3 in (points-{p1,p2})){
            if(l.contains(p3))
               count++;
         }
         if(maxCount<count){
            count = maxCount;
            resultLine = l;
         }
      }
return resultLine;
}

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


class Solution {
  static final double EPS = 1e-8;

  static class Point { final double x, y; Point(double x, double y) { this.x = x; this.y = y; } }

  static class Line {
    final boolean vertical;
    final double slope, intercept, x;
    Line(double slope, double intercept) { this.vertical = false; this.slope = slope; this.intercept = intercept; this.x = Double.NaN; }
    Line(double x) { this.vertical = true; this.slope = Double.POSITIVE_INFINITY; this.intercept = Double.NaN; this.x = x; }
    boolean contains(Point p) { return vertical ? Math.abs(p.x - x) < EPS : Math.abs(p.y - (slope * p.x + intercept)) < EPS; }
  }

  public Line findLineWithMaxPoints(java.util.List<Point> points) {
    int n = points.size();
    if (n < 2) return null;
    Line ans = null;
    int ansCount = 0;
    for (int i = 0; i < n; ++i) {
      for (int j = i + 1; j < n; ++j) {
        Point a = points.get(i), b = points.get(j);
        Line line = (Math.abs(a.x - b.x) < EPS) ? new Line(a.x) : new Line((b.y - a.y) / (b.x - a.x), a.y - ((b.y - a.y) / (b.x - a.x)) * a.x);
        int cnt = 0;
        for (Point p : points) {
          if (line.contains(p)) ++cnt;
        }
        if (cnt > ansCount) { ansCount = cnt; ans = line; }
      }
    }
    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


class Solution:
  def findLineWithMaxPoints(self, points: list[tuple[float, float]]) -> tuple[float, float] | None:
    EPS = 1e-8

    def contains(line: tuple[float, float], p: tuple[float, float]) -> bool:
      slope, intercept = line
      x, y = p
      if slope == float('inf'):
        return abs(x - intercept) < EPS
      return abs(y - (slope * x + intercept)) < EPS

    n = len(points)
    if n < 2:
      return None

    ans: tuple[float, float] | None = None
    ans_count = 0
    for i in range(n):
      p1 = points[i]
      for j in range(i + 1, n):
        p2 = points[j]
        if abs(p2[0] - p1[0]) < EPS:
          line = (float('inf'), p1[0])
        else:
          slope = (p2[1] - p1[1]) / (p2[0] - p1[0])
          intercept = p1[1] - slope * p1[0]
          line = (slope, intercept)
        cnt = 0
        for p in points:
          if contains(line, p):
            cnt += 1
        if cnt > ans_count:
          ans_count = cnt
          ans = line
    return ans

Complexity

⏰ Time complexity: O(n^3) — Three nested loops: enumerate pairs and check all points.
🧺 Space complexity: O(1) — Constant extra space.

Method 2 – Hash Table

Intuition

Treat each point as a base and count how many other points share the same slope relative to that base. Points that coincide with the base are counted as duplicates. The slope that appears most frequently for a base defines the best line through that base; the global best is the maximum over all bases.

Approach

Iterate over each point p as the base.
Create a hash map from a normalized slope key to its count and maintain a duplicates counter for points identical to p.
For every other point q, compute the slope from p to q and convert it to a robust key (e.g., reduced dy/dx or a high-precision string); use a special key for vertical lines.
Increment the count for that slope and track the local maximum for this base.
The total points on the best line through p = local_max + duplicates + 1 (including p). Update the global best when larger.
After processing all bases return the line (represented by slope and intercept or by a base point plus slope) with the highest count.

Complexity: O(n^2) time and O(n) extra space per base (for the hash map).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


class Solution {
 public:
  struct Point { double x, y; };
  struct Line {
    double slope, intercept;
    static constexpr double EPS = 1e-8;
    Line(const Point& a, const Point& b) {
      slope = (b.y - a.y) / (b.x - a.x);
      intercept = (b.x * a.y - a.x * b.y) / (b.x - a.x);
    }
    bool contains(const Point& p) const {
      return std::abs(p.y - (slope * p.x + intercept)) < EPS;
    }
  };

  Line findLineWithMaxPoints(const std::vector<Point>& points) {
    int n = points.size();
    if (n < 2) return Line{0,0};
    Line ans(points[0], points[1]);
    int ansCount = 0;
    for (int i = 0; i < n; ++i) {
      for (int j = i + 1; j < n; ++j) {
        Line line(points[i], points[j]);
        int cnt = 0;
        for (const auto& p : points) if (line.contains(p)) ++cnt;
        if (cnt > ansCount) { ansCount = cnt; ans = line; }
      }
    }
    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


type Point struct { X, Y float64 }
type Line struct { Slope, Intercept float64 }
func (l Line) Contains(p Point) bool { const EPS = 1e-8; return math.Abs(p.Y-(l.Slope*p.X+l.Intercept)) < EPS }

func FindLineWithMaxPoints(points []Point) Line {
  n := len(points)
  var ans Line
  ansCount := 0
  for i := 0; i < n; i++ {
    for j := i+1; j < n; j++ {
      l := Line{Slope: (points[j].Y - points[i].Y) / (points[j].X - points[i].X), Intercept: (points[j].X*points[i].Y - points[i].X*points[j].Y) / (points[j].X - points[i].X)}
      cnt := 0
      for _, p := range points { if l.Contains(p) { cnt++ } }
      if cnt > ansCount { ansCount = cnt; ans = l }
    }
  }
  return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


class Solution {
  static final double EPS = 1e-8;

  static class Point { final double x, y; Point(double x, double y) { this.x = x; this.y = y; } }

  static class Line { final boolean vertical; final double slope, intercept, x; Line(double slope, double intercept) { this.vertical = false; this.slope = slope; this.intercept = intercept; this.x = Double.NaN; } Line(double x) { this.vertical = true; this.slope = Double.POSITIVE_INFINITY; this.intercept = Double.NaN; this.x = x; } boolean contains(Point p) { return vertical ? Math.abs(p.x - x) < EPS : Math.abs(p.y - (slope * p.x + intercept)) < EPS; } }

  public Line findLineWithMaxPoints(java.util.List<Point> points) {
    int n = points.size(); if (n < 2) return null;
    Line ans = null; int ansCount = 0;
    for (int i = 0; i < n; ++i) {
      java.util.Map<String, Integer> map = new java.util.HashMap<>(); int duplicates = 0, localMax = 0;
      Point a = points.get(i);
      for (int j = i + 1; j < n; ++j) {
        Point b = points.get(j);
        if (Math.abs(a.x - b.x) < EPS && Math.abs(a.y - b.y) < EPS) { duplicates++; continue; }
        String key = Math.abs(a.x - b.x) < EPS ? "VERTICAL" : String.format("S:%.12f", (b.y - a.y) / (b.x - a.x));
        int cnt = map.getOrDefault(key, 0) + 1; map.put(key, cnt); localMax = Math.max(localMax, cnt);
      }
      int countWithA = localMax + duplicates + 1;
      if (countWithA > ansCount) {
        ansCount = countWithA; String bestKey = null;
        for (java.util.Map.Entry<String,Integer> e : map.entrySet()) if (e.getValue() == localMax) { bestKey = e.getKey(); break; }
        if (bestKey == null || bestKey.equals("VERTICAL")) ans = new Line(a.x);
        else { double slope = Double.parseDouble(bestKey.substring(2)); ans = new Line(slope, a.y - slope * a.x); }
      }
    }
    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


data class Point(val x: Double, val y: Double)

class Solution {
  fun findLineWithMaxPoints(points: List<Point>): Line {
    var ansCount = 0
    var ans = Line(0.0, 0.0)
    for (i in points.indices) {
      for (j in i+1 until points.size) {
        val line = Line((points[j].y - points[i].y) / (points[j].x - points[i].x), (points[j].x * points[i].y - points[i].x * points[j].y) / (points[j].x - points[i].x))
        var cnt = 0
        for (p in points) if (line.contains(p)) cnt++
        if (cnt > ansCount) { ansCount = cnt; ans = line }
      }
    }
    return ans
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


class Solution:
  def findLineWithMaxPoints(self, points: list[tuple[float, float]]) -> tuple[float, float] | None:
    EPS = 1e-8

    def contains(line: tuple[float, float], p: tuple[float, float]) -> bool:
      slope, intercept = line
      x, y = p
      if slope == float('inf'):
        return abs(x - intercept) < EPS
      return abs(y - (slope * x + intercept)) < EPS

    n = len(points)
    if n < 2:
      return None

    ans: tuple[float, float] | None = None
    ans_count = 0
    for i in range(n):
      p1 = points[i]
      for j in range(i + 1, n):
        p2 = points[j]
        if abs(p2[0] - p1[0]) < EPS:
          line = (float('inf'), p1[0])
        else:
          slope = (p2[1] - p1[1]) / (p2[0] - p1[0])
          intercept = p1[1] - slope * p1[0]
          line = (slope, intercept)
        cnt = 0
        for p in points:
          if contains(line, p):
            cnt += 1
        if cnt > ans_count:
          ans_count = cnt
          ans = line
    return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


struct Point { x: f64, y: f64 }
struct Line { slope: f64, intercept: f64 }
impl Line {
  fn contains(&self, p: &Point) -> bool { (p.y - (self.slope * p.x + self.intercept)).abs() < 1e-8 }
}
fn findLineWithMaxPoints(points: &[Point]) -> Line {
  let mut max_count = 0;
  let mut ans = Line { slope: 0.0, intercept: 0.0 };
  for i in 0..points.len() {
    for j in (i+1)..points.len() {
      let slope = (points[j].y - points[i].y) / (points[j].x - points[i].x);
      let intercept = (points[j].x * points[i].y - points[i].x * points[j].y) / (points[j].x - points[i].x);
      let line = Line { slope, intercept };
      let count = points.iter().filter(|p| line.contains(p)).count();
      if count > max_count { max_count = count; ans = line; }
    }
  }
  ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


type Point = { x: number; y: number };
function contains(line: { slope: number; intercept: number }, p: Point): boolean { return Math.abs(p.y - (line.slope * p.x + line.intercept)) < 1e-8; }

function findLineWithMaxPoints(points: Point[]): { slope: number; intercept: number } {
  let ans = { slope: 0, intercept: 0 };
  let ansCount = 0;
  for (let i = 0; i < points.length; ++i) {
    for (let j = i + 1; j < points.length; ++j) {
      const slope = (points[j].y - points[i].y) / (points[j].x - points[i].x);
      const intercept = points[i].y - slope * points[i].x;
      const line = { slope, intercept };
      let cnt = 0;
      for (const p of points) if (contains(line, p)) cnt++;
      if (cnt > ansCount) { ansCount = cnt; ans = line }
    }
  }
  return ans;
}

Complexity

⏰ Time complexity: O(n^2) — Two nested loops over points (base and other points); each inner loop does O(1) amortized hash updates.
🧺 Space complexity: O(n) — The hash map per base can store up to O(n) slope entries.

Method 3 – Hough Transform

Intuition

The Hough Transform is a technique from image processing to detect lines by mapping points in Cartesian space to parameters in Hough space. It can efficiently find the most common line among a set of points.

Approach

Map each point to all possible lines in parameter space.
Use an accumulator to count how many points map to each line.
The line with the highest count is the answer.
This method is more common in computer vision and image analysis.

See this Hough Transform tutorial for more details.

Complexity

⏰ Time complexity: O(n^2) — Each point is mapped to many lines, but practical implementations use discretization.
🧺 Space complexity: O(m) — Accumulator array size depends on discretization of parameter space.

Problem#

Examples#

Example 1#

Example 2#

Solution#

Method 1 - Naive Solution#

Pseudocode#

Code#

Complexity#

Method 2 – Hash Table#

Intuition#

Approach#

Code#

Complexity#

Method 3 – Hough Transform#

Intuition#

Approach#

Complexity#

Problem

Examples

Example 1

Example 2

Solution

Method 1 - Naive Solution

Pseudocode

Code

Complexity

Method 2 – Hash Table

Intuition

Approach

Code

Complexity

Method 3 – Hough Transform

Intuition

Approach

Complexity