Can anyone tell me why this code is showing TLE. How can I optimize this
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
class Solution {
static class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
public static Long minSum(Point[] points) {
if (points.length <= 2) return 0L;
Arrays.sort(points, new sortByX());
long sum1 = Long.MAX_VALUE;
int[] prefymin = new int[points.length];
int[] suffymin = new int[points.length];
int[] prefymax = new int[points.length];
int[] suffymax = new int[points.length];
prefymin[0] = points[0].y;
prefymax[0] = points[0].y;
for (int i = 1; i < points.length; i++) {
prefymin[i] = Math.min(prefymin[i - 1], points[i].y);
prefymax[i] = Math.max(prefymax[i - 1], points[i].y);
}
suffymin[points.length - 1] = points[points.length - 1].y;
suffymax[points.length - 1] = points[points.length - 1].y;
for (int i = points.length - 2; i >= 0; i--) {
suffymin[i] = Math.min(suffymin[i + 1], points[i].y);
suffymax[i] = Math.max(suffymax[i + 1], points[i].y);
}
int spx = points[0].x;
int epx = points[points.length - 1].x;
for (int i = 0; i < points.length - 1; i++) {
long num1 = (points[i].x - spx) * (long) (prefymax[i] - prefymin[i]);
long num2 = (epx - points[i + 1].x) * (long) (suffymax[i + 1] - suffymin[i + 1]);
sum1 = Math.min(sum1, num1 + num2);
}
Arrays.sort(points, new sortByY());
long sum2 = Long.MAX_VALUE;
int[] prefxmin = new int[points.length];
int[] suffxmin = new int[points.length];
int[] prefxmax = new int[points.length];
int[] suffxmax = new int[points.length];
prefxmin[0] = points[0].x;
prefxmax[0] = points[0].x;
for (int i = 1; i < points.length; i++) {
prefxmin[i] = Math.min(prefxmin[i - 1], points[i].x);
prefxmax[i] = Math.max(prefxmax[i - 1], points[i].x);
}
suffxmin[points.length - 1] = points[points.length - 1].x;
suffxmax[points.length - 1] = points[points.length - 1].x;
for (int i = points.length - 2; i >= 0; i--) {
suffxmin[i] = Math.min(suffxmin[i + 1], points[i].x);
suffxmax[i] = Math.max(suffxmax[i + 1], points[i].x);
}
int spy = points[0].y;
int epy = points[points.length - 1].y;
for (int i = 0; i < points.length - 1; i++) {
long num1 = (points[i].y - spy) * (long) (prefxmax[i] - prefxmin[i]);
long num2 = (epy - points[i + 1].y) * (long) (suffxmax[i + 1] - suffxmin[i + 1]);
sum2 = Math.min(sum2, num1 + num2);
}
return Math.min(sum1, sum2);
}
static class sortByX implements Comparator<Point> {
public int compare(Point p1, Point p2) {
return (p1.x - p2.x);
}
}
static class sortByY implements Comparator<Point> {
public int compare(Point p1, Point p2) {
return (p1.y - p2.y);
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw = new PrintWriter(System.out);
int t = Integer.parseInt(br.readLine());
for (int i = 0; i < t; i++) {
int n = Integer.parseInt(br.readLine());
Point[] points = new Point[n];
for (int j = 0; j < n; j++) {
String[] in = br.readLine().split("\\s");
points[j] = new Point(Integer.parseInt(in[0]), Integer.parseInt(in[1]));
}
pw.println(minSum(points));
}
pw.flush();
}
}