How to solve this problem using binary search.

Problem Statement :

You are given an array A of N integers in nondecreasing order. Remove K integers such that the maximum difference between two consecutive elements is minimized.

Problem Link

solution using binary search (I am not getting its intuition).

Auto comment: topic has been updated by I_love_penny (previous revision, new revision, compare).Binary search for the maximum difference, to find the minimum maximum difference we can achieve. If you won't allow differences bigger than mid, then you need to "cut" your array removing all differences from the left and right until you clear everything bigger than mid. That leaves, at best, a contiguous segment. So he's just looping to find the biggest contiguous segment that doesn't have any difference greater than mid.

How we are ensuring that exactly k elements are removed from array.

Okay I got it , if we can get subarray by removing <=k elements than we can get subarray by removing k elements also. Thanks :)

how to achieve this if we won't allow to to remove first and last element

You binary search on the answer. For checking a particular value x, you find the longest subarray of length L that has adjacent difference less than x. So you remove (n-L) elements. If this is less than K, you can decrease hi, otherwise you need to go in the right part ie increase lo.

But we need to remove exactly k elements.

Okay I got it , if we can get subarray by removing <=k elements than we can get subarray by removing k elements also. Thanks :)

You can solve this without binary search too.

You should remove k integers either from starting or ending because removing elements from the middle of the array only increases the consecutive difference and It doesn't make sense.

We start by building segment tree on the consecutive differences.

and then we iterate the array from left to right, at every index i we assume that we have removed i elements from starting and now, we need to remove k — i elements from the end.

We now query for the maximum difference in this remaining segment and the final answer would be the minimum of these queries.

CodeYou can solve this without using a segment tree. Simply retain the differences in a set.

CodeHow do we solve this if first and last elements are fixed?

How to make changew to your code, if the first and the last elements are fixed ?

How many problems did you solved? I only solved the one with 20 points

Where did you get the problem in which the first and last elements are fixed? I would like to solve it.

what if the first and last element is fixed

did you get the solution?