FastPrep
Problem · Sorting

Shortest Board Length to Cover Holes

Learn this problem
● MediumMicrosoft logoMicrosoftFULLTIMEOA
See Microsoft hiring insights

Problem statement

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.

Function

coverHotels(A: int[]) → int

Examples

Example 1

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

Example 2

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

Example 3

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

Example 4

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

Constraints

  • 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

    • More Microsoft problems

    drafts saved locally
    public int coverHotels(int[] A) {
  // write your code here
}
    A[11, 20, 15]
    expected4
    checking account