Count Maximum Points on the Same Line in Java
In Java, The "Count Maximum Points on the Same Line," involves finding the maximum number of points that lie on the same line in a given set of points in a two-dimensional plane. In other words, the task of counting the maximum number of points on the same line in Java involves finding the line that passes through the maximum number of points in a given set of points. The problem can be solved using some algorithms. Here's an implementation of how you can solve this problem:
Example 1
Input: points[] = {1, 1}, {2, 2}, {3, 3}, {4, 4}, {4, 5}, {5, 6},
Output: 4
Explanation: Given N point on a 2D plane as pair of (x, y) coordinates, we have to find the maximum number of points which lie on the same line. Then the maximum number of points that lie on the same
line are 4, those point are {1, 1}, {2, 2}, {3, 3}, {4, 4}.
Approach: Slope Counting Algorithm
In the above code. we have to Define a class Point to represent the coordinates of a point. The class should have x and y instance variables and a constructor to initialize them. Then we have to Create a method maxPoints that takes an array of Point objects as input and returns the maximum number of points on the same line. At the last, we have to Test the maxPoints method with sample points. In this example, we create four points that lie on the same line. The expected output is 4 because all four points are collinear.
FileName: MaxPointsOnSameLine.java
import java.util.HashMap;
import java.util.Map;
// Class to represent a point with x and y coordinates
class Point {
int x;
int y;
Point(int x, int y) {
this.x = x;
this.y = y;
}
}
// Class to calculate the maximum number of points on the same line
class Solution {
public int maxPoints(Point[] points) {
// If there are less than or equal to 2 points, return the count
if (points.length <= 2) {
return points.length;
}
int maxPoints = 0;
// Iterate over each point
for (int i = 0; i < points.length; i++) {
// Create a map to store the slope count
Map slopeCount = new HashMap<>();
int samePoints = 0; // Count of points with the same coordinates
int currentMax = 0; // Maximum points on the same line for the current point
// Iterate over the remaining points
for (int j = i + 1; j < points.length; j++) {
int dx = points[j].x - points[i].x;
int dy = points[j].y - points[i].y;
// If the points have the same coordinates, increment the samePoints count
if (dx == 0 && dy == 0) {
samePoints++;
continue;
}
// Calculate the slope of the line connecting the two points
double slope = (dx == 0) ? Double.POSITIVE_INFINITY : (double) dy / dx;
// Update the slope count
slopeCount.put(slope, slopeCount.getOrDefault(slope, 0) + 1);
// Update the currentMax value
currentMax = Math.max(currentMax, slopeCount.get(slope));
}
// Update the maxPoints if necessary
maxPoints = Math.max(maxPoints, currentMax + samePoints + 1);
}
return maxPoints;
}
}
class MaxPointsOnSameLine {
public static void main(String[] args) {
// Create an array of points
Point[] points = new Point[6];
points[0] = new Point(1, 1);
points[1] = new Point(2, 2);
points[2] = new Point(3, 3);
points[3] = new Point(4, 4);
points[4] = new Point(4, 5);
points[5] = new Point(5, 6);
// Create an instance of the Solution class
Solution solution = new Solution();
// Calculate the maximum points on the same line
int maxPoints = solution.maxPoints(points);
// Print the result
System.out.println("Maximum points on the same line: " + maxPoints);
}
}
Output
Maximum points on the same line: 4
Complexity:
The time complexity of the slope-counting algorithm used in this approach is O(n^2), where n is the number of points. Using the formula for the sum of an arithmetic series, this can be simplified to (n-1)(n)/2, which is O(n^2).
The space required by the map depends on the number of unique slopes encountered. In the worst case, if all points are distinct and no two points share the same slope, the space complexity would be O(n^2) since there can be at most (n-1)(n)/2 unique slopes. Therefore, the overall space complexity can be considered as O(n) on average, but in the worst case, it can be O(n^2).