# Widest Path Without Trees Microsoft OA 2023

Page Contents

## Widest Path Without Trees Solution

There are N trees in the forest (numbered from 0 to N-1). The Kth tree is located at coordinates (X[k], Y[k]).
We want to build the largest possible vertical path so that there is no tree. The path must be established somewhere between the leftmost tree and the rightmost tree, which means that the width of the path is not infinite.

Write a function:
public static Integer solution(int[] X, int[] Y), given the N integers to form the X and Y of the array, they indicate the position of the tree, then return the most constructable The width of the wide path.

Example

Given X=[1,8,7,3,4,1,8] , Y=[6,4,1,8,5,1,7] , the function should return 3.

### SOLUTION

Program : Widest Path Without Trees Solution in Java

``````public static void main(String[] args) {
int[] M = {1, 8, 7, 3, 4, 1, 8};
int[] N = {6, 4, 1, 8, 5, 1, 7};
System.out.println(solution2(M, N));
int[] M1 = {5, 5, 5, 7, 7, 7};
int[] N1 = {3, 4, 5, 1, 3, 4};
System.out.println(solution2(M1, N1));
int[] M2 = {6, 10, 1, 4, 4};
int[] N2 = {2, 5, 3, 1, 6};
System.out.println(solution2(M2, N2));
int[] M3 = {4, 1, 5, 4};
int[] N3 = {4, 5, 1, 3};
System.out.println(solution2(M3, N3));
}
public static Integer solution2(int[] X, int[] Y) {
int maxX = 0;
int maxY = 0;
ArrayList<Integer> X = new ArrayList<>();
ArrayList<Integer> Y = new ArrayList<>();
for (int i : X) {
}
for (int i : Y) {
}
Collections.sort(X);
Collections.sort(Y);
for (int i = 1; i < X.size(); i++) {
int j = X.get(i) - X.get(i - 1);
maxX = j >= maxX ? j : maxX;
}
for (int i = 1; i < Y.size(); i++) {
int j = Y.get(i) - Y.get(i - 1);
maxY = j >= maxY ? j : maxY;
}
return maxX >= maxY ? maxX : maxY;
}``````