Microsoft Online Assessment (OA) - Widest Path Without Trees

There are N trees (numbered from 0 to N-1) in a forest. The K-th tree is located at coordinates (X[K], Y[K]). We want to build the widest possible vertical path, such that there is no tree on it. The path must be built somewhere between a leftmost and a rightmost tree, which means that the width of the path cannot be infinite.

What is the width of the widest possible path that can be built?

Write a function:

def solution(X, Y)

that, given two arrays X and Y consisting of N integers each, denoting the positions of trees, returns the widest possible path that can be built.

Example 1:

Input: X = [5,5,5,7,7,7], Y = [3,4,5,1,3,7]

Output: 2

Example 2:

Input: X = [6,10,1,4,3], Y = [2,5,3,1,6]

Output: 4

Example 3:

Input: X = [4,1,5,4], Y = [4,5,1,3]

Output: 3

Try it yourself

Implementation

1from typing import List
2
3def widest_path(x: List[int], y: List[int]) -> int:
4    difference = 0
5    sorted_x = sorted(x)
6    for i in range(len(sorted_x) - 1):
7        diff = sorted_x[i + 1] - sorted_x[i]
8        difference = max(diff, difference)
9    return difference
10
11if __name__ == "__main__":
12    x = [int(x) for x in input().split()]
13    y = [int(x) for x in input().split()]
14    res = widest_path(x, y)
15    print(res)
16

1import java.util.Arrays;
2import java.util.List;
3import java.util.Scanner;
4import java.util.stream.Collectors;
5
6class Solution {
7    public static int widestPath(List<Integer> x, List<Integer> y) {
8        int maxWidth = 0;
9        x.sort(null);
10        for (int i = 0; i < x.size() - 1; i++) {
11            maxWidth = Math.max(maxWidth, (x.get(i + 1) - x.get(i)));
12        }
13        return maxWidth;
14    }
15
16    public static List<String> splitWords(String s) {
17        return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
18    }
19
20    public static void main(String[] args) {
21        Scanner scanner = new Scanner(System.in);
22        List<Integer> x = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
23        List<Integer> y = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
24        scanner.close();
25        int res = widestPath(x, y);
26        System.out.println(res);
27    }
28}
29

1"use strict";
2
3function widestPath(x, y) {
4    let maxWidth = 0;
5    x = x.sort((a, b) => a - b);
6    for (let i = 0; i < x.length - 1; i++) {
7        maxWidth = Math.max(maxWidth, x[i + 1] - x[i]);
8    }
9    return maxWidth;
10}
11
12function splitWords(s) {
13    return s === "" ? [] : s.split(" ");
14}
15
16function* main() {
17    const x = splitWords(yield).map((v) => parseInt(v));
18    const y = splitWords(yield).map((v) => parseInt(v));
19    const res = widestPath(x, y);
20    console.log(res);
21}
22
23class EOFError extends Error {}
24{
25    const gen = main();
26    const next = (line) => gen.next(line).done && process.exit();
27    let buf = "";
28    next();
29    process.stdin.setEncoding("utf8");
30    process.stdin.on("data", (data) => {
31        const lines = (buf + data).split("\n");
32        buf = lines.pop();
33        lines.forEach(next);
34    });
35    process.stdin.on("end", () => {
36        buf && next(buf);
37        gen.throw(new EOFError());
38    });
39}
40