FastPrep
Problem · Array

Minimum Parking Roof Length

Learn this problem
● EasyAmerican Express logoAmerican ExpressFULLTIMEOA

Problem statement

You are given distinct nonnegative integer coordinates in positions, where each coordinate contains one parked car, and an integer k.

Install one contiguous roof that covers at least k cars. A roof spanning integer coordinates x through y, inclusive, has length y - x + 1.

Return the minimum possible roof length.

Function

minimumRoofLength(positions: int[], k: int) → long

Examples

Example 1

positions = [2,10,8,17]k = 3return = 9

A roof from position 2 through position 10 covers cars at 2, 8, and 10 and has length 9.

Example 2

positions = [1,2,3]k = 1return = 1

A length-one roof can cover any single car.

Example 3

positions = [7,3,12,4,8]k = 3return = 5

Either positions 3, 4, and 7 or positions 4, 7, and 8 fit under a roof of length 5.

Constraints

  • 1 <= positions.length <= 100000
  • 0 <= positions[i] <= 1000000000
  • All positions are distinct.
  • 1 <= k <= positions.length

More American Express problems

drafts saved locally
public long minimumRoofLength(int[] positions, int k) {
    // Write your code here.
}
positions[2,10,8,17]
k3
expected9
checking account