From cassido's April 17, 2023 Newsletter

maxPointsOnLine.ts

type Point = [number, number];

const slope = ([x1, y1]: Point, [x2, y2]: Point) => (y2 - y1) / (x2 - x1);
const makeKey = ([x1, y1]: Point, [x2, y2]: Point) =>
  `(${x1},${y1}) -> (${x2},${y2})`;
const splitKey = (key: string): [string, string] =>
  key.split(" -> ") as [string, string];

function maxPointsOnLine(points: Point[]) {
  const slopes = new Map<string, number>();
  points.forEach(([x, y]) => {
    const others = points.filter(([otherX, otherY]) =>
      otherX != x || otherY != y
    );
    others.forEach((other) => {
      const thisToOther = makeKey([x, y], other);
      if (slopes.has(thisToOther)) return;

      const otherToThis = makeKey(other, [x, y]);
      slopes.set(otherToThis, slope(other, [x, y]));
    });
  });

  const slopeCount = new Map<number, number>();
  for (const slope of slopes.values()) {
    const val = slopeCount.get(slope) || 0;
    slopeCount.set(slope, val + 1);
  }

  let maxCount = -Infinity;
  let slopeWithMaxFrequency = -Infinity;
  for (const [slope, count] of slopeCount.entries()) {
    maxCount = Math.max(maxCount, count);
    if (maxCount === count) {
      slopeWithMaxFrequency = slope;
    }
  }

  const pointsSet = new Set();
  for (const [pointPair, slope] of slopes.entries()) {
    if (slope === slopeWithMaxFrequency) {
      const [point1, point2] = splitKey(pointPair);
      pointsSet.add(point1);
      pointsSet.add(point2);
    }
  }

  console.log(pointsSet);
  return pointsSet.size;
}

console.log(maxPointsOnLine([[1, 1], [2, 2], [3, 3]]));
console.log(maxPointsOnLine([[1, 1], [3, 2], [5, 3], [4, 1], [2, 3], [1, 4]]));