Question

Formatted question description: https://leetcode.ca/all/149.html

149	Max Points on a Line

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Example 1:

Input: [[1,1],[2,2],[3,3]]
Output: 3
Explanation:
^
|
|        o
|     o
|  o
+------------->
0  1  2  3  4


Example 2:

Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Explanation:
^
|
|  o
|     o        o
|        o
|  o        o
+------------------->
0  1  2  3  4  5  6


@tag-hashtable
@tog-top100

Algorithm

A slope can be calculated between two given points. Each slope represents a straight line. For each straight line, bring in all the points to see if they are collinear and calculate the number.

Two special cases need to be considered.

  • One is that when two points coincide, a straight line cannot be determined, but this is also a collinear case and requires special treatment.
  • The second is the case where the slope does not exist. Since the slope k of the two points (x1, y1) and (x2, y2) is expressed as (y2-y1) / (x2-x1), then the slope does not exist when x1 = x2, This collinear situation requires special treatment

TreeMap is used to record the mapping between the slope and the number of collinear points. The first case of coincident points assumes its slope is INT_MIN, and the second case assumes its slope is INT_MAX, so TreeMap can be used for mapping. A variable duplicate is also needed to record the number of coincident points, and finally only needs to be added to the number in the TreeMap to get the total number of collinear points.

Code

Java

import java.util.HashMap;
import java.util.Map;

public class Max_Points_on_a_Line {

	public static void main(String[] args) {

		double a = 0.0 / (-1);
		System.out.println("a:" + a);

		double b = 0.0 / (1);
		System.out.println("b:" + b);

		System.out.println("a == b ? " + (a == b)); // output: true

		HashMap<Double, Integer> hm = new HashMap<Double, Integer>();
		hm.put(a, 1);
		hm.put(b, 1);
		// @note:@memorize: so, different keys
		System.out.println("hashmap keys: " + (hm.keySet())); // output: [-0.0, 0.0]

	}

	/**
	 * Definition for a point.
	 * class Point {
	 *     int x;
	 *     int y;
	 *     Point() { x = 0; y = 0; }
	 *     Point(int a, int b) { x = a; y = b; }
	 * }
	 */
	public class Solution {
		public int maxPoints(Point[] points) {
			if (points == null || points.length == 0)
				return 0;

			// line slope => number of points
			HashMap<Double, Integer> hm = new HashMap<Double, Integer>();
			int max = 0;

			// have to touch every possible line, so O(logN)
			for (int i = 0; i < points.length; i++) {
				int duplicate = 1;
				int vertical = 0;
				for (int j = i + 1; j < points.length; j++) {
					// @note:@memorize: handle duplicates and vertical
					if (points[i].x == points[j].x) {
						if (points[i].y == points[j].y) {
							duplicate++; // itself
						} else {
							vertical++; // vertical line at the same x position
						}
					} else {
						double slope = points[j].y == points[i].y ? 0.0 : (1.0 * (points[j].y - points[i].y)) / (points[j].x - points[i].x);

                        hm.merge(slope, 1, (a, b) -> a + b);
					}
				}

				// record max number of points for one line
				for (Integer count : hm.values()) {
					if (count + duplicate > max) {
						max = count + duplicate;
					}
				}

				// @note:@memorize: special case for vertical line points
				max = Math.max(vertical + duplicate, max);

				hm.clear(); // @note: api, better than create a new hashmap?
			}

			return max;
		}

	}
}

All Problems

All Solutions