FastPrepFastPrep
Problem Brief

Shortest Board Length to Cover Holes

FULLTIMEOA
See Microsoft online assessment and hiring insights

There are N holes arranged in a row in the top of an old table. We want to fix the table by covering the holes with two boards. For technical reasons, the boards need to be of the same length.

The position of the K-th hole is A[K]. What is the shortest length of the boards required to cover all the holes? The length of the boards has to be a positive integer. A board of length L, set at position X, covers all the holes located between positions X and X+L (inclusive). The position of every hole is unique.

Complete the func in the editor 👉

which, given an array A of integers of length N, representing the positions of the holes in the table, returns the shortest board length required to cover all the hotels.

1Example 1

Input
A = [11, 20, 15]
Output
4
Explanation
The first board would cover the holes in positions 11 and 15, and the second board the hole at position 20.

2Example 2

Input
A = [15, 20, 9, 11]
Output
5
Explanation
The first board covers the holes at positions 9 and 11, and the second one the holes in positions 15 and 20.

3Example 3

Input
A = [0, 44, 32, 30, 42, 18, 34, 16, 35]
Output
18
Explanation
The first board would cover the holes in positions between 0 and 18, and the second the positions between 30 and 44.

4Example 4

Input
A = [9]
Output
1
Explanation
There is only one hole, so the board length required is 1.

Constraints

Limits and guarantees your solution can rely on.

  • N is an integer within the range [1..100,000]
  • each element of array A is an integer within the range 0..1,000,000,000
  • the elements of A are all distinct
    • public int coverHotels(int[] A) {
  // write your code here
}
    Input

    A

    [11, 20, 15]

    Output

    4

    Sign in to submit your solution.