Solutions

1. Greedy + Dynamic Programming (Top-Down)

class Solution:
    def minimizeMax(self, nums: List[int], p: int) -> int:
        n = len(nums)
        nums.sort()
        dp = {}

        def dfs(i, pairs):
            if pairs == p:
                return 0
            if i >= n - 1:
                return float('inf')
            if (i, pairs) in dp:
                return dp[(i, pairs)]

            take = max(nums[i + 1] - nums[i], dfs(i + 2, pairs + 1))
            skip = dfs(i + 1, pairs)
            dp[(i, pairs)] = min(take, skip)
            return dp[(i, pairs)]

        return dfs(0, 0)

Time & Space Complexity

Time complexity: $O(n * p)$
Space complexity: $O(n * p)$

Where $n$ is the size of the input array and $p$ is the number of pairs to select.

2. Greesy + Dynamic Programming (Bottom-Up)

class Solution:
    def minimizeMax(self, nums: List[int], p: int) -> int:
        n = len(nums)
        nums.sort()

        dp = [[float('inf')] * (p + 1) for _ in range(n + 1)]
        for i in range(n + 1):
            dp[i][0] = 0

        for i in range(n - 2, -1, -1):
            for pairs in range(1, p + 1):
                take = float('inf')
                if i + 1 < n:
                    take = max(nums[i + 1] - nums[i], dp[i + 2][pairs - 1])

                skip = dp[i + 1][pairs]
                dp[i][pairs] = min(take, skip)

        return dp[0][p]

Time & Space Complexity

Time complexity: $O(n * p)$
Space complexity: $O(n * p)$

Where $n$ is the size of the input array and $p$ is the number of pairs to select.

3. Greesy + Dynamic Programming (Space Optimized)

class Solution:
    def minimizeMax(self, nums: List[int], p: int) -> int:
        n = len(nums)
        nums.sort()

        dp = [float('inf')] * (p + 1)
        dp1 = [float('inf')] * (p + 1)
        dp2 = [float('inf')] * (p + 1)

        dp[0] = dp1[0] = dp2[0] = 0
        for i in range(n - 1, -1, -1):
            for pairs in range(1, p + 1):
                take = float('inf')
                if i + 1 < n:
                    take = max(nums[i + 1] - nums[i], dp2[pairs - 1])
                skip = dp1[pairs]
                dp[pairs] = min(take, skip)

            dp2 = dp1[:]
            dp1 = dp[:]
            dp = [float('inf')] * (p + 1)
            dp[0] = 0

        return dp1[p]

Time & Space Complexity

Time complexity: $O(n * p)$
Space complexity: $O(p)$

Where $n$ is the size of the input array and $p$ is the number of pairs to select.

4. Greedy + Binary Search

class Solution:
    def minimizeMax(self, nums: List[int], p: int) -> int:
        if p == 0:
            return 0

        def isValid(threshold):
            i, cnt = 0, 0
            while i < len(nums) - 1:
                if abs(nums[i] - nums[i + 1]) <= threshold:
                    cnt += 1
                    i += 2
                else:
                    i += 1
                if cnt == p:
                    return True
            return False

        nums.sort()
        l, r = 0, nums[-1] - nums[0]
        res = nums[-1] - nums[0]

        while l <= r:
            m = l + (r - l) // 2
            if isValid(m):
                res = m
                r = m - 1
            else:
                l = m + 1

        return res

Time & Space Complexity

Time complexity: $O(n\log n + n\log m)$
Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

Where $n$ is the size of the input array and $m$ is the maximum value in the array.