LeetCode Entry

2616. Minimize the Maximum Difference of Pairs

09.08.2023 medium 2023 kotlin

Minimum of maximums possible p diffs of distinct array positions

2616. Minimize the Maximum Difference of Pairs medium blog post substack

image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/303

Problem TLDR

Minimum of maximums possible p diffs of distinct array positions

Intuition

The hint is misleading, given the problem size 10^5 DP approach will give TLE, as it is n^2.

The real hint is:

  • given the difference diff, how many pairs there are in an array, where pair_diff <= diff?
  • if we increase the picked diff will that number grow or shrink?

Using this hint, we can solve the problem with Binary Search, as with growth of diff, there is a flip of when we can take p numbers and when we can’t.

When counting the diffs, we use Greedy approach, and take the first possible, skipping its sibling. This will work, because we’re answering the questions of how many rather than maximum/minimum.

Approach

For more robust Binary Search, use:

  • inclusive lo, hi
  • last condition lo == hi
  • result: if (count >= p) res = minOf(res, mid)
  • move border lo = mid + 1, hi = mid - 1

Complexity

  • Time complexity: \(O(nlog(n))\)

  • Space complexity: \(O(1)\)

Code


    fun minimizeMax(nums: IntArray, p: Int): Int {
        nums.sort()
        var lo = 0
        var hi = nums.last() - nums.first()
        var res = hi
        while (lo <= hi) {
          val mid = lo + (hi - lo) / 2
          var i = 1
          var count = 0
          while (i < nums.size) if (nums[i] - nums[i - 1] <= mid) {
            i += 2
            count++
          } else i++
          if (count >= p) res = minOf(res, mid)
          if (count >= p) hi = mid - 1 else lo = mid + 1
        }
        return res
    }