# Maximum Distance O(n) solution help

Problem: Maximum Distance

IDK if the link works because it isn’t blue when I’m typing this, but just put https://codeforces.com/gym/102951/problem/A, into the browser.

So, during a CPI class we were challenged to code this problem so that the code runs in O(n). My solution is that we find the top left, top right, bottom left, and bottom right, then find the greatest distance between those points.

My code,

import java.util.Scanner;

public class Main {
public static void main(String args[]) {

	Scanner sc1 = new Scanner(System.in);

int[] top = new int[2];
int[] bottom = new int[2];
int[] left = new int[2];
int[] right = new int[2];

int coordinates = sc1.nextInt();

int x = 0;
int y = 0;

int[] xs = new int[coordinates];
int[] ys = new int[coordinates];

sc1.nextLine();
for(int a = 0; a < coordinates;a++) {
x = sc1.nextInt();
xs[a] = x;
}

sc1.nextLine();
for(int a = 0; a < coordinates;a++) {
y = sc1.nextInt();
ys[a] = y;
}

top[0] = x;
top[1] = y;
bottom[0] = x;
bottom[1] = y;
left[0] = x;
left[1] = y;
right[0] = x;
right[1] = y;

for(int a = 0; a < coordinates; a++) {
x = xs[a];
y = ys[a];

if(y > top[1]) {
top[0] = x;
top[1] = y;
}

else if(y < bottom[1]) {
bottom[0] = x;
bottom[1] = y;
}

if(x > right[0]) {
right[0] = x;
right[1] = y;
}

else if(x < left[0]) {
left[0] = x;
left[1] = y;
}
}

//bottom right
//bottom left
//bottom top
//top right
//top left
//right left

int br = distance(bottom,right);
int bl = distance(bottom,left);
int bt = distance(bottom,top);
int tr = distance(top, right);
int tl = distance(top,left);
int lr = distance(left, right);

System.out.println(Math.max(Math.max(br, bl), Math.max(bt, Math.max(tr, Math.max(tl,lr)))));

}
public static int distance(int[] first, int[] second) {

int x = second[0] - first[0];
int y = second[1] - first[1];
return x*x + y*y;
}


}

Ok, did I miss miss one distance? Is my approach wrong? I got the wrong answer on test case 6… Thanks

i’m not sure if it’s possible to find the maximum distance between two points in \mathcal O(N) but i’m pretty sure \mathcal O(N\log N) is achievable using convex hull and smth else.

1 Like