Most with positive slope

Given an array of 2D coordinates of points (all the coordinates are integers), find the largest number of points that can form a set such that any pair of points in the set can form a line with positive slope. Return the size of such a maximal set.

Assumptions

• The given array is not null

• Note: if there does not even exist 2 points can form a line with positive slope, should return 0.

Examples

• <0, 0>, <1, 1>, <2, 3>, <3, 3>, the maximum set of points are {<0, 0>, <1, 1>, <2, 3>}, the size is 3.

Key Insight:

to have a positive slope between x1y1 and x2y2.

1. x1 != x2

2. y2 > y1

Solution: Sort, then longest ascending problem

First sort points so that x is in ascending pattern. y is in descending pattern.

This way when looking ahead. x1y1 x1y2 will not count as a positive slope.

ex: <1,2><1,5> is not a positive slope

/*
* class Point {
*   public int x;
*   public int y;
*   public Point(int x, int y) {
*     this.x = x;
*     this.y = y;
*   }
* }
*/
public class Solution {
  public int largest(Point[] points) {
    Arrays.sort(points, new MyComparator());
    int result = 0;
    int[] M = new int[points.length];

    for (int i = 0; i < points.length; i++){
      for(int j = 0; j < i;j++){
        if (points[j].y < points[i].y){
          M[i] = Math.max(M[j] , M[i]);
        }
      }
      M[i]++;
      result = Math.max(M[i], result);
    }
    return result == 1 ? 0 : result;
  }

  static class MyComparator implements Comparator<Point>{
    @Override
    public int compare(Point p1, Point p2){
      return p1.x != p2.x ? p1.x - p2.x : p2.y - p1.y;
    }
  }
}

TC: O(N^2)

SC: O(N)