bugl
bugl
HomeLearnPatternsPathsSearchPremium
HomeLearnPatternsPaths
HardBinary SearchLC 774

Minimize Max Distance to Gas Station

You are given an integer array stations that represents the positions of the gas stations on the x-axis. You are also given an integer k. You should add k new gas stations. You can add the stations anywhere on the x-axis, and not necessarily on an integer position. Let penalty() be the maximum distance between adjacent gas stations after adding the k new stations. Return the smallest possible value of penalty(). Answers within 10-6 of the actual answer will be accepted.

Asked at 1 company
Google
Hints
  • 1.Think about which data structure fits best
  • 2.Consider the time complexity of your approach
  • 3.Look for patterns in the constraints
LeetCode