1676. Skip Stones

There are n stones between the starting point and the end point. The distance between the starting point and the ith (i starts from 0) stone is d[i]. And the distance between the starting point and end point is target. From the starting point, we can only jump to the adjacent stone until the end point.

Now you can remove at most m stones. Return the maximum value of the shortest jump distance in your jumping from start point to end point.

1. $0 \leq m \leq n \leq 50,000$
2. $1 \leq target \leq 1,000,000,000$
3. These stones are given in order from small to large distances from the starting point, and no two stones will appear in the same place.

Have you met this question in a real interview?  

Example

Example 1:

Input: n = 5, m = 2, target = 25, d = [2,11,14,17,21]
Output: 4
Explanation: Remove the first stone and the third stone. Then the jump path is :
  1. 0 -> 11  11
  2. 11 -> 17 6
  3. 17 -> 21 4
  4. 21 -> 25 4 

Code(Language:C++)

class Solution {
public:
    /**
     * @param n: The total number of stones.
     * @param m: The total number of stones you can remove.
     * @param target: The distance from the end to the starting point.
     * @param d: The array that the distance from the i rock to the starting point is d[i].
     * @return: Return the maximum value of the shortest jump distance.
     */
        int getDistance(int n, int m, int target, vector<int> &d) {
        if (n == 0) return target;
        int start = 0, end = target;
        d[n] = target;
        while(start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (isValid(n, m, target, d, mid)) start = mid;
            else end = mid;
        }
        if (isValid(n, m , target, d, end)) return end;
        return start;
    }
    
private:
    bool isValid(int n, int m, int target, vector<int> & d, int gap) {
        int count = 0, lastPos = 0;  
        for (int i = 0; i <= n; ++i) {
            if (d[i] - lastPos < gap) count++;
            else lastPos = d[i];
        }
        
        if (count <= m) return true;
        return false;
    }
};