489. Gas Station — Minimum Stations to Add

Given sorted positions of existing gas stations along a road and a maximum allowed gap maxGap, return the minimum number of additional stations to insert so that no two adjacent stations are more than maxGap apart. Input: '[stations], maxGap'.

Input: '[stations], maxGap'.

Output: Integer — the minimum stations to add.

Examples

Input: [1,5,10,20], 3
Output: 5
Explanation: Gaps 4,5,10 need 1+1+3 inserts.

Input: [0,10], 2
Output: 4
Explanation: Gap 10 needs 4 inserts.

Input: [1,2,3,4,5], 1
Output: 0
Explanation: All gaps already within maxGap.

Constraints

• 1<=n<=10^4
• 1<=maxGap
• sorted positions

Asked by