Twitter Online Assessment (OA) 2021 | Parking Dilemma

You are in charge of a linear parking lot. There are n cars parked permanently in this parking lot. The ith car occupies the pos[i]th parking slot. You feel bad for the car owners of these cars, so you decided to build a roof to cover k cars from the rain. Why build just a singular roof and why only cover k cars instead of every car? You didn't get paid enough for this.

To save costs, you decide to minimize the size of the roof while still making sure you cover at least k cars. Given the positions of these n cars and k, find the minimum number of parking slots this roof should cover.

Parameters

  • pos: A list of integers representing the positions of the cars.
  • k: The minimum amount of cars your roof should cover.

Result

  • The minimum number of parking slots the roof needs to cover.

Examples

Example 1:

Input: pos = [2, 10, 8, 17], k = 3

Output: 9

Explanation: You need a roof spanning from 2 to 10 to cover the first three cars.

Constraints

  • 1 <= n <= 10^5
  • 1 <= k <= n
  • 1 <= pos[i] <= 10^9

Try it yourself

Solution

Title

Script

Lorem Ipsum is simply dummy text of the printing and typesetting industry. Lorem Ipsum has been the industry's standard dummy text ever since the 1500s, when an unknown printer took a galley of type and scrambled it to make a type specimen book.

Contrary to popular belief, Lorem Ipsum is not simply random text.

  >>> a = [1, 2, 3]
  >>> a[-1]
  3

Get premium for instant access to all content and solutions

Upgrade