# 2616. Minimize the Maximum Difference of Pairs (binary search idea

```
T: O(nlogn)
S: O(1)
```

````java
```java
class Solution {
    public int minimizeMax(int[] nums, int p) {
        Arrays.sort(nums);
        int left = 0;
        int right = nums[nums.length-1] - nums[0];

        while (left < right) {
            int mid = left + (right - left)/2;
            //System.out.println("mid:" + mid);
            int pairCount = 0;
            for (int i = 0; i < nums.length-1; i++) {
                if (nums[i+1] - nums[i] <= mid) {
                    pairCount++;
                    i++; // jump to next pair index (choose this i and i+1 pair)
                }
            }
            if (pairCount >= p) {
                right = mid;
            } else {
                left = mid+1;
            }
        }
        return left;
    }
}

/*
T: O(nlogn)
S: O(1)

 0  1 2 3 4 5
[10,1,2,7,1,3]


find pair 
then return maximum diff

find all pair -> O(n^2)
cal diff and sort asc -> nlogn
find max diff of pair -> O(p)
anyway it doesn't work. 

how to reduce find all pair?

or how to find small diff quickly?

sort?

[10,1,2,7,1,3]

1,1,2,3,7,10

0~9
left = 0
right = 9

0        4         9
-------------------
0      3
    1  right

mid = 0 + 9/2 = 4
p = [1,1], [2,3], [7,10]

right = mid - 1 = 4 - 1 = 3
mid = 0 + 3/2 = 1
p= [1,1], [2,3]

right = mid - 1 = 0
mid = 0
p = [1,1]

pCount < p
left = mid + 1 = 1
---> left > right -> end

return left
  

  so it ok to return left when using left <= right


  so...I think I'll use left < right in the future, because it can return left or right, all is ok
*/
```
````

有問題的code

````
```java
從題意, 會覺得, 那我就 sort, 然後算出各個 diff
在 sort diff, 取前 p 個, 不就是答案嗎 但這樣是有問題的

[3,4,2,3,2,1,2]

why this can't, because it reuse the "index"
1 2 2 2 3 3 4
 1 0 0 1 0 1
   選了 index 0 的 0
   下個 2 2 就不能再用了

   2 2 2
    0 0.  -> 只能選其中一個0

所以這樣sort diff 挑前幾個, 是會重複用到 index 的 ->不可行


本題關鍵在於, sort 後, 選了某對(鄰居)我就可以跳到下個了 greedy 的想法, 
因為如果今天我不挑鄰居, 並不能產生較小的 diff, 因為 sort 後的鄰居, 才能得到小 diff


class Solution {
    public int minimizeMax(int[] nums, int p) {
        Arrays.sort(nums);

        List<Integer> diff = new ArrayList<>();
        for (int i = 0; i < nums.length-1;i++) {
            diff.add(Math.abs(nums[i] - nums[i+1]));
        }
        Collections.sort(diff);
        int result = 0;
        for (int i = 0; i < p; i++) {
            result = Math.max(result, diff.get(i));
        }
        return result;
    }
}

/*
[10,1,2,7,1,3], p = 2
```



```
````

### new version

````
```java
class Solution {
    public int minimizeMax(int[] nums, int p) {
        Arrays.sort(nums);

        int left = 0;
        int right = nums[nums.length-1] - nums[0];

        int result = Integer.MAX_VALUE;
        while (left <= right) {
            int mid = left + (right - left)/2;
            int pCount = 0;
            for (int i = 0; i < nums.length-1; i++) {
                if (nums[i+1] - nums[i] <= mid) {
                    pCount++;
                    i++;
                }
            }
            if (pCount >= p) {
                result = Math.min(result, mid);
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return result;
    }
}

/*
[10,1,2,7,1,3], p = 2

[3,4,2,3,2,1,2]

why this can't, because it reuse the "index"
1 2 2 2 3 3 4
 1 0 0 1 0 1
   選了 index 0 的 0
   下個 2 2 就不能再用了

   2 2 2
    0 0.  -> 只能選其中一個0

所以這樣sort diff 挑前幾個, 是會重複用到 index 的 不可行

1 1 2 3 7 10
 0 1 1 4 3
*/
```
````


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/weekly-contest/2616.-minimize-the-maximum-difference-of-pairs-binary-search-idea.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.