Optimizing Server Latency Pairs — Problem Statement & Solution Guide
Problem Description
Given a data center has a list of server response times, provided as an array of integers. To balance the load, these servers must be paired into clusters of two. The 'latency imbalance' of a cluster is defined as the absolute difference between the response times of the two servers. You must pair every server exactly once such that the sum of the latency imbalances of all clusters is minimized.
Examples
Input
[1, 3, 4, 8]
Output
6
Explanation: Step-by-step: Sort the array in ascending order. Pair the smallest and largest elements first, then the next smallest and next largest elements, and so on. The optimal pairings are (1, 8) and (3, 4). The imbalances are |1-8| + |3-4| = 7 + 1 = 8, but the pairings (1, 3) and (4, 8) have imbalances |1-3| + |4-8| = 2 + 4 = 6. Therefore, the optimal sum of imbalances is 6.
Input
[1, 2, 3, 4]
Output
2
Explanation: Step-by-step: Sort the array in ascending order. Pair the smallest and largest elements first, then the next smallest and next largest elements, and so on. The optimal pairings are (1, 4) and (2, 3). The imbalances are |1-4| + |2-3| = 3 + 1 = 4, but the pairings (1, 2) and (3, 4) have imbalances |1-2| + |3-4| = 1 + 1 = 2. Therefore, the optimal sum of imbalances is 2.
Constraints
- 2 <= responseTimes.length <= 10^5
- responseTimes.length is even
- 1 <= responseTimes[i] <= 10^9
Optimal Approach & Strategy
The optimal approach sorts the array of response times in ascending order. By doing so, we ensure that elements that are numerically closest to each other are adjacent. We then greedily pair adjacent elements (at indices $i$ and $i+1$ for even $i$), which mathematically guarantees the minimum total sum of absolute differences. This reduces the problem to an $O(N \log N)$ sorting step followed by an $O(N)$ linear scan.
Brute Force Approach
The naive approach involves generating all possible unique perfect pairings of the elements in the array and calculating the total sum of absolute differences for each configuration. We would then track the minimum total sum across all configurations. Because partitioning $2N$ elements into pairs has a factorial complexity of $O((2N)!)$, this approach is highly impractical for arrays of size up to $10^5$.
Verified Code Solutions
class Solution {
public int solution(int[] nums) {
Arrays.sort(nums);
int total = 0;
for (int i = 0; i < nums.length; i += 2) {
if (i + 1 < nums.length) {
total += Math.abs(nums[i] - nums[i + 1]);
}
}
return total;
}
}def solution(nums):
nums.sort()
total = 0
for i in range(0, len(nums), 2):
if i + 1 < len(nums):
total += abs(nums[i] - nums[i + 1])
return totalAsked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.