mediumTwo PointersPattern: Two Pointers
Optimizing Server Latency Pairs Solution
Problem Statement
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. Given an array of response times, return the minimum total latency imbalance. Note that the total imbalance can exceed the range of a standard 32-bit signed integer.
Examples
Example 1:
Input:responseTimes = [1, 3, 4, 8]
Output:6
Explanation: Sort the array: [1, 3, 4, 8]. Pair (1, 3) and (4, 8). Imbalance = |1-3| + |4-8| = 2 + 4 = 6. This is the minimum possible total imbalance.
Example 2:
Input:responseTimes = [10, 20, 30, 40, 50, 60]
Output:30
Explanation: Sort the array: [10, 20, 30, 40, 50, 60]. Pair (10, 20), (30, 40), and (50, 60). Imbalance = |10-20| + |30-40| + |50-60| = 10 + 10 + 10 = 30.
Constraints
- 2 <= responseTimes.length <= 10^5
- responseTimes.length is even
- 1 <= responseTimes[i] <= 10^9
Time: O(N log N) Space: O(1)
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.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
No solution code is currently loaded.
Complete this code in the workspace editor.