I_love_penny's blog

Minimize Max Diff (CS Academy Problem)
By I_love_penny, history, 8 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

Comments Comments (7)
| Write comment?
»
8 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.

→ Reply
»
8 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.

→ Reply
  • »
    »
    8 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 :)

    → Reply
»
8 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
→ Reply
  • »
    »
    8 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
    → Reply
  • »
    »
    5 years 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 ?

    → Reply
    • »
      »
      »
      5 years 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

      → Reply