Maximum points in 2D space

Q1: Largest Set Of Points 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.

Analysis:
If two pair of points can form a line with positive slop, then (y2-y1)/(x2-x1) > 0. That means if y2 > y1, then x2 > x1; if y2 < y1, then x2 < x1. If all x coordinates are in  ascending order, all y coordinates in solution points should also in ascending order. To solve this problem, we can first sort the points in the order of ascending x, then find the max ascending subsequence of y, that is the result. As the result has to be larger than 2, if the max ascending subsequence is 1, then no pair of points can form a line with positive slop.


Solution:

class cmp {
  public:
  bool operator()(pair<int, int> left, pair<int, int> right) {
    return left.first < right.first;
  }
};
class Solution {
 public:
 //step1: sort the points in the ascending order of x
 //step2: find the maximum ascending subsequence of y
  int largest(vector<pair<int, int> > points) {
    // write your solution here.
    //sanitary check
    if (points.size() == 0) return 0;
    cmp compare;
   
    sort(points.begin(), points.end(), compare);   
    //M[i] represent the max ascendig subsequence of y from 0-i including i
    int *M = new int[points.size()];
    //base case:
    M[0] = 1;
    int global_max = 0;
    for (int i = 1; i < points.size(); i++) {
      int tmp_max = 0;
      for (int j = i-1; j >= 0; j--) {
        if (points[i].second > points[j].second) {
          tmp_max = max(tmp_max, M[j]);
        }
      }
      if (tmp_max > 0) M[i] = tmp_max + 1;
      else M[i] = 1;
      global_max = max(global_max, M[i]);
    }
    if (global_max == 1) return 0; //the result should be larger than 1
    return global_max;
  }
};

Time complexity:
     sort points: O(n logn)
     find max subsequnce : O(n^2)
     Total time complexity : O(n^2)
Space complexity: O(1)



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

Analysis:
If points are in the same straight line, then they share the same slope and intercept. The problem is to find the maximum number of points that share the same slope and intercept. We can solve this problem in three step: 1. iterative the point set, for each point, we calculate the slope and intercept with other point 2. for each point, store the slope and intercept with set of points in a hashmap, the key is pair<slope, intercept>, the value is the number of points with that slope and intercept . 3. find the maximum value in the hashmap, that's the result.
corner case: if the straight line is vertical to x, if (x1 == x2) or (x1 == x2 && y1 == y2), we should calculate this two case separately.

Solution:
assume the number of set of points is larger than 2.

class Solution {
 public:
  int most(vector<pair<int, int> > points) {
    // write your solution here.
    //sanitary check
    if (points.size() < 2) return 0;
    int same = 0; //the number of same points
    int sameX = 0; // the number of points with same x
    int global_max = 0;
    for (int i = 0; i < points.size(); i++) {
      int seedx = points[i].first;
      int seedy = points[i].second;
      same = 1;
      sameX = 0;
      int tmp_max = 0;
      map<pair<float, float>, int> line;
      for (int j = 0; j < points.size(); j++) {
        if (j == i) continue;
        int tmpx = points[j].first;
        int tmpy = points[j].second;
        //corner case
        if (tmpx == seedx && tmpy == seedy) same++;
        else if (tmpx == seedx) sameX++;
        else {
          float slope = (tmpy - seedy) * 1.0 / (tmpx - seedx);
          float intercept = (tmpy * seedx - tmpx * seedy) * 1.0 / (seedx - tmpx);
          line[make_pair(slope, intercept)]++;
          tmp_max = max(tmp_max, line[make_pair(slope, intercept)]);
        }
      }
      tmp_max = max(tmp_max, sameX);
      tmp_max = tmp_max + same ;
      global_max = max(global_max, tmp_max);
    }
    return global_max;
  }
};
Time complexity: O(n^2)
Space complexity: O(n);