I_love_penny's blog

By I_love_penny, history, 3 years ago, In English

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). ​​

 
 
 
 
  • Vote: I like it
  • +5
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by codenote (previous revision, new revision, compare).

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But we need to remove exactly k elements.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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.


Code
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    Code
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what if the first and last element is fixed