Skip to content

Instantly share code, notes, and snippets.

@vinaypuranik
Last active May 8, 2020 12:04
Show Gist options
  • Save vinaypuranik/72cf0f2eb7cea5fc334684c15dd9b6f7 to your computer and use it in GitHub Desktop.
Save vinaypuranik/72cf0f2eb7cea5fc334684c15dd9b6f7 to your computer and use it in GitHub Desktop.
MaxWidth of a vertical path
import java.util.*;
/*
Time complexity O(N*logN) where n is the number of x points.
Space O(1)
*/
public class MaxWidth{
public static int maxWidth(int[] X, int[] Y) {
Arrays.sort(X);
int xprev = X[0];
int maxWidth = 0;
for (int i = 1; i < X.length; i++) {
int width = X[i] - xprev;
if (maxWidth < width) {
maxWidth = width;
}
xprev = X[i];
}
return maxWidth;
}
public static void main(String []args){
int[] x = new int[]{4,1,5,4};
int[] y = new int[]{4,5,1,3};
System.out.println(maxWidth(x, y));
int[] x1 = new int[]{5,5,5,7,7,7};
int[] y1 = new int[]{3,4,5,1,3,7};
System.out.println(maxWidth(x1,y1));
int[] x2 = new int[]{6,10,1,4,3};
int[] y2 = new int[]{2,5,3,1,6};
System.out.println(maxWidth(x2,y2));
int[] x3= new int[]{2,6,7};
int[] y3= new int[]{6,11,3};
System.out.println(maxWidth(x3,y3));
int[] x4 = new int[]{2,4,7};
int[] y4 = new int[]{11,4,2};
System.out.println(maxWidth(x4,y4));
int[] x5 = new int[]{3,2,7};
int[] y5 = new int[]{11,11,11};
System.out.println(maxWidth(x5,y5));
int[] x6 = new int[]{2,5,9};
int[] y6 = new int[]{10,2,12};
System.out.println(maxWidth(x6,y6));
int[] x7 = new int[]{2,4,7};
int[] y7 = new int[]{2,4,11};
System.out.println(maxWidth(x7,y7));
int[] x8 = new int[]{2,5,7,9};
int[] y8 = new int[]{10,2,5,12};
System.out.println(maxWidth(x8,y8));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment